图的深度和广度优先遍历实验
- 格式：rtf
- 大小：16.42 KB
- 文档页数：4
#include <stdio.h>
#include <malloc.h>
#define MAXVER 21
typedef char vextype;
typedef struct listnode
{
int adjvex;
struct listnode * next;
}listnode;
typedef struct
{
vextype data;
listnode * first;
}headnode;
typedef struct
{
headnode vexs[MAXVER];
int vexnum,arcnum;
}ALgraph;
int visited[MAXVER];
ALgraph createALgraph()
{
ALgraph G;
int i,s,d;
listnode * p,* q;
printf("ÊäÈëͼµÄ¶¥µãÊýºÍ±ßÊý£º");
scanf("%d,%d",&G.vexnum,&G.arcnum);
for(i=1;i<=G.vexnum;i++)
{
printf("\nÊäÈëµÚ%d¸ö¶¥µãÐÅÏ¢£º",i);
scanf("%c",G.vexs[i].data);
G.vexs[i].first=NULL;
}
for(i=1;i<=G.arcnum;i++)
{
printf("\nÊäÈëµÚ%dÌõ±ßµÄʼµã±àºÅ£¬ÖÕµã±àºÅ:",i);
scanf("%d,%d",&s,&d);
p=(listnode *)malloc(sizeof(listnode));
p->adjvex=d;
p->next=G.vexs[s].first;
G.vexs[s].first=p;
q=(listnode *)malloc(sizeof(listnode));
q->adjvex=s;
q->next=G.vexs[d].first;
G.vexs[d].first=q;
}
return G;
}
void dfs(ALgraph G,int v)
{
listnode * p;
printf("%c ",G.vexs[v].data);
visited[v]=1;
p=G.vexs[v].first;
//ͼÉî¶ÈÓÅÏȱéÀúµÄµÝ¹éËã·¨!!!!!!!!!!!
while(p!=NULL)
{
if(visited[p->adjvex]==0)
dfs(G,p->adjvex);
p=p->next;
}
}
void DFS(ALgraph G,int v)
{
listnode * stack[MAXVER],*p;
int top=0;
printf("%c",G.vexs[v].data);
visited[v]=1;
p=G.vexs[v].first;
while(top>0 || p!=NULL)
{
while(p!=NULL)
if(visited[p->adjvex]!=0)
p=p->next;
else
{
printf(",%c",G.vexs[p->adjvex].data);
visited[p->adjvex]=1;
stack[++top]=p;
p=G.vexs[p->adjvex].first;
}
if(top>0)
{
p=stack[top--];
p=p->next;
}
}
}
void dfsTraverse(ALgraph G)
{
int v;
for(v=1;v<=G.vexnum;v++)
visited[v]=0;
for(v=1;v<=G.vexnum;v++)
if(visited[v]==0)
DFS(G,v);//dfs(G,v);//
}
void BFS(ALgraph G,int v)
{
int queue[MAXVER],front,rear;
listnode * p;
front=rear=0;
printf("%c",G.vexs[v].data);
visited[v]=1;
queue[++rear]=v;
while(front!=rear)
{
v=queue[++front];
p=G.vexs[v].first;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
v=p->adjvex;
printf(",%c",G.vexs[v].data);
visited[v]=1;
queue[++rear]=v;
}
p=p->next;
}
}
}
void BFSTraverse(ALgraph G) {
int v;
for(v=1;v<=G.vexnum;v++) visited[v]=0;
for(v=1;v<=G.vexnum;v++) if(visited[v]==0)
BFS(G,v);
}
void main()
{
ALgraph G;
listnode a1,a2,a3;
listnode b1,b2,b3,b4;
listnode c1,c2,c3,c4,c5;
listnode d1,d2,d3;
listnode e1;
listnode f1;
listnode g1;
listnode h1,h2;
G.vexnum=8;
G.arcnum=10;
G.vexs[1].data='A';
G.vexs[2].data='B';
G.vexs[3].data='C';
G.vexs[4].data='D';
G.vexs[5].data='E';
G.vexs[6].data='F';
G.vexs[7].data='G';
G.vexs[8].data='H';
G.vexs[1].first=&a1;
a1.adjvex=4;
a1.next=&a2;
a2.adjvex=3;
a2.next=&a3;
a3.adjvex=2;
a3.next=NULL;
G.vexs[2].first=&b1;
b1.adjvex=6;
b1.next=&b2;
b2.adjvex=5;。
