算法第49天｜图论：基本概念、深搜理论基础、98.所有可达路径、广搜理论基础-EW帮帮网

基本概念

图的分类

有向图 and 无向图
度：

无向图：有几条边连接该结点
有向图：每个节点有出度和入度

连通性： 图中节点的连通情况
连通图：

无向图：任何两个节点都是可以到达的
有向图：任何两个节点都可以相互到达，称为强连通图
连通分量：
无向图：极大连通子图称为该图的一个连通分量
有向图：极大强连通子图称为该图的一个强连通分量

极大是指，最大的一个连通子图，换言之，再加入任何一个节点这个子图都不再连通。

图的构造

我们如何用代码来表示一个图呢？

一般使用邻接表、邻接矩阵或者用类来表示，主要是朴素存储、领接表和邻接矩阵。

朴素存储：是carl自创的名字，其实就是使用顶点来存储所有边。

邻接矩阵：从节点的角度来表示图，有多少节点就申请多大的二维数组。在这里插入图片描述

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

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

邻接表：从边的角度来表示图，使用数组+链表的方式来表示，有多少边才会申请对应大小的链表。
- 优：
  - 对于稀疏图的存储，只需要存储边，空间利用率高
  - 遍历节点连接情况相对容易
- 缺：
  - 检查任意两个节点间是否存在边，效率相对低，需要O(V)时间，V表示某节点连接其他节点的数量
  - 实现相对复杂，不易理解

图的遍历方式

深度优先搜索（dfs） & 广度优先搜索（bfs）

深搜理论基础

dfs与bfs区别

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

dfs搜索过程

关键点：

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

图的存储

邻接矩阵

使用二维数组来表示图结构。邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
因为节点标号是从1开始的，为了节点标号和下标对齐，申请n+1*n+1这么大的二维数组

vectoc<vector< int >>graph(n+1, vector<int>(n+1, 0));

输入m个边，构造方式如下：

while(m--){
	cin>>s>>t;
	graph[s][t] = 1;
}

邻接表

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

// 节点编号从1到n，所以申请 n+1 这么大的数组
vector<list<int>> graph(n + 1); // 邻接表，list为C++里的链表

输入m个边，构造方式如下：

while (m--) {
    cin >> s >> t;
    // 使用邻接表 ，表示 s -> t 是相连的
    graph[s].push_back(t);
}

98.所有可达路径

题目

思路与解法


#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> res;
vector<int> path;


void dfs(vector<vector<int>> graph, int start, int end){
    if(start == end){
        res.push_back(path);
        return;
    }

    for(int i=1;i<=graph.size()-1;i++){
        if(graph[start][i] == 1){
            path.push_back(i);
            dfs(graph, i, end);
            path.pop_back();
        }
    }

}

int main(){
    int N, M; // N:节点数，M：边数
    cin>>N>>M;

    vector<vector<int>> graph(N+1, vector<int>(N+1, 0));

    int m, n;

    for(int i=0;i<M;i++){
        cin>>m>>n;
        graph[m][n] = 1;
    }
    path.push_back(1);

    dfs(graph, 1, N);

    if(res.empty()) {
        cout<< -1 <<endl;
        return 0;
    };

    for(int i=0;i<res.size() - 1;i++){
        for(int j=0;j<res[i].size() - 1;j++){
            cout<< res[i][j] << " ";
        }
        cout<<res[i][res[i].size()-1]<<endl;
    }

    for(int i=0;i<res[res.size()-1].size() - 1;i++){
        cout<<res[res.size() - 1][i]<<" ";
    }
    cout<<res[res.size() - 1][res[res.size()-1].size() - 1];

}

广搜理论基础

广搜的搜索方式就适合于解决两个点之间的最短路径问题。
因为广搜是从起点触发，以起始点为中心一圈一圈进行搜索，一旦遇到终点，记录之前走过的节点就是一条最短路径。
当然，也有一些问题是广搜和深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

广搜的过程

代码模板

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; // 只要加入队列立刻标记，避免重复访问
            }
        }
    }

}

算法第49天｜图论：基本概念、深搜理论基础、98.所有可达路径、广搜理论基础