图的存储方式：
1，数组表示法：
用两个数组来存储图的信息
- 顶点表：记录各个顶点信息的
- 邻接矩阵：表示各个顶点之间的关系(有关为1，无关为0)
注：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。
无向图的邻接矩阵
结点i的度=邻接矩阵中第i行或第i列之和
存储压缩：上三角矩阵或下三角矩阵(不含对角线)
有向图的邻接矩阵
结点i的出度=邻接矩阵中第i行之和
结点i的入度=邻接矩阵中第i列之和
A.edge[i][j]= 如果两点直接存在边且有权值，就记为权值，自环或者无边就记为∞
优点：容易实现图的各种基本操作
{
查找顶点，
判断顶点之间是否有边，仅仅耗费O(1)时间
找顶点的邻接点
}
缺点：稀疏图，即使边数<<n^2,也需要占用O(n^2)的存储单元，读入数据需要耗费O(n^2)时间
邻接矩阵表示方法，code：
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 int n, m;
7 vector<bool> vis;
8 vector<vector<bool> > adj;
9
10 bool find_edge(int u, int v) { return adj[u][v]; }
11
12 void dfs(int u) {
13 if (vis[u]) return;
14 vis[u] = true;
15 for (int v = 1; v <= n; ++v) {
16 if (adj[u][v]) {
17 dfs(v);
18 }
19 }
20 }
21
22 int main() {
23 cin >> n >> m;
24
25 vis.resize(n + 1, false);
26 adj.resize(n + 1, vector<bool>(n + 1, false));
27
28 for (int i = 1; i <= m; ++i) {
29 int u, v;
30 cin >> u >> v;
31 adj[u][v] = true;
32 }
33
34 return 0;
35 }
2，邻接表表示法
图的一种链式存储结构
顶点表：记录各个顶点的信息，通常以顺序结构存储，也可以链式存储(vector存储)
邻接链表：为每个顶点建立一个单链表，表示依附于改顶点的所有边(对有向图是以该节点为尾的所有弧)
无向图的邻接表
优点：n个顶点，e条边的无向图，只需要n个头结点和2e个表节点。对稀疏图而言，比数组表示法节省存储空间。
缺点：每条边需要对应两个表结点
有向图的邻接表
缺点：
{
查找进入某个结点的弧不易
求某个顶点的入度需要遍历整个邻接表
}
改进：建立逆邻接表
邻接表表示法code：
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<bool> vis;
vector<int> adj[n+1];
bool find_edge(int u, int v) {
for (int i = 0; i < adj[u].size(); ++i) {
if (adj[u][i] == v) {
return true;
}
}
return false;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = true;
for (int i = 0; i < adj[u].size(); ++i) dfs(adj[u][i]);
}
int main() {
cin >> n >> m;
vis.resize(n + 1, false);
adj.resize(n + 1);
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
}
return 0;
}
3，链式前向星：
本质上是用链表实现的邻接表，核心代码如下：
// head[u] 和 cnt 的初始值都为 -1
void add(int u, int v) {
next[++cnt] = head[u]; // 当前边的后继
head[u] = cnt; // 起点 u 的第一条边
to[cnt] = v; // 当前边的终点
}
// 遍历 u 的出边
for (int i = head[u]; ~i; i = next[i]) { // ~i 表示 i != -1
int v = to[i];
}
代码：
#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector<bool> vis;
vector<int> head, next, to;
void add(int u, int v) {
next.push_back(head[u]);
head[u] = to.size();
to.push_back(v);
}
bool find_edge(int u, int v) {
for (int i = head[u]; ~i; i = nxt[i]) { // ~i 表示 i != -1
if (to[i] == v) {
return true;
}
}
return false;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = true;
for (int i = head[u]; ~i; i = next[i]) dfs(to[i]);
}
int main() {
cin >> n >> m;
vis.resize(n + 1, false);
head.resize(n + 1, -1);
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
add(u, v);
}
return 0;
}
4，十字链表
5，邻接多重表表示
6，直接存边：
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int u, v;
};
int n, m;
vector<Edge> e;
vector<bool> vis;
bool find_edge(int u, int v) {
for (int i = 1; i <= m; ++i) {
if (e[i].u == u && e[i].v == v) {
return true;
}
}
return false;
}
void dfs(int u) {
if (vis[u]) return;
vis[u] = true;
for (int i = 1; i <= m; ++i) {
if (e[i].u == u) {
dfs(e[i].v);
}
}
}
int main() {
cin >> n >> m;
vis.resize(n + 1, false);
e.resize(m + 1);
for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v;
return 0;
}