图论基础：理论概念、深度搜索与广度搜索详解

图论基础：理论概念、深度搜索与广度搜索详解

引用

CSDN

1.

https://blog.csdn.net/m0_62572567/article/details/146013842

图论理论基础

• 图的基本概念
• 节点+多个节点的连线（Node + Edge）
• 种类：有向图&无向图
• 度（degree）：有几条边连接该节点，该节点就有几度。
• 出度：从该节点出发的边的个数
• 入度：指向该节点边的个数。
• 连通性
• 在图中各节点的连通情况，我们称之为连通性。
• 连通图：在无向图中，任何两个节点都是可以到达的，我们称之为连通图
• 强连通图：在有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图
• 连通分量：在无向图中的极大连通子图称之为该图的一个连通分量。

图的构造

• 邻接矩阵

• 优点：

• 表达方式简单，易于理解

• 检查任意两个顶点间是否存在边的操作非常快

• 适合稠密图

• 缺点：遇到稀疏图会导致申请过大的二维数组造成空间浪费

• 邻接表

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

• 构造：
  

• 优点：

• 对于稀疏图的存储，只需要存储边，空间利用率高

• 遍历节点连接状况相对容易

• 缺点：

• 检查两个任意节点间是否存在边，效率相对低，需要O（V）时间，V表示某节点连接其他节点的数量

• 实现相对复杂，不易理解

图的遍历方式

• dfs

• 概念：沿着一个方向不停的搜，涉及回溯

• 代码框架---回溯方式

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}  

• bfs

• 概念：把本节点所连接的所有节点遍历一遍，广度优先

• 适合于解决两个点之间的最短路径问题

• 代码框架：我们仅仅需要一个容器，能保存我们要遍历过的元素就可以

• 用队列：每一圈都是一个方向去转，例如统一顺时针或者逆时针。

• 用栈：第一圈顺时针遍历，第二圈逆时针遍历，第三圈有顺时针遍历。

• 数组

int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图，也就是一个二维数组
// visited标记访问过的节点，不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
    queue<pair<int, int>> que; // 定义队列
    que.push({x, y}); // 起始节点加入队列
    visited[x][y] = true; // 只要加入队列，立刻标记为访问过的节点
    while(!que.empty()) { // 开始遍历队列里的元素
        pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
        int curx = cur.first;
        int cury = cur.second; // 当前节点坐标
        for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
            if (!visited[nextx][nexty]) { // 如果节点没被访问过
                que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }
}