问题描述
- 求一个数据结构代码 要有注释 关于图的深度遍历的 要求必修用C语言做出
-
要求用数据结构 代码后面要有注释 底下的要求一个也不能漏图的DFS遍历 要求： 1) 先任意创建一个图； 2) 图的DFS的递归和非递归算法的实现 3) 要求用邻接矩阵、邻接表两种结构存储实现
解决方案
解决方案二：
图的深度优先遍历（DFS）
解决方案三：
#include
#include
typedef char vertextype;
typedef int edgetype;
#define MAXSIZE 20
int visit[10]={0};
typedef struct {
vertextype verx[MAXSIZE];
edgetype arc[MAXSIZE][MAXSIZE];
int vexnum,arcnum; //顶点数和边数
}mgraph;
int locate(mgraph *g,char v)
{
int i;
for(i=0;ivexnum;i++)
{
if(g->verx[i]==v)
{
return i;
}
}
return -1;
}
void creatgraph(mgraph *g){
int i,j,k;
char v1,v2;
scanf("%d%d",&(g->vexnum),&(g->arcnum));
fflush(stdin);
for(i=0;ivexnum;i++)
scanf("%c",&g->verx[i]);
fflush(stdin);
for(i=0;ivexnum;i++)
for(j=0;jvexnum;j++)
g->arc[i][j]=0; //邻接矩阵初始化
for(k=0;karcnum;k++)
{
scanf("%c%c",&v1,&v2);
i=locate(g,v1);
j=locate(g,v2);
g->arc[i][j]=1;
}
}
void DFS(mgraph *g,int i){
int j;
printf("%c ",g->verx[i]);
visit[i]=1;
for(j=1;jvexnum;j++)
if(g->arc[i][j]==1&&visit[j]==0)
DFS(g,j);
}
void main(){
mgraph g;
int i,j;
creatgraph(&g);
DFS(&g,0);
printf("n");
}