数据结构上机实验dfs&&bfs遍历图

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<algorithm>
#define MAX 1000
using namespace std;
int head[MAX],ans;
int vis[MAX],viss[MAX];
int map[MAX],ant;
queue<int>q;
struct node
{
int u,v,next;
}edge[MAX];
void init()
{
memset(head,-1,sizeof(head));
ans=0;
}
void add(int u,int v)
{
edge[ans].u=u;
edge[ans].v=v;
edge[ans].next=head[u];
head[u]=ans++;
}
void bfs(int beg)
{
int i,j;
vis[beg]=1;
q.push(beg);
printf("%d ",beg);
while(!q.empty())
{
int u=q.front();
q.pop();
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
printf("%d ",v);
vis[v]=1;
q.push(v);
}
}
}
printf("\n");
}
void dfs(int beg)
{
int i,j;
vis[beg]=1;
if(!viss[beg])
{
map[ant++]=beg;
viss[beg]=1;
}
for(i=head[beg];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
if(!viss[v])
{
map[ant++]=v;
viss[v]=1;
}
vis[v]=1;
dfs(v);
vis[v]=0;
}
}
}
int main()
{
int n,m,j,i,k,a,b;
int start;
while(1)
{
init();
printf("请输入你要创建的图的顶点连线的对数\n");
scanf("%d",&n);
printf("请输入每对顶点的值\n");
while(n--)
{
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
while(1)
{
printf("请输入你要开始广度优先遍历的起点,如果你想要退出进行其他操作请输入-1\n");
memset(vis,0,sizeof(vis));
while(!q.empty())
q.pop();
scanf("%d",&start);
if(start==-1)
break;
bfs(start);
}
while(1)
{
printf("请输入你要开始深度优先遍历的起点,如果你想要退出进行其他操作请输入-1\n");
memset(vis,0,sizeof(vis));
memset(viss,0,sizeof(viss));
while(!q.empty())
q.pop();
scanf("%d",&start);
if(start==-1)
break;
ant=0;
dfs(start);
for(i=0;i<ant;i++)
{
if(map[i]!=map[i+1])
printf("%d ",map[i]);
}
printf("\n");
}
}
return 0;
}

  

上一篇:Java生成、解析二维码


下一篇:ZXing生成条形码、二维码、带logo二维码