图的深度优先遍历算法(利用邻接矩阵))

图的深度优先遍历算法

#define N 9 //图的顶点数

char DOT[N]={'A','B','C','D','E','F','G','H','I'};//存放顶点信息的数组
char OUT[N+1]; //存放被访问顶点信息顺序的数组,OUT[0]保存已访问顶点总数
char visited[N]; //存放顶点被访问标志

//邻接矩阵:
int GRA[N][N] ={{0,1,0,0,0,0,0,1,0},
{1,0,1,0,0,0,0,0,1},
{0,1,0,1,0,1,0,0,0},
{0,0,1,0,1,0,0,0,0},
{0,0,0,1,0,1,1,0,0},
{0,0,1,0,1,0,1,0,1},
{0,0,0,0,1,1,0,1,0},
{1,0,0,0,0,0,1,0,1},
{0,1,0,0,0,1,0,1,0}};

void DFS (int i) reentrant //从顶点i出发，深度优先搜索遍历连通图
{
int j;
OUT [++OUT[0]] = DOT[i];//先访问该顶点（输出该顶点信息）
visited[i] = 1 ; //作已访问标记
for (j=0;j<N;j++) //从顶点i出发，扫描所有相邻顶点
if ( GRA[i][j] == 1 && !visited[j] ) //如果未访问过
DFS (j) ; //从顶点j出发，按深度优先继续搜索
}

//出发点序号为0时的遍历顺序：ABCDEFGHI
//出发点序号为1时的遍历顺序：BAHGEDCFI
//出发点序号为2时的遍历顺序：CBAHGEDFI
//出发点序号为3时的遍历顺序：DCBAHGEFI
//出发点序号为4时的遍历顺序：EDCBAHGFI
//出发点序号为5时的遍历顺序：FCBAHGEDI
//出发点序号为6时的遍历顺序：GEDBCAHIF
//出发点序号为7时的遍历顺序：HABCDEFGI
//出发点序号为8时的遍历顺序：IBAHGEDCF

main ( )
{
int i,j;
for (i=0;i<N;i++) {
OUT[
0]=0; //初始化已访问顶点数
for (j=0;j<N;j++) visited[j]=0;//初始化访问标志
DFS (i) ; //从序号为i的顶点出发进行深度优先遍历
}
while (1) ; //在这一行设置断点,中止程序运行,以便观察程序运行的结果
}