求图的创建和遍历的c++算法,要主函数的~

发布网友 发布时间：2022-04-19 09:43

我来回答

共1个回答

热心网友 时间：2023-08-27 15:58

#include "stdio.h"
#define Max 10
typedef struct arcnode
{ int adjvex;
struct arcnode *nextarc;
}arcnode;

typedef struct vexnode
{ int vertex;
arcnode *firstarc;
}adjlist;

typedef struct gragh
{ adjlist adjlist[Max];
int vexnum,arcnum;
}graph;

void creatgraph(graph *g)
{ int i,j,k,n, e;
arcnode *p;
printf("Enter top and edge(n,e):\n");
scanf("%d,%d",&n,&e);
getchar();
g->vexnum=n;
g->arcnum=e;
for(i=0;i<g->vexnum;i++)
{ g->adjlist[i].vertex=i;
g->adjlist[i].firstarc=NULL;
}
printf("Please enter the top's edge information(i,j):\n");
for(k=0;k<g->arcnum;k++)
{
scanf("%d,%d",&i,&j);getchar();
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=j;
p->nextarc=g->adjlist[i].firstarc;
g->adjlist[i].firstarc=p;
}
}
/*如果用下面创建图的程序替换上面的创建图程序，可以免去输入的麻烦，直接得到生成的图*/
/*void creatgraph(graph *g)
{ int n=4,e=10,i,j,k;
arcnode *p;
int edge[][2]={{0,3},{3,0},{0,1},{1,0},{2,1},{1,2},{2,0},{0,2},{2,3},{3,2},};
g->vexnum=n;g->arcnum=e;
for(i=0;i<g->vexnum;i++)
{ g->adjlist[i].vertex=i;
g->adjlist[i].firstarc=NULL;
}

for(k=0;k<g->arcnum;k++)
{
i=edge[k][0];
j=edge[k][1];
p=(arcnode *)malloc(sizeof(arcnode));
p->adjvex=j;
p->nextarc=g->adjlist[i].firstarc;
g->adjlist[i].firstarc=p;
}
}
*/
void disp(graph *g)
{ int i,mark;
arcnode *p;
printf("putout a graph:\n");
for(i=0;i<g->vexnum;i++)
{ p=g->adjlist[i].firstarc;
mark=0;
while(p!=NULL)
{ printf("(%d,%d) ",i,p->adjvex);
p=p->nextarc;
mark=1;
}
if(mark==1)
printf("\n");
}
}
int visited[Max]={0};/*因为这个数组是个全局变量，所以递归的深度优先
遍历只能进行一次，而广度优先遍历可以多次*/
void DFS(graph *g,int i)
{ arcnode *p;
printf(" %d ",i);
visited[i]=1;
p=g->adjlist[i].firstarc;
while(p!=NULL)
{ if(!visited[p->adjvex])
DFS(g,p->adjvex);
p=p->nextarc;
}
}

void BFS(graph *g,int v)
{ int queue[Max],j,rear,front,i;
arcnode *p;
rear=front=0;
for(i=0;i<Max;i++)
visited[i]=0;
printf(" %d ",v);
visited[v]=1;
rear++;
queue[rear]=v;
while(front!=rear)
{ front++;
v=queue[front];
p=g->adjlist[v].firstarc;
while(p!=NULL)
{ if(!visited[p->adjvex])
{printf(" %d ",p->adjvex);
visited[p->adjvex]=1;
rear++;
queue[rear]=p->adjvex;
}
p=p->nextarc;
}
}
}

main()
{ graph *g;
int i,change;
clrscr();
creatgraph(g);
disp(g);
while(change)
{printf("Please change you ideas:\n"
"==>1:DFS the graph.\n"
"==>2:BFS the gragh.\n");
scanf("%d",&change);getchar();
if(change==0) exit();
switch(change){
case 1:
printf("11 please input the first beginning number:\n");
scanf("%d",&i);getchar();
DFS(g,i); break;
case 2:
printf("\n");
printf("22 please input the first beginning number:\n");
scanf("%d",&i);getchar();
BFS(g,i); break;
default:printf("Enter is error!Again!\n");break;
}
}
}