在这里对图的存储和遍历进行一个规范，为以后更复杂的数据结构学习打下基础
首先是邻接矩阵的形式，适合于存稠密图，如果是全连接图就再合适不过了
int a[maxn][maxn];
一个二维数组就可以搞定了，如果是bool值那么就是不带权值的
a[i][j]=w表示i->j这条边的权值为w,反之亦然
建图操作是很显然的
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
接下来是一个DFS：
int vis[maxn];
void dfs(int dp,int x)
{
cout<<x<<" ";
for(int i=1;i<=n;i++)
if(a[x][i]&&!vis[i])
{
vis[i]=1;
dfs(dp+1,i);
}
}
特别强调一下，我是先输出的结果，再进行的遍历，如果给定的图不是连通的，给了一片森林的话，一定要注意相应的细节
在这里的细节处理是给刚开始进入dfs的点打上标记，不要漏掉这里
然后是BFS，处理方法类似
int q[maxn];
void bfs(int x)
{
int h=0,t=1;
q[t]=x;
while(h!=t)
{
h=h%maxn+1;
cout<<q[h]<<" ";
for(int i=1;i<=n;i++)
if(a[q[h]][i]&&!vis[i])
{
vis[i]=1;
t=t%maxn+1;
q[t]=i;
}
}
}
接下来给出一个完整的例子：
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 const int maxn=1005;
5 int n;
6 int a[maxn][maxn];
7 int vis[maxn];
8 void dfs(int dp,int x)
9 {
10 cout<<x<<" ";
11 for(int i=1;i<=n;i++)
12 if(a[x][i]&&!vis[i])
13 {
14 vis[i]=1;
15 dfs(dp+1,i);
16 }
17 }
18 int q[maxn];
19 void bfs(int x)
20 {
21 int h=0,t=1;
22 q[t]=x;
23 while(h!=t)
24 {
25 h=h%maxn+1;
26 cout<<q[h]<<" ";
27 for(int i=1;i<=n;i++)
28 if(a[q[h]][i]&&!vis[i])
29 {
30 vis[i]=1;
31 t=t%maxn+1;
32 q[t]=i;
33 }
34 }
35 }
36 int main()
37 {
38 cin>>n;
39 for(int i=1;i<=n;i++)
40 for(int j=1;j<=n;j++)
41 cin>>a[i][j];
42 vis[1]=1;
43 dfs(1,1);
44 memset(vis,0,sizeof(vis));
45 cout<<endl;
46 vis[1]=1;
47 bfs(1);
48 return 0;
49 }
50 /*
51 0 1 1 0 0
52 1 0 0 1 1
53 1 0 0 0 0
54 0 1 0 0 0
55 0 1 0 0 0
56 */
然后就是邻接链表了，邻接链表的存储形式是用的最多的
struct Edge
{
int t,w,next;
}e[maxm];
int g[maxn];
int tot=0;
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]=1;
dfs(dp+1,e[tmp].t);
}
}
int q[maxn];
void bfs(int x)
{
int h=0,t=1;
q[t]=x;
while(h!=t)
{
h=h%maxn+1;
cout<<q[h]<<" ";
for(int tmp=g[q[h]];tmp;tmp=e[tmp].next)
if(!vis[e[tmp].t])
{
vis[e[tmp].t]=1;
t=t%maxn+1;
q[t]=e[tmp].t;
}
}
}
这里再补充一下刚才提到的森林的问题，由于我们是进入的时候就直接输出，所以第一个点一定要提前做好标记
由于是森林，每个点都要跑一边BFS或者DFS，那么在其他点的时候，进入之前判断vis,如果可行，打上vis之后再去跑，这样就没有任何问题了
最后给出邻接链表的完整实现：
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 const int maxn=1005;
5 const int maxm=1005;
6 int n,m;
7 struct Edge
8 {
9 int t,w,next;
10 }e[maxm];
11 int g[maxn];
12 int tot=0;
13 void addedge(int a,int b,int c)
14 {
15 tot++;
16 e[tot].t=b;
17 e[tot].w=c;
18 e[tot].next=g[a];
19 g[a]=tot;
20 }
21 int vis[maxn];
22 void dfs(int dp,int x)
23 {
24 cout<<x<<" ";
25 for(int tmp=g[x];tmp;tmp=e[tmp].next)
26 if(!vis[e[tmp].t])
27 {
28 vis[e[tmp].t]=1;
29 dfs(dp+1,e[tmp].t);
30 }
31 }
32 int q[maxn];
33 void bfs(int x)
34 {
35 int h=0,t=1;
36 q[t]=x;
37 while(h!=t)
38 {
39 h=h%maxn+1;
40 cout<<q[h]<<" ";
41 for(int tmp=g[q[h]];tmp;tmp=e[tmp].next)
42 if(!vis[e[tmp].t])
43 {
44 vis[e[tmp].t]=1;
45 t=t%maxn+1;
46 q[t]=e[tmp].t;
47 }
48 }
49 }
50 int main()
51 {
52 cin>>n>>m;
53 for(int i=1;i<=m;i++)
54 {
55 int x,y,z;
56 cin>>x>>y>>z;
57 addedge(x,y,z);
58 addedge(y,x,z);
59 }
60 vis[1]=1;
61 dfs(1,1);
62 memset(vis,0,sizeof(vis));
63 cout<<endl;
64 vis[1]=1;
65 bfs(1);
66 return 0;
67 }
邻接链表是我最喜欢的一种存图的形式了
最后就是我觉得比较奇葩的邻接数组，是为了三级项目刻意实现的，当然如果把数组换成vector会更自然一些
这里直接给出完整实现，和邻接链表大同小异，唯一的区别就是不用存next，直接枚举数组下标就可以了
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 const int maxn=1005;
5 const int maxm=1005;
6 int n,m;
7 struct Edge
8 {
9 int t,w;
10 };
11 struct Graph
12 {
13 int cur;
14 Edge e[maxm];
15 }g[maxn];
16 int tot=0;
17 void addedge(int a,int b,int c)
18 {
19 tot++;
20 Edge tmp;
21 tmp.t=b;
22 tmp.w=c;
23 g[a].cur++;
24 int t=g[a].cur;
25 g[a].e[t]=tmp;
26 }
27 int vis[maxn];
28 void dfs(int dp,int x)
29 {
30 cout<<x<<" ";
31 for(int tmp=1;tmp<=g[x].cur;tmp++)
32 if(!vis[g[x].e[tmp].t])
33 {
34 vis[g[x].e[tmp].t]=1;
35 dfs(dp+1,g[x].e[tmp].t);
36 }
37 }
38 int q[maxn];
39 void bfs(int x)
40 {
41 int h=0,t=1;
42 q[t]=x;
43 while(h!=t)
44 {
45 h=h%maxn+1;
46 cout<<q[h]<<" ";
47 for(int tmp=1;tmp<=g[q[h]].cur;tmp++)
48 if(!vis[g[q[h]].e[tmp].t])
49 {
50 vis[g[q[h]].e[tmp].t]=1;
51 t=t%maxn+1;
52 q[t]=g[q[h]].e[tmp].t;
53 }
54 }
55 }
56 int main()
57 {
58 cin>>n>>m;
59 for(int i=1;i<=m;i++)
60 {
61 int x,y,z;
62 cin>>x>>y>>z;
63 addedge(x,y,z);
64 addedge(y,x,z);
65 }
66 vis[1]=1;
67 dfs(1,1);
68 memset(vis,0,sizeof(vis));
69 cout<<endl;
70 vis[1]=1;
71 bfs(1);
72 return 0;
73 }
在每一种形式中，DFS和BFS先入栈和先入队的点是可能不一样的，但是结果都是正确的，在用之前一定要现在纸上画一画，避免输出顺序错误