图的邻接矩阵存储，深度优先遍历（C语言）_邻接矩阵存储图的深度优先遍历

内容：
           采用邻接矩阵存储图，进行图的深度优先搜索并输出结果。

1.算法分析：

       整个程序分为两部分，第一部分为邻接矩阵存储图，第二部分为图的优先搜索。将两个部分的算法做一个简单的分析即可。

       第一部分，邻接矩阵存储图，因为顶点和顶点之间的关系直接合在一起存储比较困难，所以我们可以使用一维数组来存储顶点信息，用二维数组来存储边的信息。假设图G=(V,E)有n个确定的顶点，即V={V0,V1,…,V(n-1)}，则表示G中各顶点相邻关系为一个n*n的矩阵，矩阵元素为：

                                      

       这就是邻接矩阵，无向图存储于数组之后每个顶点的存储位置就确定了。若arcs[j][j]=1，则说明顶点vi，vj之间有一条边。arcs[i][j]=0，则说明顶点vi，vj之间没有边。所以，无向图的邻接矩阵是对称的，顶点vi的度就是第i行的元素之和，比如v0的度为2，如果要找顶点vi的所有邻接矩阵点，查找第i行值为1的矩阵元，其所在列的序号即为其邻接点的序号。有向图的顶点存储于数组之后每个顶点的存储位置就确定了。若arcs[i][j]=1,则说明顶点vi，vj之间有一条弧；若arcs[i][j]=0,则说明顶点vi，vj之间没有弧。有向图的邻接矩阵不一定是对称的。在有向图中判断顶点vi到vj是否有弧，只要判断arcs[i][j]是否为等于1。如果要找顶点vi的所有邻接点，查找第i行值为1的矩阵元，其所在的序号即为其邻接点的序号。

       第二部分即为树的深度优先搜索遍历。其实树的深度优先搜索遍历就相当于树的先根遍历，是树的先根遍历的推广。深度优先遍历的遍历过程如下：

      (1)将图中所有顶点做“未访问过”标记。

      (2)任选图中一个未被访问过的顶点v作为遍历起点。

      (3)访问v结点，然后深度优先访问v的第一个未被访问的邻接点w1.

      (4)再从w1出发深度优先访问w1的第一个未被访问的邻接点w2……如此下去，直到到达一个所有邻接点都被访问过的顶点为止。

      (5)然后依次退回，查找前一结点wi-1是否还有未被访问的结点，如果存在尚未被访问的邻接点，并从该结点出发按深度优先的规则访问。如果结点wi-1不存在尚未被访问的邻接点，则再后退一步，直到找到被访问的邻接点的顶点。

       (6)重复上述过程，直到图中所有与v有路径相连的顶点都被访问过。

       (7)若此时图中还有顶点未被访问，则转(2);否则，遍历结束。

       由于在这种遍历过程中，尽可能地沿“前进”的方向遍历，所以称之为深度优先遍历，显然这个算法可用递归实现。从某个结点v出发进行深度优先遍历图的算法采用递归的形式说明如下：

      (1)访问结点v。

      (2)找到v的第一个邻接点w。

      (3)如果邻接点w存在且未被访问，则从w出发深度优先遍历图；否则结束

      (4)找顶点v关于w的下一个邻接点。

       综上，我们设计两个函数实现，create_Graph实现无向图邻接矩阵的建立。DFStraverse实现深度优先遍历。

2.概要设计：

                     使用C语言，设计了以下函数：

3.程序运行流程图

 4.测试样例：

 

5.源代码：

#include<stdio.h>
#include<stdlib.h>
//邻接矩阵结构
typedef char VertexType;
typedef int EdgeType;
#define MAX 10
#define INFINITY 65535
#define TRUE 1
#define FALSE 0
typedef int Boole;  
Boole visited[MAX];    //访问标志数组 
typedef struct
{
	VertexType vexs[MAX];   //顶点表 
	EdgeType arc[MAX][MAX];   //邻接矩阵 可看作边表   
	int numVertexes,numEdges;
	int GraphType;  //图的类型  无向0,有向1	
}MGraph;
//构造图   有向图和无向图 
void create(MGraph *G)
{
	int i,j,k,w;
	printf("请输入顶点数和边数:\n");
	scanf("%d%d",&G->numVertexes,&G->numEdges);
	fflush(stdin);
	for(i=0;i<G->numVertexes;i++)     //建立顶点表
	{ 
		printf("\n第%d个顶点",i+1);
		scanf("%c",&G->vexs[i]);
		getchar();
	}
	for(i=0;i<G->numVertexes;i++)   //矩阵初始化 
		for(j=0;j<G->numVertexes;j++)
			G->arc[i][j]=INFINITY;
			
	for(k=0;k<G->numEdges;k++)
	{
		printf("输入边（Vi,Vj）的上下标i,j和权w(空格隔开)：");
		scanf("%d%d%d",&i,&j,&w);
		G->arc[i][j]=w;
		if(G->GraphType==0)      //此时为无向图   有向图与无向的区别就只是这一行代码的有无 
		G->arc[j][i]=G->arc[i][j];
	}			 
}
void Output(MGraph *G)     //输出邻接矩阵 
{
	int i,j,count=0;
	for(i=0;i<G->numVertexes;i++)
		printf("\t%c",G->vexs[i]);
	printf("\n");
	for(i=0;i<G->numVertexes;i++)
	{
		printf("%4c",G->vexs[i]);
		for(j=0;j<G->numVertexes;j++)
		{	
				printf("\t%d",G->arc[i][j]);
				count++;
				if(count%G->numVertexes==0)
				printf("\n");	
		} 
    }	 
 } 
/*深度优先遍历*/
//深度优先递归算法
void DFS(MGraph G,int i)
{
	int j;
	visited[i]=TRUE;   //被访问的标记 
	printf("%c->",G.vexs[i]);
	for(j=0;j<G.numVertexes;j++)
	{
		if(G.arc[i][j]==1&&!visited[j])   //边(i,j)存在且j顶点未被访问，递归 
			DFS(G,j);
	} 
}
//深度优先遍历
void DFStraverse(MGraph G)
{
	
	int i;
	for(i=0;i<G.numVertexes;i++)
		visited[i]=FALSE;
	for(i=0;i<G.numVertexes;i++)
			if(!visited[i])
				DFS(G,i);		
				
}
int main()
{
	MGraph G;
	int i,j;
	printf("输入生成图的类型(无向图0/有向图1)：");
	scanf("%d",&G.GraphType);
	create(&G);	
	printf("邻接矩阵数据如下：\n");
	Output(&G);
	printf("\n");
	DFStraverse(G);
	printf("\n图遍历完毕");
	return 0;	 
}

6.总结：

       如何建立邻接矩阵的表示过程和算法，重点是更加细致的学习了深度优先遍历的算法以及简单的实现，深度优先遍历的过程过程实质上也用到了递归算法。可见递归算法应用的广泛程度。