图论入门：基本概念、表示方法与遍历算法详解

图论入门：基本概念、表示方法与遍历算法详解

引用

CSDN

1.

https://blog.csdn.net/Macw07/article/details/144280264

图论是计算机科学和数学领域的重要基础知识，本文将系统地介绍图论的基本概念、图的表示方法、图的性质以及图的遍历算法，并附有相应的代码示例。

何为图论

见名知意，图论 (Graph Theory)就是研究图 (Graph)的数学理论和方法。图是一种抽象的数据结构，由节点 (Node)和 连接这些节点的边 (Edge)组成。图论在计算机科学、网络分析、物流、社会网络分析等领域有广泛的应用。

图的基本概念

在详细讲解图论和有关图论算法之前，先来了解一下在图论中的一些基本表述和规范。

1. 图 (Graph)：图是一种由一组顶点和一组边组成的数据结构，记做G = ( V , E ) G = (V, E)G=(V,E)，其中V VV代表顶点集合，E EE 代表边集合。
2. 顶点 (Vertex)：顶点是图的基本单位，也称为节点。
3. 边 (Edge)：一条边是连接两个顶点的线段或弧。可以是无向的，也可以是有向的。一条边可以记做为( u , v ) (u, v)(u,v)。在无向图中，若存在一条( u , v ) (u, v)(u,v)，表示可以从u uu点直接走到v vv点，反之亦然。但若在有向图中，存在一条边( u , v ) (u, v)(u,v)，表示可以从u uu节点直接走向v vv节点，如果不存在一条边v , u v, uv,u，那么v vv节点就没有办法直接走向u uu节点。
4. 无向图 (Undirected Graph)：图中的边没有方向，即( u , v ) (u, v)(u,v)和( v , u ) (v, u)(v,u)是同一条边。
5. 有向图 (Directed Graph/ Digraph)：图中的边有方向，即( u , v ) (u, v)(u,v)和( v , u ) (v, u)(v,u) 不是同一条边。
6. 简单图 (Simple Graph)：表示含有重边（两个顶点之间的多条边）和自环（顶点到自身的边）的图。
7. 多重图 (Multigraph)：允许有重边和自环的图。
8. 边权 (Weight of an Edge)：一般表示经过这一条边的代价（代价一般是由命题人定义的）。

图的表示方法

在计算机中，图可以通过许多方式来构建和表示。总的可以分成图的邻接矩阵和邻接表两种方法（关于链式前向星本文不过多展开叙述，有兴趣的可以自行查阅相关文档）。

图的邻接矩阵 (Adjacency Matrix)

若一个图中有N NN个顶点，那么我们就可以用一个N × N N \times NN×N的矩阵来表示这个图。我们一般定义，若矩阵的元素A i , j ≠ − ∞ A_{i, j} \neq -\inftyAi,j =−∞表示从节点i ii到j jj有一条有向边，其中边的权值为A i , j A_{i, j}Ai,j 。

假设存在一个有3 33个顶点的图，并且有三条有向边E = { ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 2 ) } E = {(1, 2), (2, 3), (3, 2)}E={(1,2),(2,3),(3,2)}，那么就可以用邻接矩阵表示为：

G = [ 1 2 3 1 0 1 0 2 0 0 1 3 0 1 0 ] G = \begin{bmatrix} & \mathtt{1} & \mathtt{2} & \mathtt{3}\ \mathtt{1} & 0 & 1 & 0 \ \mathtt{2} & 0 & 0 & 1 \ \mathtt{3} & 0 & 1 & 0 \end{bmatrix}G= 123 1000 2101 3010

画成可视化的图就长这个样子：

在 C++ 中，我们可以简单地用一个二维数组来表示：

// 定义一个矩阵。
int map[50][50];
// 将所有的边初始化为负无穷大。
for (int i=1; i<=50; i++)
    for (int j=1; j<=50; j++)
        map[i][j] = -0x7f7f7f7f;
// 建边，其中所有的边权为1。
map[1][2] = map[2][3] = map[3][2] = 1;

图的邻接表 (Adjacency List)

邻接表本质上就是用链表表示图。数组的每个元素表示一个顶点，元素的值是一个链表，链表中存储该顶点的所有邻接顶点。假设存在一个有4 44个顶点的图，并且有四条有向边E = { ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 2 ) , ( 3 , 4 ) } E = {(1, 2), (2, 3), (3, 2), (3, 4)}E={(1,2),(2,3),(3,2),(3,4)}，那么就可以用邻接表表示为：

画成可视化的图就长这个样子：

在 C++ 中，我们可以使用 STL模板库 中的 vector 来实现：

#include <vector>
vector<int> G[50];  // 建图。
G[1].push_back(2);
G[2].push_back(3);
G[3].push_back(2);
G[3].push_back(4);

一般情况下，推荐使用邻接表的方式来存图，因为使用邻接矩阵比较浪费空间。在顶点数量非常多但边非常少的图中，N 2 N^2N2的时空复杂度会导致 MLE 或 TLE 等问题。

图的各种性质

