邻接矩阵存储图并深度优先搜索遍历-Toy模板网

这篇具有很好参考价值的文章主要介绍了邻接矩阵存储图并深度优先搜索遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

采用邻接矩阵形式存储图，对图进行优先深度搜索，并输出结果。

算法设计

用邻接矩阵存储图首先定义图的邻接矩阵存储结构，其中一维数组vertexs用来表示与顶点有关的信息，二维数组arcs用来表示图中顶点之间的关系。

之后要初始化邻接矩阵，初始化顶点个数以及边的个数，输入数据并且添加权值然后输出矩阵。

深度优先搜索然后遍历，最后输出搜索遍历后的顺序。

深度优先遍历类似于树的先根遍历，是树先根遍历的推广。深度优先遍历是个递归过程，所以这个算法可以用递归实现。从某个结点v出发，进行优先遍历图的算法采用递归的形式说明如下：（1）设置访问标识数组并初始化标识数组。

（2）若访问过顶点，则该标识设置为1，并输出当前顶点。

（3）若某个顶点没有被访问过，则继续进行遍历此顶点。

（4）继续找下一个邻接点，递归递归进行遍历，直到所有顶点都被访问。

设计的函数如下：

InitG()	初始化邻接矩阵
Init_Vertex()	初始化矩阵中的顶点个数
Init_Arc()	初始化矩阵中的边数
InSerG()	插入邻接矩阵中的数据
InWeight()	在矩阵中添加连接顶点之间的信息，即为图的权值
Print()	输出邻接矩阵
Init_DFS()	深度优先搜索函数
DFS()	深度优先遍历函数
main()	主函数用来测试该算法功能

源代码：

/************
date:2021-11-27
version:1.0
author:sy
Description:采用邻接矩阵存储图，进行图的深度优先搜索并输出结果 
**************/
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 100 
/* 邻接矩阵数据结构体 */
typedef struct {
	int vexnum,	arcnum;         //  图的顶点数和弧数 
	int vertexs[MAXNUM];       	//	存储顶点的一维数组 
	int arcs[MAXNUM][MAXNUM]; 	//	邻接矩阵
}graph,*Graph; 
typedef struct Arc{
	int v1;		    //	用来存放第一个顶点 
	int v2;	    	//	用来存放第二个顶点
	int weight;	    //	权值 
}*ArcType;
/* 初始化邻接矩阵 */ 
void InitG(Graph G,int Vertex)
{	
	G->arcnum = 0;			//	初始化为0条边 
	G->vexnum = Vertex;		//	初始化顶点数 
	int i,j;
	for(i=0;i<Vertex;i++)
	{
		for(j=0;j<Vertex;j++)
		{
			G->arcs[i][j] = 0;
		}
	} 
}
/* 初始化顶点个数 */
int Init_Vertex()
{
	int Vertex;
    printf("请输入顶点个数（回车键结束）: ");
	scanf("%d",&Vertex);
	return Vertex;
}
/* 初始化边的数量 */ 
int Init_Arc()
{
	int arc;
	printf("请输入边的数量（回车键结束）: ");
	scanf("%d",&arc);
	return arc;
} 
void InWeight(Graph G,ArcType T); 
/* 开始插入数据 */ 
void InSerG(Graph G,int edge,int V)
{
	int i,j;
	if(edge>0)         // 边数大于0的时候才插入数据 
	{
		printf("请输入顶点和权值(空格分隔，回车结束)\n");
		for(i=0;i<edge;i++)
		{		
			ArcType T;	// 分配内存，接受顶点v1,v2和权值	
			T = (ArcType)malloc(sizeof(struct Arc));	
			scanf("%d %d %d",&(T->v1),&(T->v2),&(T->weight));
			if(T->v1 ==T->v2)
			{
				printf("无向图邻接矩阵对角线为0,输入错误,结束运行\n");
				exit(-1); 
			}
			InWeight(G,T);
		}	
		printf("请输入要创建的顶点（空格隔开，回车结束）: \n");
		for(j=0;j<V;j++)
		{
			scanf("%d",&(G->vertexs[j]));
		}
	}else printf("输入的边数错误"); 
} 
/* 在矩阵中添加连接顶点之间的信息 ，即为图的权值*/
void InWeight(Graph G,ArcType T)
{
	G->arcs[T->v1][T->v2] = T->weight;
	G->arcs[T->v2][T->v1] = T->weight; 
} 
/* 输出邻接矩阵 */
void Print(Graph p,int Vertex)
{
	int i,j;
	for(i=0;i<Vertex;i++)
	{
		for(j=0;j<Vertex;j++)
		{
			printf("%4d",p->arcs[i][j]);	//	打印邻接矩阵 
		}	
			putchar('\n');
	}
}

int visited[MAXNUM];             //访问标识数组 
void DFS (Graph G,int v,int V);  //声明函数 
/* 深度优先搜索 */
void Init_DFS (Graph G,int V)
{
	int i;
	for(i=0;i<V;i++)      /*初始化标识数组，全为0*/ 
	{
		visited[i] = 0;
	}
	for(i=0;i<V ;i++)	   // 检查每一个顶点是否被遍历到 
	{
		if(!visited[i])	
			DFS (G,i,V);   // 开始深度遍历	
	} 
	putchar('\n');
}
/*深度优先遍历*/
void DFS (Graph G,int v,int V)
{
	int i;
	visited[v] = 1;	 
	printf("%d ",G->vertexs[v]);	//	输出当前顶点 
	for(i=0;i<V ;i++)
	{
		if(!visited[i] && G->arcs[v][i] != 0) //	如果当前顶点的邻近点存在，且没有遍历过 
		{									  //	则继续递归遍历 
		    DFS ( G,i,V );	                  //	递归遍历当前顶点的邻近点 
		}	
	} 
}
int main()
{
	int Vernum;
	int arc;
	Graph P;		//	邻接矩阵头节点指针 					
	Vernum = Init_Vertex();     /*创建邻接矩阵*/
	arc = Init_Arc();
    P = (Graph)malloc(sizeof(graph));	//分配存储空间 
	P->vexnum = Vernum;	            	//	记录顶点个数 
	P->arcnum = arc;	            	//	记录边的个数 
	InitG(P,Vernum);                	//	初始化邻接矩阵 
	InSerG(P,arc,Vernum);	    //	插入数据  
	
	printf("无向图邻接矩阵如下:");	
	printf("\n---------\n\n");
    Print(P,Vernum);
	printf("\n---------\n");
		
	printf("深度优先搜索遍历邻接矩阵结果为:\n");
	Init_DFS (P,Vernum);
	return 0;	
}