数据结构 图邻接矩阵的深度优先遍历 C语言_给定如下图,用邻接矩阵实现该图的深度优先搜索遍历。 图片1.png

 一、图的结构体定义

1、顶点数量

2、边的数量

3、邻接矩阵（数组表示）

4、顶点数组

5、图的类型（有向图或无向图）

typedef struct GNode
{
    int nv;
    int ne;
    char v[MAX_VNUM];
    int G[MAX_VNUM][MAX_VNUM];
    int GraphType;
}

二、判断是无向图还是有向图

       输入0或者1，在主体函数判别即可。

三、图的创建

1、分别初始化顶点数量、边的数量-----输入

2、顶点集合，定义,输入每个顶点名称

3、邻接矩阵——先初始化为全为0，即没有边与任何顶点相连

4、输入邻接矩阵具体数据，有多少条边则输入几次：分别输入边的两个顶点和权重（这里不是带权邻接矩阵，输入边数，即1）

        无向图：对应G[v1][v2]=G[v2][v1]=1;

        有向图：对应G[V1][V2]=1;

void GreatGraph(GNode *G)
{
    printf("请输入顶点数和边数:");
    scanf("%d%d",&G->nv,&G->ne);//顶点数量、边的数量
 
    int i,j,w;
 
    for(i=0;i<G->nv;i++)//顶点集合
    {
        printf("第%d个顶点为：",i);
        scanf("%c",&G->v[i]);
        getchar();
    }
 
    for(i=0;i<G->nv;i++)
        for(j=0;j<G->nv;j++)
            G->G[i][j]==0;//初始化矩阵每一项为0
 
    int v1,v2,w1;
    for(w=0;w<G->ne;w++)//for循环，输入数据
    {
        printf("请输入两顶点及边数");
        scanf("%d%d%d",v1,v2,w1);
        if(G->GraphType==0)
        {  
            G->G[v1][v2]=w1;  
            G->G[v2][v1]=w1;
        }
        else
        {
             G->G[v1][v2]=w1;
        }
    }
    
}

四、邻接矩阵的输出

void out(GNode G)
{
	
	int i,j;
	for(i=0;i<G.nv;i++)
	{
		for(j=0;j<G.nv;j++)
		{
			printf("%d	",G.G[i][j]);
			if((j+1)%(G.nv)==0)
				printf("\n");
 		}
	}
}

五、深度优先遍历

1、定义一个visit数组，没有遍历的为0，已经遍历的为1，以确保遍历不重复，定义在开头

int visit[MAX_VNUM];

2、设置所有顶点为0

3、从第0个开始，到第“边数最大数”，横向依次“遍历”邻接矩阵，如下：

              0:  ——————————————————————————>

              1:  ——————————————————————————>

              3:  ——————————————————————————>

              ......

如果矩阵数据为1，下一个输出的就是这个列数：1说明这两个顶点相连，这个顶点就是深度的下一个所指；

        此时，这个顶点所在的行，再次横向遍历，递归循环

此板块分成两个部分：

第一个部分为初始化为0，然后从第0个顶点开始看，如果为0则进行深度遍历，再第二个、第三个......

第二个部分就是深度遍历的主要板块：先把已经遍历了的改为1，输出这个顶点，再看这个顶点与哪一个顶点相连而且之前没有遍历过，递归循环。

void DFS(GNode G,int v)
{
    visit[v]=1;
    printf("%c->",G.v[v];
    for(int j=0;j<G.nv;j++)
    {
        if(!visit[j]&&G.G[v][j]==1)
        DFS(G,j);
    }
}
 
 
 
void TDFS(GNode G)
{
    for(int i=0;i<G.nv;i++)
    {
        visit[i]=0;
    }
    for(int v=0;v<G.nv;v++)
    {
        if(visit[v]=0)
            GFS(G,v);
    }
}

        

源代码完整版：

#define MAX_VNUM 100
#include<stdio.h> 
#include<stdlib.h> 
 
int visit[MAX_VNUM];
 
typedef struct GNode
{
	char v[MAX_VNUM];
	int nv;//顶点数 
	int ne;//边数
	int G[MAX_VNUM][MAX_VNUM] ;
	int GraphType;
}GNode;
 
void GreatGraph(GNode *G)
{
	printf("请输入顶点数和边数：");
	scanf("%d",&G->nv);
	scanf("%d",&G->ne);//注意%d后面不要加\n，会出bug(>^ < )
	fflush(stdin);
	for(int i=0;i<G->nv;i++)
	{
		printf("请输入第%d个顶点:",i);
		scanf("%c",&G->v[i]);
		getchar();
	}
	for(int v=0;v<G->nv;v++)
		for(int w=0;w<G->nv;w++)
			G->G[v][w]=0;
		
	
	int v1,v2,w1;
	for(int i=0;i<G->ne;i++)
	{
		if(G->GraphType==1)//有向图 
		{
			printf("请输入V1和V2和边数："); 
			scanf("%d%d%d",&v1,&v2,&w1);
			G->G[v1][v2]=w1;
		}
		else
		{
			printf("请输入V1和V2和边数："); 
			scanf("%d%d%d",&v1,&v2,&w1);
			G->G[v1][v2]=w1;
			G->G[v2][v1]=w1;
		}
	}
	
}
 
//用邻接矩阵实现DFS
 
void out(GNode G)
{
	
	int i,j;
	for(i=0;i<G.nv;i++)
	{
		for(j=0;j<G.nv;j++)
		{
			printf("%d	",G.G[i][j]);
			if((j+1)%(G.nv)==0)
				printf("\n");
 		}
	}
}
 
void DFS(GNode G,int i)//深度遍历 
{
	int j;
	visit[i]=1;//遍历了，变为1 
	printf("%c-> ",G.v[i]);
	for(j=0;j<G.nv;j++)
	{
		if(!visit[i]&&G.G[i][i]==1)
		DFS(G,j);//递归调用 
	}
}
 
void TraverseGraph(GNode G)
{
	int v;
	for(v=0;v<G.nv;v++)
	{
		visit[v]=0;//设置初始值都为0 
	}
	for(v=0;v<G.nv;v++)
	{
		if(!visit[v]) 
		DFS(G,v);
	}
}
 
 
int main()
{
	GNode G;
	printf("请输入图的类型，有向为1，无向为0:");
	scanf("%d",&G.GraphType) ;
	GreatGraph(&G);
	printf("所以邻接矩阵为：\n");
	out(G);
	printf("深度遍历结果为："); 
	TraverseGraph(G); 
	return 0;
}