1. 度数 (Degree)：一个顶点的度是连接该顶点的边的数量。在有向图中，有入度 (Indegree)和出度 (Outdegree)之分（具体例子见后文）。
2. 路径 (Path)：从一个顶点到另一个顶点的顶点序列，路径上的边没有重复。
3. 回路 (Cycle)：起点和终点相同的路径。
4. 连通图 (Connected Graph)：任意两个顶点之间都有路径相连的无向图。
5. 强连通图 (Strongly Connected Graph)：任意两个顶点之间都有路径相连的有向图。

对于下面这个无向图不连通图，顶点1 11的度数为1 11；顶点2 22的度数为2 22；顶点3 33的度数为1 11；顶点4 44的度数为0 00。同时，由于4 44号顶点没有度数，所以该顶点没有办法到达任何一个其他的顶点，所以这个图是一个不连通图：

图的遍历

图通常采用深度优先搜索/ 广度优先搜索这两个算法来遍历。其中深度优先算法是最常见的遍历算法。

对于一个用邻接矩阵保存的图，其深度优先搜索遍历的 C++ 代码如下：

int vis[105], map[105][105];
void dfs(int node){
    if (vis[node]) return ;
    vis[node] = 1;
    cout << node << endl;
    for (int i=1; i<=n; i++)
        if (map[node][i] != -0x7f7f7f7f)
            dfs(i);
    return ;
}
// 函数调用：dfs(1); 表示从1号顶点开始遍历。

对于一个用邻接表保存的图，其深度优先搜索遍历的 C++ 代码如下：

#include <vector>
vector<int> G[105];
int vis[105];
void dfs(int node){
    if (vis[node]) return ;
    vis[node] = 1;
    cout << node << endl;
    for (int to : G[node])
        dfs(to);
    return ;
}
// 函数调用：dfs(1); 表示从1号顶点开始遍历。

广度优先搜索的方式也类似：

#include <queue>
vector<int> G[105];
int vis[105];
void bfs(int node){
    queue<int> que;
    que.push(node);
    while(!que.empty()){
        int t = que.front();
        cout << t << endl;
        que.pop();
        for (int to : G[node]){
            if (!vis[to]) {
                vis[to] = 1;
                que.push(to);
            }
        }
    }
    return ;
}
// 函数调用：bfs(1); 表示从1号顶点开始遍历。

对于判断无向图的连通性，我们只需要从任意一个点开始跑一遍深搜或者广搜就行了。如果所有顶点的 vis 都被标记了，则证明图是联通的，否则图就是不连通的。

例题讲解

P3916 图的遍历

模板题目，从每一个顶点开始用深搜遍历一遍就可以了。但从每一个点考虑能走到的最大点比较麻烦，一个更优的解决办法是反向建边，从最大的点开始遍历，这样子就可以一次性计算出多个结果。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 10005;
int n, m, ans, vis[N];
vector<int> G[N];
void dfs(int node, int d){
    if (vis[node]) return ;
    vis[node] = d;
    ans = max(node, ans);
    for (int to : G[node]) 
        dfs(to, d);
    return ;
}
int main(){
    cin >> n >> m;
    for (int i=0, u, v; i<m; i++){
        cin >> u >> v;
        G[v].push_back(u);  // 反向建边。
    }
    for (int i=n; i>=1; i--) dfs(i, i);
    for (int i=1; i<=n; i++) 
        cout << vis[i] << ' ';
    return 0;
}

P5318 【深基18.例3】查找文献

也是一道模板题目，正常遍历即可。

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100005;
int n, m;
int vis1[MAXN], vis2[MAXN];
queue<int> que;
vector<int> G[MAXN];
void dfs(int node, int current){
    vis1[node] = 1;
    cout << node << ' ';
    if (current == n) return ;
    for (int i=0; i<G[node].size(); i++){
        if (vis1[G[node][i]]) continue;
        dfs(G[node][i], current+1);
    }
    return ;
}
void dfs(int node){
    vis2[node] = 1;
    que.push(node);
    while(que.size()){
        int t = que.front();
        cout << t << " ";
        for (int i=0; i<G[t].size(); i++){
            if (vis2[G[t][i]]) continue;
            vis2[G[t][i]] = 1;
            que.push(G[t][i]);
        }
        que.pop();
    }
    return ;
}
int main(){
    cin >> n >> m;
    for (int i=0; i<m; i++){
        int t1, t2;
        cin >> t1 >> t2;
        G[t1].push_back(t2);
    }
    for (int i=1; i<=n; i++) 
        sort(G[i].begin(), G[i].end());
    dfs(1, 0), cout << endl, dfs(1);
    return 0;
}

番外 - 图的常见算法

更多关于图论的算法，请持续关注后续更新。

1. 深度优先搜索 (DFS)：适用于遍历图和检测图中的回路。
2. 广度优先搜索 (BFS)：适用于寻找最短路径（无权图）。
3. Dijkstra 算法：适用于加权图中寻找单源最短路径。
4. Bellman-Ford 算法：适用于有负权边的图中寻找单源最短路径。
5. Floyd-Warshall 算法：适用于寻找所有顶点对之间的最短路径。
6. Kruskal 算法：用于求解最小生成树 (MST - Minimum Spanning Tree)。
7. Prim 算法：另一种求解最小生成树的方法。
8. 拓扑排序 (Topological Sorting)：适用于有向无环图 (DAG)，用于任务调度等应用。
9. Tarjan 算法：用于求解图中的强连通分量、割点、桥。