YuriCode
0%

图

发表于 更新于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

图

在离散数学中，图（英语：graph）是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作节点或顶点（vertex, node, point），节点间的相关关系则称作边。在描绘一张图的时候，通常用一组点或小圆圈表示节点，其间的边则使用直线或曲线。

建图

邻接矩阵建图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int n;
const int N = 100;
int g[N][N];

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u][v] = w;	
		// g[v][u] = w;
	}
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

邻接表存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef pair<int, int> PII;
int n, m;
vector<vector<PII>> g;

void solve() {
	cin >> n >> m;
	g.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
//		g[v].push_back({u, w});
	}
}

链式前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, m;
const int N = 1e5 + 10, M = N * 2;

// h存的是表头，e存的是每一个节点的值，ne存的是每一个节点的下一个节点的下标
int h[N], e[M], ne[M], idx;

// 插入一条 a -> b 的边
void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
int n, m;

void solve() {
	// 初始化 	
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
}

图的遍历

dfs遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int u, vector<bool>& vis) {
	vis[u] = true;
	cout << u << " ";
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if (!vis[v]) dfs(v, vis);
	}
}

void dfs(int u) {
	vis[u] = true;
	cout << u << " ";
	for (int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if (!vis[v]) dfs(v);
	}
}

bfs遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void bfs(int x, vector<bool>& vis) {
	queue<int> q;
	q.push(x);
	vis[x] = true;
	while (!q.empty()) {
		int u = q.front();
		cout << u << " ";
		q.pop();
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			if (!vis[v]) {
				vis[v] = true;
				q.push(v);
			}
		}
	}
}

void bfs(int x){
	queue<int> q;
	q.push(x);
	vis[x] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		cout << u << ' ';
		for (int i = h[u]; i != -1; i = ne[i]) {
			int v = e[i];
			if (!vis[v]) {
				vis[v] = true;
				q.push(v);
			}
		}
	}
}

拓扑序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 有向图的拓扑序列
// 按照拓扑序排好之后所有边都是从前指向后的
// 有向无环图一定存在一个拓扑序列，这样的图也被称为拓扑图

// 入度: 有多少条边指向自己
// 出度：有多少条边从自己这出去

// 所有入度为 0 的点都可以排在前面
// 存入queue

int n, m;
vector<vector<int>> g;
// d 数组存入度
vector<int> d;
vector<int> ans;

void bfs() {
	queue<int> q;
	for (int i = 1; i <= n; i++) {
		if (d[i] == 0) {
			q.push(i);
			ans.push_back(i);
		}
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = 0; i < g[u].size(); i++) {
			int v = g[u][i];
			d[v]--;
			if (d[v] == 0) {
				q.push(v);
				ans.push_back(v);
			}
		}
	}
	if (ans.size() == n) {
		for (auto x : ans) {
			cout << x << ' ';
		}
		cout << endl;
	} else {
		cout << -1 << endl;
	}
}

void solve() {
	cin >> n >> m;
	g.resize(n + 1);
	d.assign(n + 1, 0);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		d[v]++;
	}
	bfs();
}

经典例题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m;
int ans[N];

vector<int> g[N];

void dfs(int x, int d) {
	if (ans[x]) return;
	ans[x] = d;
	for (int i = 0; i < g[x].size(); i++) {
		dfs(g[x][i], d);
	}
}

void solve() {
	// 反向建边
	// 从n -> 1, 较大的数可以到哪个数，那么这个数可以到的最大的数就是这个较大数
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		g[v].push_back(u);
	}
	for (int i = n; i >= 1; i--) dfs(i, i);
	for (int i = 1; i <= n; i++) cout << ans[i] << " ";
	cout << endl;
}

signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}