Directed Graph - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

无向图和有向图

图Graph 有向图Directed Graph
结点Nodes（或顶点Vertices） 至少一个 至少一个
边Edges（或弧Arcs） 1. 每条边edge连接图中两个（=2）结点nodes（有的结点nodes可能没有边edges相连）
2. 每条边edge都是唯一的		 1. 每条边edge连接图中两个（=2）结点nodes（有的结点nodes可能没有边edges相连）
2. 每条边edge都是唯一的
3. 每条边edge都是有方向的

有向图Directed Graph的定义 Graph G = <V, E>

  • V是结点nodes的集合
    • 至少一个|V| > 0
  • E是边edges的集合
    • E ⊆ {(v, w) : (v ∈ V), (w ∈ V)}
    • 定义一条从v到w的边 e = (v, w) 这里是有向的
    • 每条边edge都是唯一的 For all e1, e2 ∈ E : e1 ≠ e2

图解

graph graph graph

有向图Directed Graph的术语

入度In-degree 出度Out-degree
定义 某点作为图中边的终点的次数之和 某点作为图中边的起点的次数之和
图例 graph graph

入门连接

图Graph, 深度优先遍历(DFS), 广度优先遍历(BFS)【数据结构和算法入门9】

要点

  • 有向图的邻接矩阵和邻接表都要注意，每次添加或移除结点时，只需要考虑一个方向，e = (v, w)和e = (w, v)是代表不同的边

适用场景

⚠️ **GitHub.com Fallback** ⚠️