图

SyEic_L Lv4
  2026-03-12 17:41:49 2026-03-12 17:41:49 Created   2026-03-12 17:41:49 2026-03-12 17:41:49 Updated    3.7k Words  16 Mins  

概念

  • 由顶点集合和顶点间的关系集合组成的数据结构：Graph=(V,E)Graph = (V, E)

    • V：顶点集合
    • E：边集合
    • Path(x,y)Path(x,y)：从x到y的单向通路，有方向的

  • 有向图与无向图

    • 有向图中，顶点对<x,y><x,y>是有序的
    • 无向图中，顶点对<x,y><x,y>是无序的

  • 完全图

    • n个顶点的无向图有n(n−1)2\frac{n(n-1)}{2}条边，则为完全无向图
    • n个顶点的有向图有n(n−1)n(n-1)条边，为完全有向图

  • 邻接顶点：如果(u,v)(u,v)是E(G)E(G)中的一条边，则u与v互为邻接顶点

  • 子图：顶点集和边集都是子集，则图是子图

  • 权：某些图的边具有与它相关的数（例如距离）

  • 顶点的度

    • 一个顶点v的度是与它相关联的边的条数，TD(v)TD(v)
    • 有向图的度是出度入度之和

  • 路径

    • 路径长度
      • 非带权图的路径长度为路径上边的条数
      • 带权图的路径长度是路径上各边的权之和
    • 简单路径：路径顶点均不互相重复
    • 回路：路径上第一个顶点v1v_1和最后一个顶点vmv_m重合

  • 连通图与连通分量

    • 无向图中，若从顶点v1v_1到顶点v2v_2有路径，则是连通的
    • 如果图中热议一对顶点都是连通的，则此图是连通图
    • 非连通图的极大连通子图叫做连通分量

  • 强连通图与强连通分量

    • 有向图中，对于每一对顶点viv_i和vjv_j，都存在一条从viv_i到vjv_j和vjv_j到viv_i的路径，则为强连通图
    • 非强连通图的极大连通子图叫做强连通分量

  • 生成树：一个连通图的生成树是其极小连通子图，在n个顶点的情形下，有n−1n-1条边

存储表示

  • 邻接矩阵
  • 邻接表

