1.使用邻接矩阵存储图
2.无向图
3.深度优先遍历顶点（递归）
准备部分：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_VERTEX_NUM 20
#define MAX 20
#define INF -1
#define error -1
#define ok 1
typedef struct ArcCell
{
int adj;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char vexs[MAX][MAX];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
//函数原型
void CreateUDN(MGraph &G);
int LocatVex(MGraph G,char v[MAX]);
void show(MGraph G);
void DFSTraverse(MGraph &G);
void DFS(MGraph &G,int v);
int firstAdjVex(MGraph G,int v);
int NextAdjVex(MGraph G,int v,int w);
//全局变量:
int visited[MAX];
int main()
{
MGraph G;
CreateUDN(G);
show(G);
DFSTraverse(G);
return 0;
}DFS遍历函数：
void DFSTraverse(MGraph &G)
{
int i;
for(i=0;i<G.vexnum;i++) //初始化标志变量
{
visited[i]=error;
}
for(i=0;i<G.vexnum;i++)
{
if(visited[i]==error)
{
DFS(G,i);
}
}
}
void DFS(MGraph &G,int v)
{
int w;
visited[v]=ok;
printf("%s->",G.vexs[v]);
for(w=firstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
{
if(visited[w]==error) DFS(G,w);
}
}
int firstAdjVex(MGraph G,int v)
{
int i;
for(i=0;i<G.vexnum;i++)
{
if(G.arcs[v][i].adj!=error)
{
return i;
}
}
return error;
}
int NextAdjVex(MGraph G,int v,int w)
{
int i;
for(i=w+1;i<G.vexnum;i++)
{
if(G.arcs[v][i].adj!=error)
{
return i;
}
}
return error;
}构造无向图的邻接矩阵：
void CreateUDN(MGraph &G)
{
int i,j,v,w;
char v1[MAX],v2[MAX];
printf("请输入顶点的个数: ");
scanf("%d",&G.vexnum);
printf("请输入边的个数: ");
scanf("%d",&G.arcnum);
for(i=0;i<G.vexnum;i++)
{
printf("请输入第%d个顶点的名称:",i+1);
scanf("%s",G.vexs[i]);
}
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=INF;
}
}
for(v=0;v<G.arcnum;v++)
{
printf("请输入第一个顶点:");
scanf("%s",&v1);
printf("请输入第二个顶点:");
scanf("%s",&v2);
i=LocatVex(G,v1);
j=LocatVex(G,v2);
printf("请输入两顶点之间的权值:");
scanf("%d",&w);
G.arcs[i][j].adj=w;
G.arcs[j][i]=G.arcs[i][j];
}
}
int LocatVex(MGraph G,char v[MAX])
{
int i;
for(i=0;i<G.vexnum;i++)
{
if(strcmp(G.vexs[i],v)==0)
{
return i;
}
}
return error;
}
//打印邻接矩阵
void show(MGraph G)
{
int i,j;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].adj!=error) printf(" %d",G.arcs[i][j].adj);
else printf(" ");
}
printf("\n");
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/69346.html
