数据结构之图的定义

数据结构与算法

图的定义

图： 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图的定义与线性表定义的对比：

• 线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中数据元素，我们则称之为顶点（Vertex）。
• 线性表中可以没有数据元素，称为空表。树中可以没有结点，叫做空树。但是在图结构中，不允许没有顶点。在定义中，若V是顶点的集合，则强调了顶点集合V有穷非空。
• 线性表中，相邻的数据元素之间具有线性关系，树结构中，相邻两层的结点具有层次关系，而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

1.1 各种图定义

无向边: 若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(vi,vj)来表示。
无向图: 如果图中任意两个顶点之间的边都是无向边，则称该图为无向图（Undirected graphs）。
对于无向图G1来说，G1=(V1,{E1})，其中顶点集合V1={A,B,C,D}；边集合E1={(A,B),(B,C),(C,D),(D,A),(A,C)}。

有向边： 若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc）。用有序偶来表示，vi称为弧尾（Tail），vj称为弧头（Head）。
有向图: 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图（Directed graphs）。
对于下有向图G2来说，G2=(V2,{E2})，其中顶点集合V2={A,B,C,D}；弧集合E2={,,,}。

无向边用小括号“()”表示，而有向边则是用尖括号“<>”表示。

简单图: 在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图。
无向完全图: 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

含有n个顶点的无向完全图有n(n-1)/2条边。

有向完全图: 在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

含有n个顶点的有向完全图有n×(n-1)条边。

对于具有n个顶点和e条边数的图，无向图$0≤e≤n(n-1)/2$，有向图$0≤e≤n(n-1)$。

稀疏图与稠密图： 有很少条边或弧的图称为稀疏图，反之称为稠密图。这里稀疏和稠密是模糊的概念，都是相对而言的。
权: 有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权（Weight）。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
网： 带权的图通常称为网（Network）。
子图： 设有两个图G=(V,{E})和G'=(V',{E'})，如果$V'∈V且E'∈E,则称G'为G的子图（Sub-graph）。

1.2 图的顶点与边间关系

邻接点: 对于无向图G=(V,{E})，如果边(v,v')∈E，则称顶点v和v'互为邻接点（Adjacent），即v和v'相邻接。

边(v,v')依附（incident）于顶点v和v'，或者说(v,v')与顶点v和v'相关联。

度： 顶点v的度（Degree）是和v相关联的边的数目，记为TD(v)。

对于有向图G=(V,{E})，如果弧∈E，则称顶点v**邻接到**顶点v'，顶点v'**邻接自**顶点v。弧和顶点v，v'相关联。以顶点v为
头弧的数目称为v的入度（InDegree），记为ID(v)；以v为尾的弧的数目称为v的出度（OutDegree），记为OD(v)；顶点v的度为TD(v)=ID(v)+OD(v)。

路径： 无向图G=(V,{E})中从顶点v到顶点v'的路径（Path）是一个顶点序列$(v=v_{i0},v_{i1},...,v_{im}=v')，其中(v_{i,j-1},v_{i,j})∈E，1≤j≤m$。如果G是有向图，则路径也是有向的，顶点序列应满足$<v_{i,j-1},v_{i,j}>∈E，1≤j≤m。$

路径的长度是路径上的边或弧的数目。

回路: 第一个顶点和最后一个顶点相同的路径称为回路或环（Cycle）。
简单路径: 序列中顶点不重复出现的路径称为简单路径。
简单回路: 除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

1.3 连通图相关术语

连通: 在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。
连通图: 如果对于图中任意两个顶点vi、vj∈V，vi和vj都是连通的，则称G是连通图（Connected Graph）。
连通分量: 无向图中的极大连通子图称为连通分量。连通分量的概念强调：

• 要是子图；
• 子图要是连通的；
• 连通子图含有极大顶点数；
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

强连通图: 在有向图G中，如果对于每一对vi、vj∈V、vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
强连通分量: 有向图中的极大强连通子图称做有向图的强连通分量。
下图左边的并不是强连通图，因为顶点A到顶点D存在路径，而D到A就不存在。右边就是强连通图，而且显然图2是图1的极大强连通子图，即是它的强连通分量。

连通图的生成树: 所谓的一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
比如下图中图1是一普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2或图3，就满足n个顶点n-1条边且连通的定义了。它们都是一棵生成树。

如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多于n-1边条，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2和图3，随便加哪两顶点的边都将构成环。不过有n-1条边并不一定是生成树，比如图4。

有向树: 如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一个有向树。

对有向树的理解比较容易，所谓入度为0其实就相当于树中的根结点，其余顶点入度为1就是说树的非根结点的双亲只有一个。

有向图的生成森林: 一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。