邻接矩阵

  • 顶点表用二维数组表示

  • 有n个顶点的图，则邻接矩阵是A.edge[n][n]

  • A.edge[n][n]={1,如果<i,j>∈E或者(i,j)∈E0,else A.edge[n][n] = \begin{cases} 1, & 如果<i,j>\in E或者(i,j)\in E\\ 0, & else \end{cases}

  • 无向图的邻接矩阵是对称的

    • 第i行1的个数是i的度

  • 有向图的邻接矩阵可能是不对称的

    • 第i行1的个数是i的出度
    • 第j列1的个数是j的入度

网络的邻接矩阵

A.edge[n][n]={W(i,j),若i≠j且<i,j>∈E或者(i,j)∈E∞,若i≠j且<i,j>∉E或者(i,j)∉E0,若i==j A.edge[n][n] = \begin{cases} W(i,j), & 若i\neq j且<i,j>\in E或者(i,j)\in E\\ \infty , &若i\neq j且<i,j>\notin E或者(i,j)\notin E\\ 0, & 若i==j \end{cases}

空间复杂度：O(n2)O(n^2)

邻接表

  • 无向图

    • 同一个顶点发出的边链接在同一个边链表中，每个链节点代表一条边

      无向图邻接表

  • 有向图

    • 邻接表（出边表）

    • 逆邻接表（入边表）

      有向图邻接表

  • 带权图

    • 每个链表节点带一个cost

      带权图邻接表

容易找到邻接点，但判断两个顶点之间是否有边不如邻接矩阵方便

基本操作

构造

  • 邻接矩阵
    • 构造顶点数组
    • 初始化邻接矩阵
    • 输入边，确定顶点在顶点数组中的位置，邻接矩阵赋值
  • 邻接表

遍历

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//递归
template<class Type> void DFS (Graph<Type>& G) {
    int n = G.NumberOfVertices( );
    static int * visited = new int [n];
    for ( int i = 0; i < n; i++ ){ //访问数组
        visited [i] = 0; //visited 初始化
    }
    DFS (G, 0, visited ); //从图G的顶点0开始搜索
    delete [ ] visited; //释放 visited
}

//非递归
void DFS ( Graph<Type>& G, int v, int visited [ ] ) {
    cout << G.GetValue (v) << ‘ ’; //访问顶点 v
    visited[v] = 1; //顶点 v 作访问标记
    int w = G.GetFirstNeighbor (v);
    while ( w != -1 ) { //若邻接顶点 w 存在
        if ( !visited[w] ){
            DFS ( G, w, visited );	//若顶点 w 未访问过, 递归访问顶点 w
        } 
        w = G.GetNextNeighbor ( v, w );
        //取顶点 v 排在 w 后的下一个邻接顶点
    }
}

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
template<class Type> void BFS ( Graph <Type>& G, int v ){
    int n = G.NumberOfVertices( );
    int * visited = new int[n];
    for ( int i = 0; i < n; i++ ){
    	visited[i] = 0; 
    } 
    cout << G.GetValue (v) << ' ';
    visited[v] = 1;
    Queue<int> q; 
    q.EnQueue (v); //进队列
    while ( !q.IsEmpty ( ) ) { //队空搜索结束
        q.GetFront(v); 
        q.DeQueue ( );
        int w = G.GetFirstNeighbor (v);
        while ( w != -1 ) { //若邻接顶点 w 存在
            if ( !visited[w] ) { //未访问过
                cout << G.GetValue (w) << ‘ ’;
                visited[w] = 1; 
                q.EnQueue (w);
            }
            w = G.GetNextNeighbor (v, w);
        } //重复检测 v 的所有邻接顶点
    } //外层循环，判队列空否
    delete [ ] visited; 
}

最小生成树

  • 按照生成树的定义，n个顶点的连通网络的生成树有n个顶点，n-1条边
  • 构造准则
    • 必须使用且仅使用网络中的n-1条边来联结网络中的n个顶点
    • 不能使用产生回路的边
    • 各边上的权值综合达到最小

克鲁斯卡尔算法（Kruskal）

  • 先构造一个n个顶点，没有边的非连通图T={V,∅}T = \{V, \empty\}，图中每个顶点自成一个连通分量
  • 在E中选一条最小权值的边，若该边的两个顶点落在不同的连通分量上，则将此边加入到T中，否则舍去，重新选择一条权值最小的边
  • 重复，直到所有顶点都在同一个连通分量上

kruskal

  • 利用最小堆和并查集

    堆中每个节点的格式：tail | head | cost

    ​ 两个节点位置 边的权值

  • 检查一条边的tail、head是否在同一连通分量上，是则舍去，否则将此边加入T，同时将两个顶点放在同一个连通分量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct DSU {
    vector<size_t> pa, size;

    explicit DSU(size_t size_) : pa(size_), size(size_, 1) {
        iota(pa.begin(), pa.end(), 0);
    }

    size_t find(size_t x) {
        return pa[x] == x ? x : pa[x] = find(pa[x]);
    }

    void unite(size_t x, size_t y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (size[x] < size[y]) swap(x, y);
        pa[y] = x;
        size[x] += size[y];
    }
};

struct Edge {
    int tail, head, cost;
};

struct EdgeCompare {
    bool operator()(const Edge& a, const Edge& b) const {
        return a.w > b.w;  // 小权值优先
    }
};

vector<Edge> kruskal(int n, const vector<Edge>& edges) {
    priority_queue<Edge, vector<Edge>, EdgeCompare> pq(edges.begin(), edges.end());

    DSU dsu(n);
    vector<Edge> MST;

    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        if (dsu.find(e.tail) != dsu.find(e.head)) {
            dsu.unite(e.tail, e.head);
            MST.push_back(e);
        }
    }
    return MST;  // 返回生成树
}

复杂度分析

  • 建立e条边的最小堆

    总的建堆时间O(elog2e)O(elog_2e)，检测邻接矩阵O(n2)O(n^2)

  • 构造最小生成树

    出堆操作：e 总时间O(elog2e)O(elog_2e)

    find操作：2e 总时间O(elog2n)O(elog_2n)

    Union操作：n-1 总时间O(n)O(n)

  • 总时间复杂度：O(elog2e+elog2n+n2+n)O(elog_2e+elog_2n+n^2+n)

邻接表更好

普利姆算法（Prim）

  1. 从某一顶点u0u0出发，U={u0},TE={}U = \{u0\}, TE= \{\}

  2. 每次选择一条边，这条边是所有(u,v)(u,v)中权最小的边，u∈U,v∈V−Uu \in U, v \in V-U

    TE=TE+[(u,v)]TE = TE + [(u,v)] U=U+[v]U = U +[v]

  3. 当U≠VU\neq V时，转2

prim

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
vector<Edge> prim(int n, const vector<vector<Edge>>& adj, int start = 0) {
    vector<bool> visited(n, false);
    priority_queue<Edge, vector<Edge>, EdgeCompare> pq;

    vector<Edge> MST;   // 保存生成树的边

    visited[start] = true;

    // 把 start 的所有邻接边加入堆
    for (auto& e : adj[start]) {
        pq.push(e);
    }

    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        // e.tail -- e.head（tail 是树内点，head 是外部点）
        if (visited[e.head]) continue;  // 若 head 已在树中，跳过

        // 接受该边
        MST.push_back(e);
        int newNode = e.head;
        visited[newNode] = true;

        // 将新加入节点的所有边加入堆
        for (auto& ne : adj[newNode]) {
            if (!visited[ne.head]) {
                pq.push(ne);
            }
        }
    }

    return MST;
}

