图论1-2 图的表示

在有向图中，点对是有顺序的，如(v,u)和(u,v)是方向不同的边，但在无向图中，这两个点对是同一条边。

2.1 邻接矩阵（Adjacency Matrix）

使用一个二维的矩阵表示图，矩阵的行和列都为顶点编号，若顶点1,2直接有一条边，则矩阵的位置(1,2)置一。若图有权值weight，则则矩阵的位置(1,2)的值为weight。

优点

删除或添加一条边需要O(1)的时间，查询某两个顶点之间是否有边需要O(1)的时间。

缺点

需要O(υ2)的空间，添加一个顶点需要O(υ2)的时间。

代码实现

cpp

#include <iostream>
using namespace std;

int main() {
	// n is the number of vertices
	// m is the number of edges
	int n, m;
	cin >> n >> m ;
	int graph[n + 1][n + 1];
	for(int i = 0; i < m; ++i) {
		int u , v ;
		cin >> u >> v ;
		graph[u][v] = 1 ;
		graph[v][u] = 1 ;
	}
	return 0;
}

2.2 邻接表（Adjacency List）

每一个顶点对应一个链表，链表的头节点为顶点编号，后面的节点为相邻的顶点。权值可以保存在节点中。

优点

需要O(υ+ε)的空间，最坏的情况下（完全图）需要O(υ2)的空间。

缺点

查询某两个顶点之间是否有边需要O(υ)的时间。

代码实现

cpp

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

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

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");
	}
}

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

输出：

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

2.3 链式向前星

使用 head[i] 存储起点是 i 的第一条边的位置（在 to 和 next），to[i] 是第 i 条边的终点，next[i] 是第 i 条边的后继边的位置。

head[i] 初始化为 -1。

对于添加边的顺序 0->1, 1->2, 2->3, 0->2, 0->3 有以下存储状态。

index	0	1	2
head	0->3->4	1	2

index	0	1	2	3	4
to	1	2	3	2	3
next	-1	-1	-1	0	3

代码实现

cpp

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

int V, E;
vector<int> head, nxt, to;

void addEdge(int src, int dest) {
	nxt.emplace_back(head[src]);
	head[src] = to.size();
	to.emplace_back(dest);
}

void queryEdge(int src, int dest) {
	for (int i = head[src]; ~i; i = nxt[i]) {	// ~i -> i != -1
		if (to[i] == dest) {
			cout << "Edge from " << src << " to " << dest << " found." << '\n';
			return;
		}
	}
	cout << "Edge from " << src << " to " << dest << " not found." << '\n';
}

void printGraph() {
	for (int i = 0; i < V; ++i) {
		cout << i;
		for (int j = head[i]; ~j; j = nxt[j]) {	// ~i -> i != -1
			cout << "-> " << to[j];
		}
		printf("\n");
	}
}

int main() {
    V = 4, E = 5;
    head.resize(E, -1);

	addEdge(0, 1);
	addEdge(1, 2);
	addEdge(2, 3);
	addEdge(0, 2);
	addEdge(0, 3);
 
    printGraph();

    queryEdge(2, 1);
    queryEdge(0, 3);
 
    return 0;
}

输出：

0-> 3-> 2-> 1
1-> 2
2-> 3
3
Edge from 2 to 1 not found.
Edge from 0 to 3 found.

查询边需要 O(υ) 的时间，遍历整张图需要 O(υ+ε) 的时间，空间复杂度为 O(ε)。

2.4 使用哈希表表示

我们使用哈希表来保存每个顶点的相邻点。这里使用c++的无序集合 unordered_set，如果使用有序集合则查询时间会增加到 O(υ)。

cpp

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

struct Graph {
    int v;
    unordered_set<int>* adjList;

    Graph(int _v) : v(_v) {
    	adjList = new unordered_set<int>[v];
    }
};

void addEdge(Graph& graph, int src, int dest) {
	graph.adjList[src].emplace(dest);
	graph.adjList[dest].emplace(src);
}

void queryEdge(Graph& graph, int src, int dest) {
	auto it = graph.adjList[src].find(dest);
	if (it == graph.adjList[src].end()) {
		cout << "Edge from " << src << " to " << dest << " not found." << '\n';
	} else {
		cout << "Edge from " << src << " to " << dest << " found." << '\n';
	}
}

void printGraph(Graph& graph) {
	for (int i = 0; i < graph.v; ++i) {
		unordered_set<int> st = graph.adjList[i];
		cout << i;
		for (const auto& x : st)
			cout << "-> " << x;
		printf("\n");
	}
}

int main() {
    int V = 5;
    Graph graph(V);
	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);

    queryEdge(graph, 2, 1);
    queryEdge(graph, 0, 3);
 
    return 0;
}

输出：

0-> 4-> 3-> 1

1-> 4-> 0

2-> 3

3-> 4-> 2-> 0

4-> 3-> 1-> 0

Edge from 2 to 1 not found.

Edge from 0 to 3 found.

优点

查询是否有边需要 O(1) 的时间，添加一条边需要 O(1) 的时间。

缺点

不能表示含有重边的图。