数据结构简单入门/复习（六）-图的知识介绍（C语言）

2022/1/24：更新为 Markdown 格式，修复挂的图，修复图对应描述。

定义

图中的元素被称为顶点（Vertex），用符号G表示图。
V是元素集合，A是顶点关系集合，G=(V, {A})
用<v, w>表示有向关系，代表从v到w的一段弧，v为弧尾，w为弧头。
用(v, w)表示无向关系，表示v与w间的边。
有向关系的是有向图，无向关系是无向图。

有向图G1	无向图G2

上图G1为有向图，G2为无向图。
G1 = ( V1, {A1}), V1 = {v1, v2, v3, v4}, A1 = {<v1, v2>, <v2, v3>, <v3, v4>, <v4, v2>}
G2 = ( V2, {A2}), V2 = {v1, v2, v3, v4}, A2={(v1, v3), (v1, v4), (v3, v4), (v2, v4)}

术语

用n表示图中顶点数目，用e表示边/弧数目，在不考虑顶点到自身的边/弧时：
1.无向图的e取值范围为0~(n(n-1))/2。
2.完全图(Completed graph)：e = (n(n-1))/2的无向图
3.有向图的e取值范围为0~n(n-1)。
4.有向完全图：e = n(n-1)的有向图。
5.稀疏图(Sparse graph)：e<nlogn的有向/无向图。
6.稠密图(Dense graph)：e>=nlogn的有向/无向图。

权(Weight)：边/弧的效率不同，例如从A地到B地有两条路，一条十分钟，一条半小时，这个过路的时间就是边的权。
网(Network)：带权的图
子图(Subgraph)：G1=(V, {E})的V与E都是另一个G2图V、E的子集，则G1为G2的子图。

邻接点(Adjacent)：对于无向图，一条边的两个点相邻接，互为邻接点。
依附(Incident)/相关联：对于无向图，边依附于顶点，或称边与顶点相关联。
度(Degree)：与顶点v相关联的边的数量，记为TD(V)。

邻接到：对于有向图的弧<v1, v2>，称v1邻接到v2。
邻接自：对于有向图的弧<v1, v2>，称v2邻接自v1
入度(InDegree)：以顶点v为头的弧的数目，称为v的入度，记为ID(v)。
出度(OutDegree)：以顶点v为尾的弧的数目，称为v的出度，记为OD(v)。
有向图的度等于入度+出度，即TD=ID+OD

路径(Path)：边/弧的序列（按顺序的多条边/弧），边的路径是无向的，弧的路径是有向的。
简单路径：路径中的顶点不重复（边/弧不出现交叉）。
回路/环(Cycle)：起点与终点是同一个顶点的路径。
简单回路/简单环：只有起点与终点重复。（不过对于一个回路来说，任何一个顶点都可以是起点，所以可以用路径不交叉来记忆）

连通：对于无向图，v1与v2间有路径，则v1与v2是连通的。
连通图(Connected Graph)：对于无向图，图中任意两点均连通。
连通分量(Connected Component)/极大连通子图：对于无向图，三个连通图构成的非连通图G，则三个连通图为图G的三个连通分量/极大连通子图。
强连通图：对于有向图，v1到v2、v2到v1均有路径，则为强连通图。
强连通分量：与连通分量的定义类似，对于有向图，三个强连通图组成的图G，这三个强连通图是图G的强连通分量。
生成树/极小连通子图：包含连通图中所有的n个顶点，但只有n-1条边（要点：连通图，n个顶点，n-1条边，缺一不可）。如果一个无向图，有n个顶点，n条边，必有环。
有向树：有向图的一个顶点入度为0，其余顶点入度均为1.
生成森林：由若干个有向树组成。