图的广度遍历和深度遍历图
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1e5+10;
struct Node{
char date;
int fristedge;
void clear()
{
fristedge=-1;
}
}head[maxn];;
struct Edge{
int v;//该边连接的下一个节点
int next;
void clear()
{
next=-1;
}
}edge[maxn];
void AddEdge(int u,int v,int index)//把边u v邻接表中
{
edge[index].clear();
edge[index].v=v;
edge[index].next=head[u].fristedge;
head[u].fristedge=index;
}
void CreatGraph(struct Node *head,struct Edge *edge)
{
int n,m;//表示边的个数
printf("the point(n) and edge(e):");
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
head[i].clear();
printf(" he %d information:",i);
char s[2];
scanf("%s",s);
head[i].date=s[0];
}
for(int i=1;i<=m;++i)
{
printf("
the%d edges=>
:",i);
int u ,v;
scanf("%d %d",&u,&v);
AddEdge(u,v,i);
}
}
int book[maxn];
void dfs(int u)//u节点深搜
{
/*
1.遍历与u邻接的边
2.若该定点被搜索过 则返回，否则将u标记已遍历过，并输出该节点信息
3.遍历所有与u邻接的终端节点v dfs(v)。
*/
if(book[u])
return;
printf("now is at point %d",u);
printf("the data is %c
",head[u].date);
book[u]=1;
int to=head[u].fristedge;//to表示遍历节点u的连接的所有边
while(~to)
{
dfs(edge[to].v);
to=edge[to].next;
}
}
void bfs()//广搜
{
memset(book,0,sizeof(book));
queue<int> mmp;
mmp.push(1);
book[1]=1;
int u;
/*
1.把节点1 放入队列，并将该顶点进行标记已经遍历过。
2.每次从队列中取出一个顶点u，如果队列已 空则退出
3.输出u节点的信息
4.将与u顶点邻接的顶点且未加入队列的加入队列。重复步骤2
*/
while(!mmp.empty())
{
u=mmp.front();
mmp.pop();
printf("now visit the point:%c
",head[u].date);
int to;
to=head[u].fristedge;
while(~to)
{
if(!book[edge[to].v])
{
mmp.push(edge[to].v);
book[edge[to].v]=1;
}
to=edge[to].next;
}
}
}
int main()
{
memset(book,0,sizeof(book));
CreatGraph(head,edge);
printf("dfs...........................
");
dfs(1);
printf("bfs...........................
");
bfs();
return 0;
}
/*
1.
2.
*/