Code

/* '邻接矩阵' 实现无向图的创建、深度优先遍历*/
#include <stdio.h>
#include <stdlib.h> #define MaxVex 100 //最多顶点个数
#define INFINITY 32768 //表示极大值,即 ∞
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0 typedef char VertexType; //假设顶点数据类型为字符类型
typedef int EdgeType; //对于无权图,用1或0表示是否相邻,对带权图,则为权值类型
typedef struct
{
VertexType vertex[MaxVex]; //顶点数组
EdgeType arcs[MaxVex][MaxVex]; //邻接矩阵
int vexnum,arcnum; //图中的顶点数和边数
}Graph; int visited[MaxVex]; //访问标志数组 /**********************各个子函数的定义*********************/
void init(Graph *G); //初始化邻接矩阵
int LocateVertex(Graph *G,VertexType v);//求顶点位置函数
int createUDG(Graph *G); //创建一个无向图
void DepthFirstSearch(Graph G, int i); //图的深度优先遍历
void TraverseGraph(Graph G); /**************************主函数*************************/
int main()
{
Graph G;
int choice;
while(true)
{
printf("*****************Please enter your choice*****************\n\n");
printf(" choice 1:Initialization\n");
printf(" choice 2:Create Graph\n");
printf(" choice 3:Depth First Search\n");
printf(" choice 0:exit\n\n");
scanf("%d",&choice);
switch(choice)
{
case :
init(&G);
break;
case :
(createUDG(&G)==)?printf("Create Graph success.\n"):printf("Create Graph ERROR\n");
break;
case :
printf("图的深度优先遍历为: ");
TraverseGraph(G);
break;
case :
exit();
break;
default:
printf("ERROR!!\n");
exit();
break;
}
}
return ;
} /**********************各个子函数功能的实现*********************/
void init(Graph *G) //初始化邻接矩阵
{
int i,j;
printf("请输入图的顶点个数和边数:");
scanf("%d %d",&(G->vexnum),&(G->arcnum));//输入图的顶点个数和边数
for(i=;i<G->vexnum;i++) //初始化
{
for(j=;j<G->vexnum;j++)
{
G->arcs[i][j]=INFINITY;
}
}
printf("图的初始化成功\n");
} int LocateVertex(Graph *G,VertexType v) //查找并返回顶点的位置
{
int j=,k;
for(k=;k<G->vexnum;k++)
{
if(G->vertex[k]==v)
{
j=k;
break;
}
}
return j;
} int createUDG(Graph *G) //创建一个无向图
{
int i,j,k,weight;
VertexType v1,v2;
for(i=;i<G->vexnum;i++)
{
printf("请输入图的第 %d 顶点:",i+);
getchar();
scanf("%c",&(G->vertex[i])); //输入图的顶点集
}
for(k=;k<G->arcnum;k++)
{
printf("请分别输入图的第 %d 条边的两个顶点和权值",k+);
getchar();
scanf("%c %c %d",&v1,&v2,&weight);//输入一条边的两个顶点、权值
i=LocateVertex(G,v1);
j=LocateVertex(G,v2);
G->arcs[i][j]=weight; //建立顶点之间的关系
G->arcs[j][i]=weight;
}
return OK;
} void DepthFirstSearch(Graph G, int i) //图的深度优先遍历
{
int j;
visited[i] = TRUE;
printf("%c ",G.vertex[i]);
for (j=; j<G.vexnum; j++)
{
if (G.arcs[i][j]!=INFINITY && !visited[j])
DepthFirstSearch(G,j);
}
} void TraverseGraph(Graph G)
{
int i;
for (i=; i<G.vexnum; i++) //初始化访问标志数组
visited[i] = FALSE; for (i=; i<G.vexnum; i++)//循环调用深度优先遍历连通子图的操作,若图G是连通图,则此调用只执行一次
{
if (!visited[i])
DepthFirstSearch(G, i);
}
printf("\n");
}

代码测试

C语言实现邻接矩阵创建无向图&amp;图的深度优先遍历-LMLPHPC语言实现邻接矩阵创建无向图&amp;图的深度优先遍历-LMLPHP​​

04-25 11:21
查看更多