最短路径

Dijkstra算法（权值非负的单源最短路径）

  • 引入辅助数组dist，dist[i]表示从源点v0v_0到终点viv_i的最短路径长度

    • 初始状态：

      若从源点v0v_0到顶点viv_i有边，则dist[i]为边上的权值

      若从源点v0v_0到顶点viv_i无边，则dist[i]为∞\infin

  • 具体算法

    • 初始化：

      S={v0}S = \{v_0\}

      dist[j] = Edge[0][j], j=1,2,…,n-1

    • 求出最短路径的长度：

      dist[k] = min{dist[i]} , i∈V−Si \in V-S

      S=S ∪{K}S = S \space \cup \{K\}

    • 修改：

      dist[i] = min{dist[i], dist[k] + Edge[k][i]}, i∈V−Si \in V-S

    • 判断：

      若S=VS=V，则算法结束，否则重复

  • 用path数组来记录路径

  • 时间复杂度O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void dijkstra(Graph<float>& G, int v, float dist[], int path[]){
    int n = G.NumberOfVertices();
    int* S = new int[n]; // 是否已确定最短路的集合

    // --- 初始化 ---
    for (int i = 0; i < n; i++) {
        dist[i] = G.GetWeight(v, i);   // 初始距离
        S[i] = 0;                      // 都不在 S 集合中

        if (i != v && dist[i] < MaxValue)
            path[i] = v;               // 有边：前驱是 v
        else
            path[i] = -1;              // 无边：无前驱
    }
    S[v] = 1;
    dist[v] = 0;
    path[v] = -1;

    // --- 主循环 ---
    for (int i = 0; i < n - 1; i++) {

        float minDist = MaxValue;
        int u = v;

        // 找 dist 中未加入 S 的最小值下标 u
        for (int j = 0; j < n; j++) {
            if (!S[j] && dist[j] < minDist) {
                u = j;
                minDist = dist[j];
            }
        }

        S[u] = 1; // 把 u 加入 S

        // 用 u 松弛其他点
        for (int k = 0; k < n; k++) {
            float w = G.GetWeight(u, k);

            if (!S[k] && w < MaxValue && dist[u] + w < dist[k]) {
                dist[k] = dist[u] + w;
                path[k] = u; // 更新最短路前驱
            }
        }
    }

    delete[] S;
}

Floyd算法

floyd

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void floyd(Graph<float>& G, float a[][100], int path[][100]) 
{
    int n = G.NumberOfVertices();

    // ----- 初始化 -----
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {

            a[i][j] = G.GetWeight(i, j);

            if (i != j && a[i][j] < MaxValue)
                path[i][j] = i;      // i→j 有直接边，前驱是 i
            else
                path[i][j] = 0;      // 无路径
        }

    // ----- Floyd 主过程 -----
    for (int k = 0; k < n; k++){          // 枚举中间点 k
        for (int i = 0; i < n; i++){      // 枚举起点 i
            for (int j = 0; j < n; j++){  // 枚举终点 j
                if (a[i][k] + a[k][j] < a[i][j]) {
                    a[i][j] = a[i][k] + a[k][j];
                    path[i][j] = path[k][j];  // j 的前驱通过 k 更新
                }
            }
        }
    }   
}
  • 允许带负权值的边，但不允许包含带负权值的回路
  • 时间复杂度：O(n3)O(n^3)

活动网络

  • 用顶点表示活动的网络（AOV网络）：拓扑排序
  • 用边表示活动的网络（AOE网络）：关键路径

