U222098 图的存储【笔记】
题目背景
## 链式前向星
```
#include
using namespace std;
struct q{
int to; //到达点的信息
int w; //距离
int next; //下一条边的信息
};
int head[105]; //（105:边的数量）所能指向的第一条边
q k[105]; //（同上）边的数组
int cnt = 0; //每条边的下标
void f(int a,int b,int c){ //a到达b的距离是c
//刚开始 1→-1
k[cnt].to = b;
k[cnt].w = c;
k[cnt].next = head[a];//0→-1
head[a] = cnt;//1→0
//此时1→0→-1
cnt++;//下一条边
}
int main(){
int n,m;
int a,b,c;
cin >> n >> m;
for (int i = 1;i a >> b >> c;
f(a,b,c);
}
int v;//已知边（求能到达哪些边）
cin >> v;
for (int i = head[v];i != -1;i = k[i].next){ //输出
cout
题目描述
## 矩阵表示法
- 用**矩阵**表示顶点间的邻接关系。
- $A[i][j]=1$表示顶点$i$到$j$有边，等于$0$表示没有边。
- 便于**快速判断**两个顶点间**是否有边。**
- 空间开销为$O(|V|^2)$，不存在的边也占了空间。
- 适用于**稠密图**。
---
### 代码
```cpp
#include
using namespace std;
int G[105][105];
int main(){
int n,m;
cin >> n >> m;
for (int i = 1;i > u >> v;
G[u][v] = 1;
}
for (int i = 1;i
输入格式
无
输出格式
## 邻接表
- **便于快速找到一个顶点的所有邻居**。
- 空间开销为$O(|E|+|V|)$。
- **紧凑**，只有存在的边占空间，适用于**稀疏图**。
---
### 代码
```cpp
#include
using namespace std;
vector G[105]; // t1能到达的第t2个点 = a[t1][t2]
int n,m;
int main(){
int x,y;
cin >> n >> m; // 点数、边数
for (int i = 1;i > x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1;i m >> b >> c; // 点数、边数、起点、终点
for (int i = 0;i < m;i++){
cin >> x >> y;
a[x].push_back(y);
}
w[b] = 1; // 初始化
dfs(b);
if (k == 1){
cout