Graph¶

Definitions¶

1. G(V, E)

• \(G\) 表示 图（graph）
• \(V = V(G)\) 表示关于 顶点（vertices） 的有限非空集合

• \(E = E(G)\) 表示关于 边（edges/arcs） 的有限集合

• 无向图（undirected graph）：\((v_i,v_j) = (v_j,v_i)\)

• 有向图（directed graph, digraph）：\(<v_i,v_j> \neq <v_j,v_i>\) （单行线）

稀疏图 稠密图 完全图

Representation of Graph¶

邻接矩阵 (adjacency matrix)

无向图 -- 将 下三角矩阵 存入一维数组中（节约一半空间）

\(a_{ij}\)的索引为 \(\frac{i(i+1)}{2} + j\)

• 查看任意一对顶点间是否存在边
• 查找某个顶点的所有邻接点（有边直接相连的顶点）
• 计算任一顶点的度数（degree）
  • 出度：从该顶点 出发 的边的数量
  • 入度：指向 / 到达该顶点的边的数量
  • 无向图：度数 = 出度 = 入度
  • 有向图：度数 = 出度（行） + 入度（列）

不适合存储 稀疏图（sparse graph） -- 边的数量远小于顶点数量的平方

稠密图 -- 边的数量接近于顶点数量的平方

邻接表 (adjacency list)

邻接多重表 (adjacency multilist)

Graph Traversal遍历¶

Depth-First Search (DFS)¶

深度优先搜索（DFS）-- (前序遍历 的泛化推广)

从一个起始顶点开始，沿着图的边向下探索，直到无法继续为止，然后回溯到上一个顶点继续探索其他路径。

走到一个没有任何未访问邻居的节点时，不能直接“瞬移”到图上的另一个点，而是必须按原路退回到上一个还有岔路口的节点

    void DFS(Vertex V){
        visited[V] = true; // 标记当前顶点为已访问
        for (each neighbor W of V) { // 遍历V的所有邻接点
            if (!visited[W]) // 如果邻接点W未被访问
                DFS(W); // 递归调用DFS访问邻接点W
        }
    }

recursive

若有N个顶点、E条边

• 时间复杂度
  • 邻接表：\(O(N+E)\)
  • 邻接矩阵：\(O(N^2)\)
• 空间复杂度 \(O(N)\)（递归调用栈的深度）

Breadth-First Search (BFS)¶

广度优先搜索（BFS）-- （层序遍历 的泛化推广）

    void BFS(Vertex V){
        visited[V] = true;       // 标记当前顶点为已访问
        Enqueue(V, Q);           // 将起始顶点V加入队列Q
        while (!IsEmpty(Q)) {    // 当队列Q不为空
            V = Dequeue(Q);      // 从队列Q中取出一个顶点V
            for (each neighbor W of V) {    // 遍历V的所有邻接点
                if (!visited[W]) {          // 如果邻接点W未被访问
                    visited[W] = true;      // 标记邻接点W为已访问
                    Enqueue(W, Q);          // 将邻接点W加入队列Q
                    }
            }
        }
    }

若有N个顶点、E条边

• 时间复杂度
  • 邻接表：\(O(N+E)\)
  • 邻接矩阵：\(O(N^2)\)
• 空间复杂度 \(O(N)\)（队列中最多同时存在N个顶点）

Topological Sort¶

拓扑排序（topological sort）-- AOV网（activity on vertex network）

对于有向图 \(G\)，\(V(G)\)表示活动，\(E(G)\) 表示位次关系

• 拓扑序（topological order）

  拓扑序不唯一

• 有效的AOV网一定是有向无环图 (Directed Acyclic Graph, DAG)

void TopSort(Graph G) {
    int cnt;
    Vertex V, W;
    for(cnt = 0; )
}

Shortest Path¶

最短路径问题（shortest path problem）-- AOE网（activity on edge network）

在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那条路径（最短路径 Shortest Path）

• 源点 （source vertex）-- 起点
• 汇点 （sink vertex）-- 终点

Network Flow¶

网络流（network flow）-- 流量图（flow graph）、残量图（residual graph）

Minimum Spanning Tree (MST)¶

最小生成树（minimum spanning tree, MST）-- Prim算法、Kruskal算法

HW8 -- Graph¶

HW9 -- Shortest Path¶

HW10 -- Network Flow & Minimum Spanning Tree¶