0%
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
| '''
V(Vertex) 表示顶点集合
E(Edge) 表示边的集合
（v，w）属于 E ，E这条边 就包括 v w 两个顶点的连线。
< v,w > 属于 E ，v 指向 w 的有向边 ，属于E。
不考虑 重边 和 自回路。
G Graph
G(V,E)
邻接矩阵 G[N][N]
[
0 1 1
1 0 0
1 1 0
]
对角线为0 因为没有自回路。
对于无向图，可以省一半的空间。（只存 "下三角区域" 内容）
存放图 在一个长度为 [n (n + 1)] / 2 的1维数组中。
G[i][j] 对应的下标为
（ i*(i+1)/2 + j ） #看图可以知道。
网络 中 每条边有权重。
G[i][j] 的值，不再定义为1 ，而定义为 < vi,wj > 的权重即可。
问题：
在无权的这种无向图中，两个结点之间不连接，用 G[N][N] = 0 来表示。
在有向的图中（带权重），怎么表示不相连的 < vi,wj > 呢？
邻接矩阵（优点）
1】直观、
2】方便查看顶点之间是否存在边、
3】方便找任意顶点的"邻接点"。
4】方便计算任意顶点的度。
"度" 是指该点出发的边数，"入度"是指向该点的边数。
对于"无向图"邻接矩阵：行或列的 非0 元素个数 就是该顶点的度。
对于"有向图"邻接矩阵：行 非0 元素的个数是"出度"，列 非0 元素的个数是"入度"。
邻接矩阵（缺点）
1】点多边少的 稀疏图 浪费空间，只有堆任意顶点之间都有边的完全图 划算、
2】点多边少的 稀疏图 浪费时间，统计稀疏图边数特别浪费时间。
'''
'''
邻接表：
我们用G[N]为指针数组，对应矩阵每行一个链表，只存非零元素。
G[0] = node1 node3 （表示出了 01、03两条边）
G[1] = node5 node3 node0 node2 （表示出了 15、13、01、12四条边，其中01算重复出现的。）
...
G[N] = ...
邻接表 的表示是不唯一的。
邻接表一定要够稀疏才合算。其优缺点如下：
1】方便找任意顶点的所有"邻接点"
2】节约稀疏图空间
需要 N 个头指针、
（每条边存2遍）2E 个结点， 画一个4顶点5条边的图作相应邻接表，可以很容易理解。
每个结点至少2个域（数组中位置下标、指向下一个结点的指针、网还有权值）。
3】方便计算 "无向图" 任意顶点的度
对 "无向图" 出度 好算，但是 入度 需要哦构造 "逆邻接表"存指向自己的边 来计算，"逆邻接表"相当于在邻接矩阵以列为单位存。
4】不方便检查 任意一对顶点 是否存在边。
'''
|