如何将有向图转化为⽆向图_图论基础与图存储结构
1 前⾔
由于后续更新「⾯试专场」的好⼏篇⽂章都涉及到 图 这种数据结构，因此打算先普及⼀下 图 的相关理论⽀持，如果后⾯的相关内容有些点不太容易理解，可以查阅此篇⽂章。本⽂不建议⼀⼝⽓阅读完毕，可以先浏览⼀遍，在后续有需要的时候进⾏查阅即可。
2 图
图是数据结构中重要内容。相⽐于线性表与树，图的结构更为复杂。在线性表的存储结构中，数据直接按照前驱后继的线性组织形式排列。在树的结构中，数据节点以层的⽅式排列，节点与节点之间是⼀种层次关系。但是，在图的结构中数据之间可以有任意关系，这就使得图的数据结构相对复杂。
2.1 定义
定义：图(Graph)是由顶点的有穷⾮空集合和顶点之间边的集合组成，通常表⽰为：G(V，E)，其中，G表⽰⼀个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。
数组和链表
例如：图 2.1 所⽰图
在图 2.1 中，共有 V0，V1，V2，V3 这 4 个顶点，4 个顶点之间共有 5 条边。
注：
当线性表没有数据节点时，线性表为空表。树中没有节点时，树为空树。但是，在图中不允许没有顶点，但是可以没有边。
2.2 ⽆向边
⽆向边：若顶点 x 和 y 之间的边没有⽅向，则称该边为⽆向边(x,y)，(x,y) 与 (y,x) 意义相同，表⽰ x 和 y 之间有连接。
图 2.2 所⽰图中的边均为⽆向边。
2.3 有向边
有向边：若顶点 x 和 y 之间的边有⽅向，则称该边为有向边，与表⽰的意义是不同的，表⽰从 x 连接到 y ，x 称为尾，y 称为头。表⽰从y 连接到 x ，y 称为尾， x 称为头。
图2.3所⽰图中的边为有向边。
2.4 ⽆向图
⽆向图：若图中任意两个顶点之间的边均是⽆向边，则称该图为⽆向图。
图2.2所⽰图为⽆向图。
2.5 有向图
有向图：若图中任意两个顶点之间的边均是有向边，则称该图为有向图。
图2.3所⽰的图为有向图。
2.6 顶点与顶点的度
顶点的度：
顶点 V 的度是和 V 相关联的边的数⽬，记为TD(V)。
图 2.6 所⽰图中，V0 顶点的度为 3 。
⼊度：
以顶点v为头的边的数⽬，记为ID(V)。
图2.6所⽰图中，V0的⼊度为1。
出度：
以顶点 v 为尾的边的数⽬，记为 OD(V)。
图2.6所⽰图中，V0的出度为2。
顶点的度 = ⼊度 + 出度。
即 TD(V) = ID(V) + OD(V)。
邻接是两个顶点之间的⼀种关系。如果图包含(u,v)，则称顶点 v 与顶点 u 邻接。在⽆向图中，这也暗⽰了顶点 u 也与顶点 v 邻接。换句话说，在⽆向图中邻接关系是对称的。
2.8 路径
路径：在图中，依次遍历顶点序列之间的边所形成的轨迹。
例如：在图 2.8 中所⽰图中依次访问顶点 V0 、V3 和 V2 ，则构成⼀条路径。
3 完全图
完全图：每个顶点都与其他顶点相邻接的图。
⽆向完全图：在⽆向图中，如果任意两个顶点之间都存在边，则称该图为⽆向完全图。(含有n个顶点的⽆向完全图有(n×(n-1))/2条边)
图 3.1 所⽰的图为⽆向完全图。
有向完全图：在有向图中，如果任意两个顶点之间都存在⽅向互为相反的两条边，则称该图为有向完全图。(含有 n 个顶点的有向完全图有n×(n-1) 条边)
图3.2所⽰的图为有向完全图。
在⽆向图 G 中，如果从顶点 v 到顶点 v' 有路径，则称 v 和 v' 是连通的。 如果对于图中任意两个顶点 vi 、vj ∈E， vi，和vj都是连通的，则称 G 是连通图，否则图为⾮连通图。
例如：图4.1所⽰图，图中顶点A、B、C、D是连通的，但是其中任⼀顶点与顶点E或者顶点F之间没有路径，因此图4.1中所⽰的图为⾮连通图。
若添加顶点B与顶点F之间的邻接边，则图变为连通图，如图4.2所⽰：
5 数组存储
图的数组存储⽅式也称为邻接矩阵存储。图中的数据信息包括：顶点信息和描述顶点之间关系的边的信息，将这两种信息存储在数组中即为图的数组存储。
⾸先，创建顶点数组，顶点数组中存储的是图的顶点信息，采⽤⼀维数组的⽅式即可存储所有的顶点信息。存储图中边的信息时，由于边是描述顶点与顶点之间关系的信息，因此需要采⽤⼆维数组进⾏存储。
定义：设图 G 有 n 个顶点，则邻接矩阵是⼀个n X n的⽅阵A，定义为：
其中，或者(Vi , Vj,)表⽰顶点 Vi 与顶点 Vj 邻接。wi,j表⽰边的权重值。
例如：下图所⽰的⽆向图，采⽤数组存储形式如下。
注：图中的数组存储⽅式简化了边的权值为 1 。
⽆向图的数组存储主要有以下特性：
(1)顶点数组长度为图的顶点数⽬n。边数组为n X n的⼆维数组。(2)边数组中，A[i][j] =1代表顶点i与顶点j邻接，A[i][j] = 0代表顶
点i与顶点j不邻接。(3)在⽆向图中。由于边是⽆向边，因此顶点的邻接关系是对称的，边数组为对称⼆维数组。(4)顶点与⾃⾝之间并未邻接关系，因此边数组的对⾓线上的元素均为0。(5)顶点的度即为顶点所在的⾏或者列1的数⽬。例如：顶点V2的度为3，则V2所在⾏和列中的1的数⽬为3。
当图为有向图时，图的数组存储⽅式要发⽣变化。
例如：图5.2所⽰的有向图，采⽤数组存储形式如下。
有向图的数组存储主要有以下特性：
(1)顶点数组长度为图的顶点数⽬n。边数组为n X n的⼆维数组。(2)边数组中，数组元素为1，即A[i][j] = 1，代表第i个顶点与第j个顶
点邻接，且i为尾，j为头。 A[i][j] = 0代表顶点与顶点不邻接。(3)在有向图中，由于边存在⽅向性，因此数组不⼀定为对称数组。(4)对⾓线上元素为0。(5)第i⾏中，1的数⽬代表第i个顶点的出度。例如：顶点V1的出度为2，则顶点V1所在⾏的1的数⽬为2。(6)第j 列中，1的数⽬代表第j个顶点的⼊度。例如：V3的⼊度为1，则V3所在列中1的数⽬为1。
数组存储⽅式优点：
数组存储⽅式容易实现图的操作。例如：求某顶点的度、判断顶点之间是否有边(弧)、顶点的邻接点等等。
数组存储⽅式缺点：
采⽤数组存储⽅式，图若有n个顶点则需要n2个单元存储边(弧)，空间存储效率为O(n2)。 当顶点数⽬较多，边数⽬较少时，此时图为稀疏图，这时尤其浪费空间。
例如：图5.3所⽰的图，图中有 9 个顶点，边数为10，需要 9X9 的⼆维数组，⽽实际存储边信息空间只有10，造成空间浪费。
图5.3所⽰⽆向图的存储数组：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。