【算法导论】有向图的深度优先搜索遍历

在前面的文章中，我已经讨论了无向图的遍历，现在发现在有向图中，可能会发生无法遍历到所有节点的情况。因此在经历一次深度优先搜索遍历后，如果还存在未被搜索到的节点，则需要再从新的节点开始进行深度优先搜索遍历，直到访问完所有节点。

以下面的有向图为例：

如果从$a$开始进行深度优先搜索遍历，则会得到 $ a b c d h g f $后结束，因此我们还要 从未访问到的节点$e$进行第二次深度优先搜索遍历得到$e$.在前面的深度优先搜索的基础上，有向图的深度优先搜索程序实现如下：

#include<stdio.h>
#include<stdlib.h>
#define N 8 //顶点数

typedef struct node
{
	char vexs[N];//顶点数组
	int color[N];
	int arcs[N][N];//邻接矩阵
//	struct node *p;
}graph;


void DFS_direction(graph g,int i,int visited[N])
{
	printf("%c\n",g.vexs[i]);
	visited[i]=1;
	for(int j=0;j<N;j++)
		if(g.arcs[i][j]==1&&visited[j]==0)
			DFS_direction(g,j,visited);
}


void main()
{
	graph g;
	int v=0;
	int visited[N]={0};
	int visited1[N]={0};
	char vertex[N]={'A','B','C','D','E','F','G','H'};
	int matrix[N][N]={{0,1,0,0,0,0,0,0},
					  {0,0,1,0,0,1,0,0},
					  {0,0,0,1,0,0,1,0},
					  {0,0,1,0,0,0,0,1},
					  {1,0,0,0,0,1,0,0},
					  {0,0,0,0,0,0,1,0},
					  {0,0,0,0,0,1,0,1},
					  {0,0,0,0,0,0,0,1}};
	for(int i=0;i<N;i++)
	{
		g.vexs[i]=vertex[i];
		for(int j=0;j<N;j++)
			g.arcs[i][j]=matrix[i][j];
	}
	//printf("%d",g.arcs[7][5]);
	int d[N]={0};
	int f[N]={0};
	int num=0;
	//printf("图按照邻接矩阵存储时的深度优先搜索遍历：\n");
	while(num!=N)//当从某个节点无法一次搜索完所有节点时，从一个没有被访问过的节点开始
	{
		for(int j=0;j<N;j++)
			if(visited[j]==0)
				DFS_direction(g,j,visited);
		
		for(int k=0;k<N;k++)
			num=num+visited[k];//查看是否所有节点遍历到	
		
	}


}