什么是图？如何表示和实现？图又有那些基本的性质？常见的应用有哪些？
什么是图
图常用来建立多对多的关系，如社交网络等。那么用什么概念来说明这些关系呢？答案就是“顶点”跟“边”。
图的构成只有两种：顶点和边，二者即是用来表示关系的概念。
顶点
一个图内肯定不止一个顶点（Vertex），所以一般用 Ｖ 来表示顶点集合
边
同样，一个图内肯定不止一条边（Edge），所以一般用 E 来表示边的集合。需要注意的是，图分为有向图与无向图，所以边在这两种图中分别称作有向边（单行线，如$<v_1, v_2>$）与无向边（$(v1, v2)$）。
另外，在图内是不考虑重边和自回路的。
基本术语
与图相关的基本术语有很多，碰见一个记录一个：
- 无向图，图内所有的边都是无向边，对应的，若图内所有的边都是有向边，那这个图就是有向图
- 每一条边上赋予权值后，那么称这个图叫做“网络”，这个概念与互联网络是不一样的
- 完全图，图内所有顶点，任意两个顶点之间都有边
- 连通，如果从 V 到 W 存在一条（无向）路径，则称 V 和 W 是连通的
- 路径，V 到 W 的路径是一系列顶点${V, V_1, V_2, \dots, V_n, W}$的集合，其中任一对相邻顶点间都有图中的边。路径的长度是路径种的边数（如果带权，则是所有边的权重和）。如果 V 到 W 之间的所有顶点都不同，则称简单路径
- 回路，起点等于终点的路径
- 连通图，图中任意两顶点均连通
- 连通分量，无向图的极大连通子图，其中“极大”包含下面两个意思：
- 极大顶点数：再加一个顶点就不连通了
- 极大边数：包含子图种所有顶点相连的所有边
- 有向图中顶点 V 和 W 之间存在双向路径，则称 V 和 W 是强连通的
- 强连通图，有向图中任意两顶点均强连通
- 强连通分量，有向图的极大强连通子图
- 弱连通图，如果一个非强连通图，将其中所有的有向边改为无向边，得到的图为连通图，这样的图称为弱连通图
图的抽象数据类型描述
类型名称：图（Graph）
数据对象集：$G(V, E)$由一个非空的有限顶点集$V$和一个有限边集合$E$组成。
操作集：最大堆$H ∈ MaxHeap$，元素$item ∈ ElementType$，主要操作有：
- Graph Create()，建立并返回空图
- Graph InsertVertex(Graph G, Vertex v)，将 v 插入 G
- Graph InsertEdge(Graph G, Edge e)，将 e 插入 G
- void DFS(Graph G, Vertex v)，从顶点 v 出发深度优先遍历图 G
- void BFS(Graph G, Vertex v)，从顶点 v 出发宽度优先遍历图 G
- void ShortestPath(Graph G, Vertex v, int Dist[])，计算图 G 中顶点 v 到任意其他顶点的最短距离
- void MST(Graph G)，计算图 G 的最小生成树
图的表示
图的表示有多种方法，按照所要解决的问题的性质，用符合问题情况的表示方法来表示图，在解决问题是可以事半功倍，
下面只介绍两种常见的表示方法。
邻接矩阵
邻接矩阵本质上就是一个二维数组，用数组下标$0-N-1$代表$N$个顶点的编号，数组的元素的值表示两个顶点之间是否有边（若是网络，那么直接将数组元素的值修改为对应的权值即可），即有：
$G[i][j] =
\begin{cases}
1& 若<v_i, v_j>是G中的边\\
0& 否则
\end{cases}
$
值得注意的是，无向图的邻接矩阵一定是对称的。也就是说，无向图的邻接矩阵只需要存储一半即可。要解决这个问题，需要用到矩阵的压缩存储知识。
使用邻接矩阵表示图的优点有以下几点：
- 直观、简单、便于理解
- 方便检查任意一对顶点间是否存在边
- 方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
- 方便计算任一顶点的“度”（这里的度的概念与树是类似的，从该顶点发出的边数为“出度”，指向该点的边数为“入度”）
- 无向图：对应行（或列）非 0 元素的个数
- 有向图：对应行非 0 元素的个数是“出度”，对应列非 0 元素的个数是“入度”
邻接矩阵的缺点如下：
- 存储稀疏图（顶点多边很少）时有大量无效元素，极大浪费空间，但存储稠密图（特别是完全图）很合算
- 统计稀疏图中的边数效率很低
邻接表
由于邻接矩阵表示稀疏图浪费空间，为了解决这个问题对应出现的就是邻接表。
在邻接表中，$G[N]$为指针数组，对应矩阵每一行一个链表，只存非 0 元素，注意邻接表的表示并不唯一。
邻接表的特点：
- 方便找任一顶点的所有“邻接点”
- 节约稀疏图的空间，需要 N 个头指针 和 2E 个结点（每个结点至少 2 个域）
- 方便计算无向图任一顶点的度和有向图任一顶点的出度，但计算有向图任一顶点的入度比较麻烦，需要构造“逆邻接表”（存储指向自己的边）才能方便的计算入度
- 不便于检查任意一对顶点是否存在边
图的遍历
图里面遍历的概念与树是一致的，图的基本遍历方法有两种：深度优先搜索（Depth First Search，DFS）和广度优先搜索（Breath First Search，BFS）。根据应用场景的不同，两种遍历算法在不同场景下解决问题的难易程度也不一样。
DFS
DFS 算是树的先序遍历的推广，其伪码算法为：1
2
3
4
5
6void DFS(Vertex V) {
visited[V] = true; // 此结点标记为已访问
for( V 的每个邻接点 W) {
if(!visited[W]) DFS(W);
}
}
根据图的存储结构的不同，DFS 的时间复杂度也不同：
- 使用邻接表存储，时间复杂度为：$O(N + E)$
- 使用邻接矩阵存储，时间复杂度为：$O(N^2)$
BFS
BFS 算是树的层序遍历的推广，其伪码算法为：1
2
3
4
5
6
7
8
9
10
11
12
13void BFS(Vertex V) {
visited[V] = true;
Enqueu(V, Q);
while(!Isempty(Q)) {
V = Dequeue(Q);
for(V 的每个邻接点 W) {
if(!visited[W]) {
visited[W] = true;
Enqueue(W, Q);
}
}
}
}
同样，其时间复杂度也分两种情况：
- 使用邻接表存储，时间复杂度为：$O(N+E)$
- 使用邻接矩阵存储，时间复杂度为：$O(N^2)$
Homework
06-1 列出连通集
题目意思很明确，给定一个无向图，分别用 DFS 和 BFS列出其所有的连通集（其实就是连通分量，忘记是啥了，可以重新看下上面的概念）即可。之前姥姥在课上讲过，按照 DFS 的遍历过程，一个最外层的 DFS 的调用，就相当于访问了这个图的一个连通集。那么使用 DFS 在访问每个连通集是顺便输出当前所处连通集的所有元素即可，同理，BFS 也是一样的。
由于姥姥讲了图的两种存储方法，继续按部就班的按照姥姥给定的代码接着往下写：
邻接表
1 | /* notes: The adjacency list is built by head pointer, so the traversal sequences is not same as sample output. |
邻接矩阵
1 |
|
06-2 Saving James Bond - Easy Version
这道题目是难度降低后的简单版，按照姥姥给定的思路来写即可，这里使用 C++ 的部分功能来写可能会比较方便（用纯 C 也可以胜任，可能会稍微麻烦），如下：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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
const int maxn = 100 + 5;
struct node{
double x, y;
} coords[maxn];
int n;
double d;
bool visited[maxn] = {false};
bool firstjump(int v) {
return sqrt(pow(coords[v].x, 2) + pow(coords[v].y, 2)) - 7.5 <= d;
}
bool jump(int v, int w) {
return sqrt(pow(coords[v].x - coords[w].x, 2) + pow(coords[v].y - coords[w].y, 2)) <= d;
}
bool issafe(int v) {
return fabs(fabs(coords[v].x) - 50) <= d || fabs(fabs(coords[v].y) - 50) <= d;
}
bool DFS(int v) {
visited[v] = true;
bool flag = false;
if(issafe(v)) return true;
else {
for(int w = 0; w < n; w++) {
if(!visited[w] && jump(v, w)) {
flag = DFS(w);
if(flag) break;
}
}
}
return flag;
}
void save007() {
bool flag = false;
for(int v = 0; v < n; v++) {
if(!visited[v] && firstjump(v)) {
flag = DFS(v);
if(flag) break;
}
}
flag ? cout << "Yes" : cout << "No";
}
int main() {
cin >> n >> d;
for(int v = 0; v < n; v++) {
cin >> coords[v].x >> coords[v].y;
}
save007();
return 0;
}
/*
sample:
in:
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
out:
Yes
in:
4 13
-12 12
12 12
-12 -12
12 -12
out:
No
*/
06-3 六度空间
由于六度空间理论姥姥已经介绍过了，所以题目意思理解起来比较容易，按照姥姥的讲解，只需要稍稍修改 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
const int inf = 0x3fffffff;
int G[maxn][maxn], nv, ne;
bool visited[maxn];
void init() {
for(int i = 0; i < maxn; i++) {
for(int j = 0; j < maxn; j++) {
G[i][j] = inf;
}
}
}
int BFS(int v) {
memset(visited, false, sizeof(visited));
visited[v] = true;
int Queue[maxn], front = -1, rear = -1;
Queue[++rear] = v;
int count = 1, level = 0, last = v, tail;
while(front < rear) {
int first = Queue[++front];
for(int w = 1; w <= nv; w++) {
if(!visited[w] && G[first][w] != inf) {
Queue[++rear] = w;
visited[w] = true;
tail = w;
count++;
}
}
if(first == last) {
level++;
last = tail;
}
if(level == 6) break;
}
return count;
}
void sds() {
for(int i = 1; i <= nv; i++) {
int count = BFS(i);
printf("%d: %.2lf%%\n", i, (double)count / nv * 100.0);
}
}
int main() {
init();
scanf("%d %d", &nv, &ne);
int v1, v2;
for(int i = 0; i < ne; i++) {
scanf("%d %d", &v1, &v2);
G[v1][v2] = G[v2][v1] = 1;
}
sds();
return 0;
}
/*
samples:
in:
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
out:
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
*/
