算法笔记-第十章-图的遍历（未处理完-11.22日）

本文主要是介绍算法笔记-第十章-图的遍历（未处理完-11.22日），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

图遍历的知识点一

关于深度和广度优先遍历的基础知识 ：

大佬讲解

大佬讲解一

大佬讲解二

图遍历知识二

连通分量

算法笔记-352

DFS的具体实现
两个概念：
连通分量，强连通分量（有向路径）

实现DFS的模板思路

DFS(u)//访问顶点u
{vis[u] = true;for (从u出发能到达的所有顶点){if vis[v] == false//如果v未被访问  {DFS(v);//递归访问v  }}DFStrave(G)//遍历图G  {for (G的所有顶点u)//对G的所有顶点u  {if (vis[u] == false)//如果u未被访问  DFS(u);//访问u所在的连通块  }}
}

邻接矩阵版本

//邻接矩阵版本
const int N = 1001, INF = 1000001;
int n, G[N][N];
bool vis[N] = { false };
void DFS(int u, int depth)
{vis[u] = true;//需要对u进行一些操作，从u出发//能到达的 分支进行枚举for (int v = 0; v < n; v++){if (vis[v] == false && G[u][v] != INF){DFS(v, depth + 1);  }}}
void DFStrave()//遍历图  
{for (int u = 0; u < N; u++)  {if (vis[u] == false)  {DFS(u, 1);  }}
}

邻接表版本

//邻接表版
vector<int> adj[N];
int n;
bool vis[N] = { false };
void DFS(int u, int depth)
{vis[u] = true;for (int i = 0; i < adj[u].size(); i++)//从u出发可以到达的所有顶点{int v = adj[u][i];if (vis[v] == false){DFS(v, depth + 1);  }}}
void DFStrave()//遍历图  
{for (int u = 0; u < N; u++)  {if (vis[u] == false)  {DFS(u, 1);  }}
}

无向图的连通块

这篇关于算法笔记-第十章-图的遍历（未处理完-11.22日）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---