C语言 图的深度优先遍历_图的深度优先遍历头歌

实验内容:

（1）实现图的邻接矩阵表示，并创建图；

（2）对邻接矩阵表示的图实现深度优先遍历；

深度优先遍历的基本思想：

① 选择一个起始点出发，并访问之；

②一次从起始点的未访问过的邻接点出发，深度遍历图，直到图中与起始点有路径相通的顶点都被访问过为止；

③如此时图中尚有顶点未被访问过，则另选图中一个未访问过的顶点作起始点， 重复上述过程，直到所有顶点被访问过为止。

C语言代码如下：

#include<stdio.h>
#define MaxSize 100
typedef struct
{
	int n,e;							//顶点数、边数 
	int link[MaxSize][MaxSize];			//两顶点之间连接 
	char vexs[MaxSize]; 				//顶点的名称 
}MGraph;
 
 
void CreateGraph(MGraph *G)
{
	int i,j,k;
	printf("请输入顶点数和边数：");
	scanf("%d%d",&(G->n),&(G->e));
	for(i=0;i<G->n;i++)					 //初始化邻接矩阵 ，全部置零 
	{
		for(j=0;j<G->n;j++)
		{
			G->link[i][j]=0;
		}
	}
	 
	printf("\n请输入每个顶点的名称：\n");
	fflush(stdin);
	for(i=0;i<G->n;i++)
	{
		scanf("%c",&G->vexs[i]); 
		fflush(stdin);					//清除缓冲区 
	}	
	printf("\n请输入边的信息：");
	for(k=0;k<G->e;k++)                 //输入邻接矩阵 
	{
		scanf("%d,%d",&i,&j);
		G->link[i][j]=1;
	}
	printf("输出的邻接矩阵如下："); 
	for(i=0;i<G->n;i++)					 //打印邻接矩阵 
	{
		printf("\n"); 
		for(j=0;j<G->n;j++)
			printf("%8d",G->link[i][j]) ; 
	}
}
int visited[MaxSize];
void dfs(MGraph *G,int i)				 
{
	int j;
	printf("%c",G->vexs[i]);
	visited[i]=1;
	for(j=0;j<G->n;j++)
	{
		if(G->link[i][j]==1&&visited[j]==0)
		{
			dfs(G,j);		
		}
	}
}
void DFSTraverse(MGraph *G) 
{
	int i;
	for(i=0;i<G->n;i++)
	{
		visited[i]=0;  				    //全部标记为未访问 
	} 
	for(i=0;i<G->n;i++)
	{
		if(visited[i]==0)
		{
			dfs(G,i);
		}
	} 
}
int main()
{
	MGraph G;
	CreateGraph(&G);
	printf("\n\n深度优先遍历序列：");
	DFSTraverse(&G);
	return 0; 
}