当前位置：首页 > article >正文

算法日记 41 day 图论

article 2025/3/4 17:09:41

大章节来了，图论部分。

先来认识认识图论基础。

图：

包括无向图，有向图，无向加权图，有向加权图。就和他的名字一样，

无向图是指图中边没有方向：

加权有向图，就是图中边是有权值的，例如：

图的特性：

度：几条边指向该节点，该节点就有几度

出度：从该节点出发的边的个数。

入度：指向该节点边的个数。

连通性：

表示节点的连通情况，我们称之为连通性

在无向图中，任何两个节点都是可以到达的，我们称之为连通图

如果有节点不能到达其他节点，则为非连通图。

强连通图

在有向图中，任何两个节点是可以相互到达的，我们称之为强连通图。

连通分量

在无向图中的极大连通子图称之为该图的一个连通分量。

该无向图中节点1、节点2、节点5 构成的子图就是该无向图中的一个连通分量，该子图所有节点都是相互可达到的。

同理，节点3、节点4、节点6 构成的子图也是该无向图中的一个连通分量。

那么无向图中节点3 、节点4 构成的子图是该无向图的联通分量吗？

不是！

因为必须是极大联通子图才能是连通分量，所以必须是节点3、节点4、节点6 构成的子图才是连通分量。

强连通分量

在有向图中极大强连通子图称之为该图的强连通分量。

图的构造：

一般使用邻接表、邻接矩阵或者用类来表示。

主要是朴素存储、邻接表和邻接矩阵。

邻接矩阵

邻接矩阵 使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

例如： grid[2][5] = 6，表示节点 2 连接节点5 为有向图，节点2 指向节点5，边的权值为6。

如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与节点5 相互连通，权值为6。

这种表达方式（邻接矩阵）在边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。

而且在寻找节点连接情况的时候，需要遍历整个矩阵，即 n * n 的时间复杂度，同样造成时间浪费。

邻接矩阵的优点：

表达方式简单，易于理解
检查任意两个顶点间是否存在边的操作非常快
适合稠密图，在边数接近顶点数平方的图中，邻接矩阵是一种空间效率较高的表示方法。

缺点：

遇到稀疏图，会导致申请过大的二维数组造成空间浪费且遍历边的时候需要遍历整个n * n矩阵，造成时间浪费

邻接表

邻接表 使用数组 + 链表的方式来表示。邻接表是从边的数量来表示图，有多少边才会申请对应大小的链表。

这里表达的图是：

节点1 指向节点3 和节点5
节点2 指向节点4、节点3、节点5
节点3 指向节点4
节点4指向节点1

有多少边邻接表才会申请多少个对应的链表节点。

从图中可以直观看出使用数组 + 链表来表达边的连接情况。

邻接表的优点：

对于稀疏图的存储，只需要存储边，空间利用率高
遍历节点连接情况相对容易

缺点：

检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
实现相对复杂，不易理解

遍历方式：

深度优先（DFS）和广度优先（BFS）

深度优先搜索

dfs是可一个方向去搜，不到黄河不回头，直到遇到绝境了，搜不下去了，再换方向（换方向的过程就涉及到了回溯）。
bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程。

那么深搜的关键在于：

搜索方向，是认准一个方向搜，直到碰壁之后再换方向
换方向是撤销原路径，改为节点链接的下一个路径，回溯的过程。

在写代码的时候就需要注意搜索的回溯过程了，这一部分和之前的二叉树回溯和数组回溯的方法也是一样的。

回溯三部曲：确定递归的参数，确定终止条件，处理遍历的结点。

来看一道题目：

题目:所有可达路径

98. 所有可达路径 (kamacoder.com)

题目描述

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个函数，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。

输入描述

第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边

后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输出描述

输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。

注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 `1 3 5`,而不是 `1 3 5 `， 5后面没有空格！

题目分析：

//邻接矩阵写法
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径

void dfs (const vector<vector<int>>& graph, int x, int n) {
    // 当前遍历的节点x 到达节点n 
    if (x == n) { // 找到符合条件的一条路径
        result.push_back(path);
        return;
    }
    for (int i = 1; i <= n; i++) { // 遍历节点x链接的所有节点
        if (graph[x][i] == 1) { // 找到 x链接的节点
            path.push_back(i); // 遍历到的节点加入到路径中来
            dfs(graph, i, n); // 进入下一层递归
            path.pop_back(); // 回溯，撤销本节点
        }
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m;

    // 节点编号从1到n，所以申请 n+1 这么大的数组
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));

    while (m--) {
        cin >> s >> t;
        // 使用邻接矩阵 表示无线图，1 表示 s 与 t 是相连的
        graph[s][t] = 1;
    }

    path.push_back(1); // 无论什么路径已经是从0节点出发
    dfs(graph, 1, n); // 开始遍历

    // 输出结果
    if (result.size() == 0) cout << -1 << endl;
    for (const vector<int> &pa : result) {
        for (int i = 0; i < pa.size() - 1; i++) {
            cout << pa[i] << " ";
        }
        cout << pa[pa.size() - 1]  << endl;
    }
}




//邻接表写法
#include <iostream>
#include <vector>
#include <list>
using namespace std;

vector<vector<int>> result; // 收集符合条件的路径
vector<int> path; // 1节点到终点的路径

void dfs (const vector<list<int>>& graph, int x, int n) {

    if (x == n) { // 找到符合条件的一条路径
        result.push_back(path);
        return;
    }
    for (int i : graph[x]) { // 找到 x指向的节点
        path.push_back(i); // 遍历到的节点加入到路径中来
        dfs(graph, i, n); // 进入下一层递归
        path.pop_back(); // 回溯，撤销本节点
    }
}

int main() {
    int n, m, s, t;
    cin >> n >> m;

    // 节点编号从1到n，所以申请 n+1 这么大的数组
    vector<list<int>> graph(n + 1); // 邻接表
    while (m--) {
        cin >> s >> t;
        // 使用邻接表 ，表示 s -> t 是相连的
        graph[s].push_back(t);

    }

    path.push_back(1); // 无论什么路径已经是从0节点出发
    dfs(graph, 1, n); // 开始遍历

    // 输出结果
    if (result.size() == 0) cout << -1 << endl;
    for (const vector<int> &pa : result) {
        for (int i = 0; i < pa.size() - 1; i++) {
            cout << pa[i] << " ";
        }
        cout << pa[pa.size() - 1]  << endl;
    }
}

题目：所有可能路径

797. 所有可能的路径 - 力扣（LeetCode）

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

题目分析：

这里题目中给出的是邻接表，注意写法即可

public class Solution {
    IList<IList<int>> res=new List<IList<int>>();
    IList<int> path=new List<int>();
    public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
        path.Add(0);//0是起点
        DfS(graph,0,graph.Length-1);
        return res;
    }
    public void DfS(int[][] graph,int x,int n){
        if(x==n){
            res.Add(new List<int>(path));
            return;
        }
        for(int i=0;i<graph[x].Length;i++){
            path.Add(graph[x][i]);
            DfS(graph,graph[x][i],n);
            path.RemoveAt(path.Count-1);
        }
    }
}

对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。

代码随想录 (programmercarl.com)