在这里对图的存储和遍历进行一个规范,为以后更复杂的数据结构学习打下基础
首先是邻接矩阵的形式,适合于存稠密图,如果是全连接图就再合适不过了
int a[maxn][maxn];
一个二维数组就可以搞定了,如果是bool值那么就是不带权值的
a[i][j]=w表示i->j这条边的权值为w,反之亦然
建图操作是很显然的
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>a[i][j];
接下来是一个DFS:
int vis[maxn];
void dfs(int dp,int x)
{
cout<<x<<" ";
for(int i=;i<=n;i++)
if(a[x][i]&&!vis[i])
{
vis[i]=;
dfs(dp+,i);
}
}
特别强调一下,我是先输出的结果,再进行的遍历,如果给定的图不是连通的,给了一片森林的话,一定要注意相应的细节
在这里的细节处理是给刚开始进入dfs的点打上标记,不要漏掉这里
然后是BFS,处理方法类似
int q[maxn];
void bfs(int x)
{
int h=,t=;
q[t]=x;
while(h!=t)
{
h=h%maxn+;
cout<<q[h]<<" ";
for(int i=;i<=n;i++)
if(a[q[h]][i]&&!vis[i])
{
vis[i]=;
t=t%maxn+;
q[t]=i;
}
}
}
接下来给出一个完整的例子:
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
int n;
int a[maxn][maxn];
int vis[maxn];
void dfs(int dp,int x)
{
cout<<x<<" ";
for(int i=;i<=n;i++)
if(a[x][i]&&!vis[i])
{
vis[i]=;
dfs(dp+,i);
}
}
int q[maxn];
void bfs(int x)
{
int h=,t=;
q[t]=x;
while(h!=t)
{
h=h%maxn+;
cout<<q[h]<<" ";
for(int i=;i<=n;i++)
if(a[q[h]][i]&&!vis[i])
{
vis[i]=;
t=t%maxn+;
q[t]=i;
}
}
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
cin>>a[i][j];
vis[]=;
dfs(,);
memset(vis,,sizeof(vis));
cout<<endl;
vis[]=;
bfs();
return ;
}
/*
0 1 1 0 0
1 0 0 1 1
1 0 0 0 0
0 1 0 0 0
0 1 0 0 0
*/
然后就是邻接链表了,邻接链表的存储形式是用的最多的
struct Edge
{
int t,w,next;
}e[maxm];
int g[maxn];
int tot=;
dalao们喜欢用vector改成邻接数组,我不是dalao,所以就先这样了(*^▽
意义还是很明显的,t代表着这条边的to节点,如果需要记录起始节点,就要存一个u了
由于是链表,next是必不可少的,存的是与此边共起点的下一条边的编号
然后就是g数组了,存的是由下标节点所引出的第一条边的编号
建图采用的是链表的头插法
void addedge(int a,int b,int c)
{
tot++;
e[tot].t=b;
e[tot].w=c;
e[tot].next=g[a];
g[a]=tot;
}
然后我们给出DFS和BFS的部分,这里原理是一模一样的,唯一需要注意的就是,数据结构变了,循环变量什么的要相应的调整
int vis[maxn];
void dfs(int dp,int x)
{
cout<<x<<" ";
for(int tmp=g[x];tmp;tmp=e[tmp].next)
if(!vis[e[tmp].t])
{
vis[e[tmp].t]=;
dfs(dp+,e[tmp].t);
}
}
int q[maxn];
void bfs(int x)
{
int h=,t=;
q[t]=x;
while(h!=t)
{
h=h%maxn+;
cout<<q[h]<<" ";
for(int tmp=g[q[h]];tmp;tmp=e[tmp].next)
if(!vis[e[tmp].t])
{
vis[e[tmp].t]=;
t=t%maxn+;
q[t]=e[tmp].t;
}
}
}
这里再补充一下刚才提到的森林的问题,由于我们是进入的时候就直接输出,所以第一个点一定要提前做好标记
由于是森林,每个点都要跑一边BFS或者DFS,那么在其他点的时候,进入之前判断vis,如果可行,打上vis之后再去跑,这样就没有任何问题了
最后给出邻接链表的完整实现:
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int maxm=;
int n,m;
struct Edge
{
int t,w,next;
}e[maxm];
int g[maxn];
int tot=;
void addedge(int a,int b,int c)
{
tot++;
e[tot].t=b;
e[tot].w=c;
e[tot].next=g[a];
g[a]=tot;
}
int vis[maxn];
void dfs(int dp,int x)
{
cout<<x<<" ";
for(int tmp=g[x];tmp;tmp=e[tmp].next)
if(!vis[e[tmp].t])
{
vis[e[tmp].t]=;
dfs(dp+,e[tmp].t);
}
}
int q[maxn];
void bfs(int x)
{
int h=,t=;
q[t]=x;
while(h!=t)
{
h=h%maxn+;
cout<<q[h]<<" ";
for(int tmp=g[q[h]];tmp;tmp=e[tmp].next)
if(!vis[e[tmp].t])
{
vis[e[tmp].t]=;
t=t%maxn+;
q[t]=e[tmp].t;
}
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
addedge(x,y,z);
addedge(y,x,z);
}
vis[]=;
dfs(,);
memset(vis,,sizeof(vis));
cout<<endl;
vis[]=;
bfs();
return ;
}
邻接链表是我最喜欢的一种存图的形式了
最后就是我觉得比较奇葩的邻接数组,是为了三级项目刻意实现的,当然如果把数组换成vector会更自然一些
这里直接给出完整实现,和邻接链表大同小异,唯一的区别就是不用存next,直接枚举数组下标就可以了
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=;
const int maxm=;
int n,m;
struct Edge
{
int t,w;
};
struct Graph
{
int cur;
Edge e[maxm];
}g[maxn];
int tot=;
void addedge(int a,int b,int c)
{
tot++;
Edge tmp;
tmp.t=b;
tmp.w=c;
g[a].cur++;
int t=g[a].cur;
g[a].e[t]=tmp;
}
int vis[maxn];
void dfs(int dp,int x)
{
cout<<x<<" ";
for(int tmp=;tmp<=g[x].cur;tmp++)
if(!vis[g[x].e[tmp].t])
{
vis[g[x].e[tmp].t]=;
dfs(dp+,g[x].e[tmp].t);
}
}
int q[maxn];
void bfs(int x)
{
int h=,t=;
q[t]=x;
while(h!=t)
{
h=h%maxn+;
cout<<q[h]<<" ";
for(int tmp=;tmp<=g[q[h]].cur;tmp++)
if(!vis[g[q[h]].e[tmp].t])
{
vis[g[q[h]].e[tmp].t]=;
t=t%maxn+;
q[t]=g[q[h]].e[tmp].t;
}
}
}
int main()
{
cin>>n>>m;
for(int i=;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
addedge(x,y,z);
addedge(y,x,z);
}
vis[]=;
dfs(,);
memset(vis,,sizeof(vis));
cout<<endl;
vis[]=;
bfs();
return ;
}
在每一种形式中,DFS和BFS先入栈和先入队的点是可能不一样的,但是结果都是正确的,在用之前一定要现在纸上画一画,避免输出顺序错误