AOV网络

  • 描述工程或系统进程
  • 子工程之间存在一定的先决条件约束

拓扑排序

  1. 输入AOV网络，n为顶点个数
  2. 选一个入度为0的顶点，并输出（如果同时存在多个，随便选择一个）
  3. 从图中删去该顶点，同时删去所有它发出的有向边
  4. 重复2、3步，直到
    • 全部顶点均已输出
    • 或图中还有未输出的顶点，但入度不为0，说明网络中不存在有向环
算法实现
  1. AOV网用邻接表实现
  2. count：存放各顶点的入度
  3. 建立入度为0的顶点栈
  4. 顶点从0开始编号
  5. 每输入一条边，建立一个边节点，链入相应边链表中，统计入度信息
  6. 当入度为0的顶点栈不空时，重复执行：
    • 从顶点栈中退出一个顶点吗，并输出
    • 从AOV网络中删去这个顶点和它发出的边，边的终顶点入度减1
    • 如果边的终顶点入度减至0，则该顶点进入度为0的顶点栈
  7. 如果输出顶点少于AOV网络的顶点个数，则报告网络中存在有向环
  • 顶点栈的建立，不用额外分配存储空间，直接利用入度为0的顶点对count[]数组元素
    • 顶点i进栈时：count[i] = top; top = i;
    • 退栈操作：j = top; top = count[top];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void TopologicalSort ( Graph<Type>& G ) {
    int i, j, k;
    int top = -1; //入度为零的顶点栈初始化
    int n = G.NumberOfVertices( ); //顶点个数
    int *count = new int[n]; //入度为零顶点栈
    for ( i = 0; i < n; i++ ){ //入度为零顶点
        if ( count[i] == 0 ){ //进栈
            count[i] = top; top = i; }
            for ( i = 0; i < n; i++ ){ //期望输出n个顶点
                if ( top == -1 ) { //中途栈空,转出
                    cout << “network has a cycle" << endl;
                    return;
                }
            }
    	}
        else { //继续拓扑排序
            int j = top; top = count[top]; //退栈
            cout << j << endl; //输出
            Edge <int> *l=NodeTable[j].adj;
            while (l){
                int k=l.dest;
                if (--count==0) {
                    count[k]=top;
                    top=k;
                }
                l=l->link;
            }
        }
    }
}

复杂度

  • n个顶点，e条边

  • 建立链式栈：O(n)O(n)

  • 每个顶点输出一次，每条边被检查一次：O(n+e)O(n+e)

  • 总复杂度：O(n+e)O(n+e)

AOE网络

  • 事件顶点网络

  • 顶点表示事件

  • 有向边表示活动

  • 边上权值表示活动持续时间

  • 无环有向图

  • 有唯一的入度为0的开始顶点

    ​ 唯一的出度为0的完成顶点

工程估算
  • 完成整个工程至少需要多少时间
  • 缩短完成工程所需的时间，应该加快哪些活动

关键路径（critical path）

从开始顶点到完成顶点的最长

计算关键活动

  • Ve[i]Ve[i]：事件ViV_i的最早可能开始时间 
            是从源点{% _internal_math_placeholder 106 %}到顶点{% _internal_math_placeholder 107 %}的最长路径长度
  • Vl[i]Vl[i]：事件ViV_i的最迟允许开始时间
  • e[k]e[k]：活动aka_k的最早可能开始时间 
            {% _internal_math_placeholder 112 %}
  • l[k]l[k]：活动aka_k的最迟允许开始时间

  • 时间余量：l[k]−e[k]l[k]-e[k]

    如果时间余量为0，则是关键活动

顺序生成VeVe数组，逆序生成VlVl数组

  • Title: 图
  • Author: SyEic_L
  • Created at : 2026-03-12 17:41:49
  • Updated at : 2026-03-12 17:41:49
  • Link: https://blog.syeicl.vip/2026/03/12/图/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
树 树 排序 排序 数组、串与广义表 数组、串与广义表
推荐阅读
树 树 排序 排序
Comments
On this page
图
  1. 概念
  2. 存储表示
    1. 邻接矩阵
    2. 邻接表
  3. 基本操作
    1. 构造
    2. 遍历
    3. BFS
  4. 最小生成树
    1. 克鲁斯卡尔算法（Kruskal）
    2. 普利姆算法（Prim）
  5. 最短路径
    1. Dijkstra算法（权值非负的单源最短路径）
    2. Floyd算法
  6. 活动网络
    1. AOV网络
    2. AOE网络