图（邻接表法）
图的表示方法有很多，这里有一种比较常见的用法：邻接表法，它的实现往往在竞赛中不用链表，而是通过vector动态数组实现
表示方法：
vector<int>a[10]；//表示有10个结点，其中每个结点对应的vector里存放与它相连的结点
例题1：求各点到1号点的最短距离
测试数据：
7 6
1 2
2 4
1 3
2 5
3 7
3 6
/*邻接表 bfs 最短距离*/
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int n,m;
vector<int>a[10];
bool vis[12];
int dis[12];//记录步数
queue<int> q;
void bfs(int st){
q.push(st);
vis[st]=1;
memset(dis,0x3f,sizeof(dis));
dis[st]=0;//起点的步数为0
while(!q.empty()){
int now=q.front();
q.pop();
for(auto to:a[now]){
if(!vis[to]){
dis[to]=min(dis[to],dis[now]+1);
q.push(to);
vis[to]=1;
}
}
}
}
int main(){
cin>>n>>m;
int u,v;
for(int i=1;i<=m;i++){
cin>>u>>v;
a[u].push_back(v);//无向图，需要两次
a[v].push_back(u);
}
bfs(1);
/*求最短距离的*/
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
return 0;
}
/*
7 6
1 2
2 4
1 3
2 5
3 7
3 6
*/
例题2：图的遍历（普及+/提高）
题目描述
给出N个点，M条边的有向图，对于每个点v*，求A(v)表示从点vv出发，能到达的编号最大的点。
输入格式
第1 行，2 个整数N,M*。
接下来M行，每行2个整数U_i,V_iU**i,V**i，表示边(U_i,V_i)(U**i,V**i)。点用1, 2,\cdots,N1,2,⋯,N编号。
输出格式
N 个整数A(1),A(2),\cdots,A(N)A(1),A(2),⋯,A(N)。
输入输出样例
输入 #1复制
4 3
1 2
2 4
4 3
输出 #1复制
4 4 3 4
说明/提示
• 对于60% 的数据，1 \le N . M \le 10^31≤N.M≤103；
• 对于100% 的数据，1 \le N , M \le 10^51≤N,M≤105。
大佬题解：反向建边 + dfs
按题目来每次考虑每个点可以到达点编号最大的点，不如考虑较大的点可以反向到达哪些点
循环从N到1，则每个点i能访问到的结点的A值都是i
每个点访问一次，这个A值就是最优的，因为之后如果再访问到这个结点那么答案肯定没当前大了
#include<bits/stdc++.h>
using namespace std;
vector<int> vv[100005];
int dis[100005];
int n,m;
void dfs(int x,int d){
if(dis[x]){
return;
}
dis[x]=max(dis[x],d);
for(int i=0;i<vv[x].size();i++){
dfs(vv[x][i],d);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
vv[v].push_back(u);
}
//memset(dis,0x7fffffff,sizeof(dis));
for(int i=n;i>=1;i--){
dfs(i,i);
}
for(int i=1;i<=n;i++){
cout<<dis[i]<<" ";
}
return 0;
}
例题3：图的两种遍历方式
小K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。
假设洛谷博客里面一共有 n(n\le10^5)n(n≤105) 篇文章（编号为 1 到 nn）以及 m(m\le10^6)m(m≤106) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。
这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。保证编号为 1 的文章没有被其他文章引用。
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。
输入格式
无
输出格式
无
输入输出样例
输入 #1复制
8 9
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
输出 #1复制
1 2 5 6 3 7 8 4
1 2 3 4 5 6 7 8
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> A[100005];
bool book[100005];
queue<int> qu;
void dfs(int x){
if(book[x]){
return;
}
book[x]=1;
cout<<x<<" ";
for(int i=0;i<A[x].size();i++){
dfs(A[x][i]);
}
}
void bfs(int x){
qu.push(x);
book[x]=1;
while(!qu.empty()){
int now=qu.front();
cout<<now<<" ";
qu.pop();
for(int i=0;i<A[now].size();i++){
if(!book[A[now][i]]){
book[A[now][i]]=1;
qu.push(A[now][i]);
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
A[u].push_back(v);
}
for(int i=1;i<=n;i++){
sort(A[i].begin(),A[i].end());
}
dfs(1);
cout<<endl;
memset(book,0,sizeof(book));
bfs(1);
}
转载：https://blog.csdn.net/hebtu_Kangweiqi/article/details/105766480