吃的网站要怎么做/电商平台排行榜前十名

dfs是以深度为第一关键词
每次都沿着路径到不能再前进时
才退回到最近的岔道口

沿着一条路径直到无法继续前进
才退回到路径上里当前顶点最近的&还存在未访问的岔道口
并前往访问那些未访问的分支顶点
直到遍历完这个图

dfs的具体实现
2个概念：
1）连通分量：

2个顶点联通：2个顶点之间可以互相到达(无向图中)
====》
联通图：图G(V,E)的任意2个顶点都联通（无向图）

连通图的连通分量一个，
但是非联通图的联通分量有多个

连通分量：极大的联通子图
link

求图的连通分量的目的，
是为了确定从图中的一个顶点是否能到达图中的另一个顶点，
也就是说， 图中任意两个顶点之间是否有路径可达。

对于连通图，
从图中任一顶点出发遍历图，
可以访问到图的所有顶点，
即连通图中任意两顶点间都是有路径可达的。

2）强连通分量：
2个顶点强连通：2个顶点可以各自通过一条有向路径到达另一个顶点（有向图）

构成一个单向循环

强连通图：图G(V,E)的任意2个顶点都强连通（有向图）
强连通分量：极大强连通子图

---

我们把联通分量和强连通分量都叫做：连通块
我们遍历整个图，就需要对所有的连通块分别进行遍历
=====》
dfs遍历图：
1.把经过的顶点设置为已经被访问
2.在下次递归碰到这个顶点时就不再去处理
----直到整个图的顶点都被标记为已经被访问

沿着一条路径直到无法继续前进
才退回到路径上里当前顶点最近的&还存在未访问的岔道口
并前往访问那些未访问的分支顶点
直到遍历完这个图

如果给定的图是一个连通图，则只需要一次dfs就能遍历完图

邻接表版：dfs

const int MAXV=1000;
const int INF=1000000000;vector<int> Adj[MAXV];
int n;//顶点数，MAXV为最大顶点数
bool vis[MAXV]={false};//如果顶点已经被访问，则vis[i]==true，初值为falsevoid dfs(int index,int depth){//index为当前访问的顶点编号vis[index]=true;///让我想到了------childs[depth]++;//求树的每层节点数//------------操作-----------//for(int j=0;j<Adj[index].size();j++){int v=Adj[index][j];if(vis[Adj[index][j]]==false){dfs(Adj[index][j],depth+1);}}
}void dfsTravel(){//遍历图G
//把每个顶点当作根节点来遍历，来寻找连通块（标记访问的节点，下次不访问）for(int i=0;i<n;i++){if(vis[i]==0)dfs(i,1);//访问顶点i和i所在的连通块}
}