图
题单介绍
[图的定义与基本术语](https://baike.baidu.com/item/%E5%9B%BE/13018767)
图的存储方式有邻接矩阵和邻接表两种。
邻接矩阵指的是用一个二维数组记录每个点对之间的边的长度，若点a到点b有一条长度为c的边，那么edge[a][b]=c。
对于稀疏图来说，这种存储方式太过浪费空间，所以一般会使用邻接表来存储。
```cpp
struct edge{
int x,y,z;//x表示这条边的起点,y表示这条边的终点,z表示这条边的权值
};
vector<edge> a[1000];
//当读入一条有向边t时
edge t;
scanf("%d%d%d",&t.x,&t.y,&t.z);
a[t.x].push_back(t);
//若是无向图则在加上下面两句，即将边反过来再存下来:
swap(t.x,t.y);
a[t.x].push_back(t);
```
图的深度优先遍历：
```cpp
bool vst[1000];
void dfs(int x){
if(vst[x])return;
vst[x]=1;
printf("%d ",x);
for(int i=0;i<a[x].size();i++)
dfs(a[x][i]);
}
```
图的广度优先遍历：
```cpp
void bfs(int s){
q.push(x);
while(q.size()){
int x=q.front();q.pop();
printf("%d ",x);
for(int i=0;i<a[x].size();i++){
if(vst[a[x][i]])continue;
vst[a[x][i]]=1;
q.push(a[x][i]);
}
}
}
```