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

定义

图中的元素被称为顶点(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.
生成森林:由若干个有向树组成。

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注