图论之dfs浅谈

什么是dfs？

dfs depth first search 深度优先搜索

字面意思理解 就是按照深度的方式进行搜索，有多深就先挖多深

简单讲就是按着一条线走到头。然后再回退走另一条线

show code

• 非递归版DFS（理解）

通过这种方式进行深入浅出，快速理解DFS在做什么

#include <iostream>
using namespace std;
int main(){
    int m, n;
    //还没写完
    return 0;
}

• 递归版DFS（必须掌握）

#include <iostream>
#include <stack>
using namespace std;
//使用邻接矩阵
const int N = 1e2+10;
int g[N][N];
//利用数组标记
bool vis[N]
int m, n;//m边数 n顶点数

void dfs(int p){
	cout << p << " ";//输出
    vis[p] = 1;//搜索即标记
    for(int i =1;i<=n;i++){
        if(!vis[i]&&g[p][i]==1){//找该点所有 未被标记 的 邻接点（二者要同时满足）
            dfs(i);//递归调用
        }
    }
}

int main(){
    int s;//起点
    cin >> m >> n >> s;
    
    for(int i=1;i<=m;i++){
        int u,v;
        g[u][v] = g[v][u] = 1;
    }
    dfs(s); //从起点开始调用dfs
}

······未完待续