数据结构 图的遍历

发布网友 发布时间：2022-04-23 02:16

我来回答

共3个回答

热心网友 时间：2023-09-27 16:30

图的遍历：#include<stdio.h>
#define INFINITY 0
#define MAX_VERTEX_NUM 20
typedef int VRType,InfoType;
typedef char VertexType;
typedef struct ArcCell{
VRType adj;//VrType是顶点关系类型，对无权图，用1或0表示相邻否，对有权图为权值类型
InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;//图的当前顶点数和弧数
}MGraph;

int LocateVex(MGraph G,VertexType v){
int i;
for(i=0;i<G.vexnum;){
if(G.vexs[i]==v)
{
return i;
break;
}
i++;
}
if(i>=G.vexnum) return -1;
}
int CreateUDN(MGraph &G){//创建无向网
int IncInfo,i,k,j,w;
VertexType v1,v2;
printf("开始构造一个无向网\n");
printf("请输入图的顶点数 边数 弧是否包含其他信息\n");
scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);
printf("输入各顶点元素");
for(i=0;i<G.vexnum;++i)scanf("\n%c",&G.vexs[i]);
for(i=0;i<G.vexnum;++i)//初始化邻接矩阵
for(j=0;j<G.vexnum;++j) {
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
for(k=0;k<G.arcnum;++k){
printf("输入一条边依附的顶点及权:");
scanf("\n%c%c%d",&v1,&v2,&w);
i=LocateVex(G,v1);//确定v1和v2在G中的位置
j=LocateVex(G,v2);
G.arcs[i][j].adj=w;
if(IncInfo) {
printf("输入弧包含的信息:");
scanf("%d",&G.arcs[i][j].info);
}
G.arcs[j][i]=G.arcs[i][j];
}
return 1;
}

void DispGraph(MGraph G){//输出图的邻接矩阵表示
int i,j;
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++){
printf("%d\t",G.arcs[i][j].adj);
}
printf("\n");
}
}
void DFS(MGraph G,int first,int mark[])
{
int v1;
mark[first]=1;
printf("%c ",G.vexs[first]);
for(v1=0;v1<G.vexnum;v1++)
{
if(G.arcs[first][v1].adj!=0&&mark[v1]==0)
DFS(G,v1,mark);
}
}
void GraphDFS(MGraph G)
{
int first=0,v,v1,mark[MAX_VERTEX_NUM];
printf("\n深度遍历：");
for(v=0;v<G.vexnum;v++)
{
mark[v]=0;
}
for(v=first;v<G.vexnum+first;v++)
{
v1=v%G.vexnum;
if(mark[v1]==0)
DFS(G,v1,mark);
}
}

热心网友 时间：2023-09-27 16:31

无向图可以。有向图的话，因为可以认为是多条遍历路径同时进行，对于一个已访问过的结点无法判断该节点或其后代结点中是否存在当前遍历路径上的结点；而对于深度优先遍历，任何时候都只有一条遍历路径，可以通过标记区分出某个已访问结点是在当前路径上的结点还是不在当前路径上的已回溯结点。

热心网友 时间：2023-09-27 16:31

这个根据图的广度和深度算法就可以写出来。详细答案就是程序了。