图论1-5 转置图

5.1 介绍

将有向图的所有边的方向反转，即$(u,v)$变为$(v,u)$，这样的操作叫做图的转置。

5.2 代码

对于邻接矩阵，我们只需要将矩阵进行转置即可。
对于邻接表，我们需要遍历每个顶点和边，将每个边逆向。因此，时间复杂度为$O(\upsilon+\varepsilon)$

#include <bits/stdc++.h>
using namespace std;

void addEdge(vector<vector<int>>& graph, int u, int v) {
	graph[u].emplace_back(v);
}

void printGraph(vector<vector<int>>& graph, int n) {
	for (int i = 0; i < n; ++i) {
		cout << i;
		for (const auto& x : graph[i])
			cout << "-> " << x;
		printf("\n");
	}
}

void transposeGraph(vector<vector<int>>& graph, vector<vector<int>>& transpose, int n) {
	for (int i = 0; i < n; ++i) {
		for (const auto& x : graph[i]) {
			addEdge(transpose, x, i);
		}
	}
}

int main() {
	int n = 5;
	vector<vector<int>> graph(n);
	addEdge(graph, 0, 1);
	addEdge(graph, 0, 3);
	addEdge(graph, 0, 4);
	addEdge(graph, 1, 4);
	addEdge(graph, 2, 3);
	addEdge(graph, 3, 4);
	printGraph(graph, n);
	printf("\n");

	vector<vector<int>> transpose(n);
	transposeGraph(graph, transpose, n);
	printGraph(transpose, n);
	return 0;
}

输出：

0-> 1-> 3-> 4
1-> 4
2-> 3
3-> 4
4

0
1-> 0
2
3-> 0-> 2
4-> 0-> 1-> 3