图的深度广度遍历
- 提问者网友：姑娘长的好罪过
- 2021-04-22 19:02
- 五星知识达人网友：骨子里都是戏
- 2021-04-22 19:12
#include <stdio.h>
#include <iostream.h>
#include <malloc.h>
#define max 20
int visited[max];
int w;
typedef struct arcnode
{
int adjvex;//该弧指向的顶点的位置
struct arcnode *nextarc;//弧尾相同的下一条弧
char *info;//该弧信息
}arcnode;
typedef struct vnode
{
char data;//结点信息
arcnode *firstarc;//指想第一条依附该结点的弧的指针
}vnode,adjlist;
typedef struct
{
adjlist vertices[max];
int vexnum,arcnum;
int kind;
}algraph;
typedef struct qnode
{
int data;
struct qnode *next;
}qnode,*queueptr;
typedef struct
{
queueptr front;
queueptr rear;
}linkqueue;
void dfs(algraph gra,int i);
int creatadj(algraph &gra)//用邻接表存储图
{
int i,n,m;
char cha;
cout<<"输如结点个数：";
cin>>n;
cout<<"输如弧个数：";
cin>>m; arcnode *arc,*tem;
for(i=0;i<n;i++)
{
cout<<"输如结点信息：";
cin>>gra.vertices[i].data;
gra.vertices[i].firstarc=NULL;
}
for(i=0;i<n;i++)
{
cout<<"结点"<<i<<"是否有出度：";
cin>>cha;
if(cha=='y')
{
arc=(arcnode *)malloc(sizeof(arcnode));
cin>>arc->adjvex;
gra.vertices[i].firstarc=arc;
cout<<"是否还有出度：";
cin>>cha;
while(cha=='y')
{
tem=(arcnode *)malloc(sizeof(arcnode));
cin>>tem->adjvex;
arc->nextarc=tem;
arc=tem;
cout<<"是否还有出度：";
cin>>cha;
}
arc->nextarc=NULL;
}
if(cha=='n')
continue;
}
gra.vexnum=n;
gra.arcnum=m;
return 1;
}
int firstadjvex(algraph gra,vnode v)//返回依附顶点V的第一个点
//即以V为尾的第一个结点
{
return v.firstarc->adjvex;
}
int nextadjvex(algraph gra,vnode v,int w)//返回依附顶点V的相对于W的下一个顶点
{
arcnode *p;
p=v.firstarc;
while(p!=NULL)
{
if(p->adjvex!=w)
p=p->nextarc;
if(p->adjvex==w&&p->nextarc!=NULL)
return p->nextarc->adjvex;
else return 0;
}
}
int initqueue(linkqueue &q)//初始化队列
{
q.rear=(queueptr)malloc(sizeof(qnode));
q.front=q.rear;
if(!q.front)
return 0;
q.front->next=NULL;
return 1;
}
int enqueue(linkqueue &q,int e)//入队
{
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p)
return 0;
p->data=e;
p->next=NULL;
q.rear->next=p;
q.rear=p;
return 1;
}
int dequeue(linkqueue &q,int &e)//出队
{
queueptr p;
if(q.front==q.rear)
return 0;
p=q.front->next;
e=p->data;
q.front->next=p->next;
if(q.rear==p)
q.rear=q.front;
free(p);
return 1;
}
int queueempty(linkqueue q)//判断队为空
{
if(q.front==q.rear)
return 1;
return 0;
}
void bfstra(algraph gra,vnode v)//广度优先遍历
{
int i,e;
linkqueue q;
for(i=0;i<gra.vexnum;i++)
visited[i]=0;
initqueue(q);
for(i=0;i<gra.vexnum;i++)
if(!visited[i])
{
visited[i]=1;
cout<<gra.vertices[i].data;
enqueue(q,i);
while(!queueempty(q))
dequeue(q,e);
for(w=firstadjvex(gra,gra.vertices[e]);w>0;w=nextadjvex(gra,gra.vertices[e],w))
if(!visited[w])
{
visited[w]=1;cout<<gra.vertices[w].data;
enqueue(q,w);
}
}
}
int dfstra(algraph gra,vnode v)//深度优先遍历
{
int i;
for(i=0;i<gra.vexnum;i++)
visited[i]=0;
for(i=0;i<gra.vexnum;i++)
if(!visited[i])
dfs(gra,i);
return 1;
}
void dfs(algraph gra,int i)
{
visited[i]=1;
cout<<gra.vertices[i].data;
for(w=firstadjvex(gra,gra.vertices[i]);w>0;w=nextadjvex(gra,gra.vertices[i],w))
if(!visited[w])
dfs(gra,w);
}
void main()
{
algraph gra;
vnode v;
creatadj(gra);
cout<<"广度优先遍历：";
bfstra(gra,v);
cout<<endl;
cout<<"深度优先遍历：";
dfstra(gra,v);
cout<<endl;
}