连通图的DFS算法实现讨论

(1) DFS(v)的第一句话为“==访问定点v==”
- 即函数visit(v)的实现，大多场合是输出顶点的值，也可根据具体问题的需要来设计。
(2)DFS(v)的第二句话为“==依次从顶点v的未被访问的邻接点出发进行深度遍历==”。这涉及到以下内容：
- 顶点是否被访问的标识：设置访问标志数组==visited[n+1]==，值为True表示已经访问，False表示未访问。假设图有n个顶点，其中visited[0]单元不用，使数组下标与顶点编号一致，都从1开始。
- 顶点v的各邻接点的求解：
  - 一个顶点的邻接点的求解取决于图的存储结构。
  - 用邻接矩阵存储图时，顶点vi的各邻接点在邻接矩阵的第i行中，因此可通过该行中依次搜索非∞元素（或非0元素）来搜索所有邻接点；
  - 用邻接表存储时，该顶点的邻接点全部在邻接表的第i个链表中，因此可通过依次取该链表中结点来实现所有邻接点的求解。
  - 为使算法不受图的具体存储结构的影响，用时也为算法更清晰，下面的讨论更倾向于用如下两个不依赖于特定存储结构的邻接点函数来实现这一求解：
    - firstAdj(G,v)：返回图G中顶点v的第一个邻接点。若不存在邻接点（编号），则返回0；
    - nextAdj(G,v,w)：返回图G中顶点v的邻接点中处于w之后的那个邻接点。若不存在这样的邻接点（编号），则返回0；
    - 通过这两个函数，可依次求出一个顶点的所有邻接点。
- 从邻接点出发深度遍历的实现：可通过调用DFS算法来实现，也就是说，DFS算法是一个递归算法。

连通图的算法实现描述

// An highlighted block
void DFS(Graph G,int v)
{    //从编号v的顶点开始对图G进行深度优先搜索遍历
	int w;
	visit(G,v);   //访问顶点v
	visited[v] = TRUE;  //设置v已经访问标志
	w = firstAdj(G,v);  //求v的第一个邻接点，返回其编号给w
	while(w!=0)
	{
		if(!visited[w])
			DFS(G,w);   //对v的邻接点w递归DFS
		w = nextAdj(G,v,w); //找v的w后的下一个邻接点
	}
}

(1) 基于邻接矩阵的实现

// An highlighted block
void DFS(Graph G,int v)
{
	visit(G,v);  //访问顶点v，如：cout<<Data[v]<<"\t"
	visited[v] = TRUE; //标记v已经访问
	for(int w=1; w<=G.VerNum; w++)  //循环找v的邻接点
	{     //w为v的邻接点，且未被访问
		if((G.AdjMatrix[v][w]>=1) && (G.AdjMatrix[v][w]<INF) && (!visited[w]))  //考虑到图和网的通用性
		{
			DFS(G,w);
		}
	}
}

(2) 基于邻接表的实现

// An highlighted block
void DFS(Graph G,int v)
{
	visit(v); //访问顶点v,如:cout<<Data[v]<<"\t"
	visited[v] = TRUE; //标记编号为v的顶点已经访问
	EdgeNode *p;
	p=G.VerList[v].firstEdge;   //p初始化为顶点v的边链表的头指针
	while(p)
	{
		if(!visited[p->adjVer])  //p->adjVer为v的邻接点编号
			DFS(G,p->adjVer);  //递归深度遍历顶点v的邻接点
		p = p->next;  //p指向v的下一个邻接点
	}
}

一般图的（通用）DFS算法

// An highlighted block
void DFSTraverse(Graph G,int v)
{
	int i;   //顶点编号
	for(i = 1 ; i <= G.VerNum; i++)  //初始化访问标记数组
	{
		visited[i] = false;
	}
	DFS(G,v);
	for(i = 1 ; i <= G.VerNum ; i++)
	{  //循环遍历图中所有其他的连通分量
		if(!visited[i])
		{
			DFS(G,i); //遍历i所在的连通分量
		}
	}
}

深度优先搜索遍历算法

连通图的DFS算法实现讨论

连通图的算法实现描述

一般图的（通用）DFS算法