本文摘要：前言： 图盘算在数据科学中占据了很重要的职位，例如内存盘算大数据框架Spark的数据工具就是接纳图盘算的方式； 旅游大数据中游客最佳门路选择也是接纳图盘算，等等。一、图的相关观点1、图的界说 图是由极点和边组成的荟萃，通常用 G = ( V , E )来表现，其中V是所有极点组成的荟萃，而E代表所有边所组成的荟萃。

前言： 图盘算在数据科学中占据了很重要的职位，例如内存盘算大数据框架Spark的数据工具就是接纳图盘算的方式； 旅游大数据中游客最佳门路选择也是接纳图盘算，等等。一、图的相关观点1、图的界说 图是由极点和边组成的荟萃，通常用 G = ( V , E )来表现，其中V是所有极点组成的荟萃，而E代表所有边所组成的荟萃。

图的种类有2种：一种是无向图，一种是有向图，无向图以（V1 , V2）表现其边，而有向图以< V1,V2>表现其边2、无向图 无向图是一种边没有偏向的图，即同边的两个极点没有序次关系，例如(V1,V2)与(V2,V1)代表的是相同的边，如图所示：V = {A,B,C,D,E}E = {(A,B),(A,E),(B,C),(B,D),(C,D),(C,E),(D,E)}接下来先容无向图的重要术语：（1）完全图：在“无向图”中，N个极点正好有N(N-1)/2条边，则称为“完全图”，如图所示（2）路径：对于从极点Vi到Vj的一条路径，是指由所经由极点组成的一连数列，如上图中，V1到V5的路径有{(V1,V2)、(V2,V5)}以及{(V1,V2)、(V2,V3)、(V3,V4)、(V4,V5)}等等（3）简朴路径：除了起点和终点可能相同外，其它经由的极点都差别，也就是说如果一条路径上极点不重复泛起（4）路径长度：是指路径上所包罗边的总数，在上图中（V1,V2）、(V2,V3)、(V3,V4)、(V4,V5)是一条路径，其长度为4，且为一条简朴路径（5）回路：起始极点和终止极点为同一个点的简朴路径称为回路。例如上图：{(V1,V2)、(V2,V4)、(V4,V5)、(V5,V3)、(V3,V1)}的起点和终点都是A，所以是一个回路（6） 关联（Incident）：如果Vi与Vj相邻，我们则称(Vi,Vj)这个边关联极点Vi和极点Vj，关联极点V2的边有（V1,V2）、(V2,V4)、(V2,V5)、(V2,V3)（7）子图，例如：（8）相邻（adjacent）：如果（Vi,Vj）是E(G)中的一边，则称Vi和Vj相邻（9）连通分支（connected component）：在无向图中，相连在一起的最大子图，例如上图有2个联通分支（10）度数：在无向图中，一个极点所拥有边的总数为度数，例如上图V1的度数为43、有向图 有向图是一种每一条边都可是使用有序对<V1,V2>来表现图，而且<V1,V2>与<V2,V1>是表现两个偏向差别的边，而所谓<V1,V2>，是指V1为尾端指向为头部的V2，如下图：V = {A, B , C , D,E}E ={<A,B>,<B,C>,<C,D>,<C,E>,<E,D>,<D,B>}有向图的相关界说（1）完全图：具有n个极点且恰好有n*(n-1)个边的有向图，如下图所示：（2）路径：有向图从极点Vp到极点Vq的路径是指一串从极点所组成的一连有向序列（3）强连通：有向图中，如果每个成对极点Vi,Vj有直接路径（Vi和Vj不是同一个点），同时有另一条路径从Vj到Vi，则称此图为强连通图，如下图所示：（4）强连通分支：有向图中组成强连通的最大子图，在下图（a）是强连通，但(b)不是强连通，如图所示： 而图（b）中的强连通分支如图所示：（5）出度数：是指有向图中，以极点V为箭尾的边数（6）入度数：是指有向图中，以极点V为箭头的边数，如下图： V4的入度数是1，出度数是0 ； V2的入度数是4，出度数是1二、图的数据表现法1、毗邻矩阵法 图A有n个极点，以n x n的二维矩阵来表现，此矩阵的界说为：对于一个图G = (V,E)，假设有n个极点，n >= 1，则可以将n个极点的图，使用一个n x n的二维矩阵来表现，其中假设A(i , j) = 1，则表现图中有一条边( Vi , Vj)存在，反之， A(i , j) = 0，则不存在边A(i , j) 相关特性： （1）对于无向图而言，毗邻矩阵一定是对称的，而且对角线一定为0，有向图则纷歧定如此 （2）在无向图中，任一节点i的度数为 ，就是第 i “行”所有元素的和 ；在有 向图中，节点 i 的出度数为 ，就是第 i 行所有的元素的和，而入度数为 ，就是第j 列所有的元素的和（3）用毗邻矩阵法表现图共需n x n个单元 空间，由于无向图的毗邻矩阵一定具有对称关系，所以扣除对角线全部为零外，仅需存储上三角或下三角的数据即可，因此仅需n(n – 1 )/2的单元空间示例-1：使用毗邻矩阵表现下列“无向”图获得下列毗邻矩阵：而对于有向图，毗邻矩阵则纷歧定是对称矩阵。其中节点i的出度数为 ，就是第i行所有元素1的和，而入度数为 ，就是第j列所有元素1的和，如下图：示例-2：请以毗邻矩阵表现下面有向图：2、使用毗邻表方法表现矩阵 前面先容毗邻矩阵法，优点是借着矩阵的运算，可以有许多特此外应用。

要在图中加入新的边时候，这个表现法的插入与删除操作相当浅易。不外要思量到稀疏矩阵空间浪费的问题，另外如果盘算所有结点的度时候，其时间庞大度为O(n的平方) 因此可以思量更有效的方法，就是毗邻表法。这种表现方法就是将一个n行的毗邻矩阵，表现成n个链表，这种做法和毗邻矩阵相比节约空间，如盘算所有节点的度的时候，其时间庞大度为O(n+e)，缺点是有新边加入图中或从图中删除边时就要修改相关的链接，较为贫苦（1）无向图的毗邻表（2）有向图的毗邻表毗邻矩阵法和毗邻表法优缺点比力总结：（1）毗邻矩阵法优点：【1】实现简朴【2】盘算度数相当利便【3】要在图中加入新边时，这个表现法的插入与删除操作相当容易缺点：【1】如果极点与极点间的路径差不多时，容易造成稀疏矩阵而浪费存储空间【2】盘算所有极点的度时，其时间庞大度为O（n的平方）（2）毗邻表法优点：【1】和毗邻矩阵相比，比力节约空间【2】盘算所有节点度数时，其时间庞大度为O（n+e），比毗邻矩阵法盘算快缺点：【1】欲求入度数时，必须先求其反转线性表【2】新边的加入图中或从图中删除边时就要修改相关的链接，较为贫苦费时3、毗邻复合链表法 上面先容了两个图表现法是从图的极点出发，但如果要处置惩罚的是“边”则必须使用毗邻复合链表（或称为毗邻多叉链表）。毗邻复合链表是处置惩罚无向图的另一种方法。

毗邻复合链表的节点用于存放边的数据，其结构如下：其中相关特性说明如下： M：是记载该边是否被找过的一个位的字段 V1和V2：是所记载的边的起点与终点 LINK1：在尚有其它极点与 V1相连的情况下，此字段会指向下一个与V1相连的边节点，如果已经没有任何极点与V1相连时，则指向NULL LINK2：在尚有其它极点与 V2相连的情况下，此字段会指向下一个与V2相连的边节点，如果已经没有任何极点与V2相连时，则指向NULL 现在以“毗邻复合链表” 来表现下面的无向图：划分把极点和边的节点找出，生成的毗邻复合链表如下图所示：4、索引表格法 索引表格法，是一种用一维数组来按序存储与各个极点相邻的所有极点，并建设索引表格来记载各个极点在此一维数组中第一个与该极点相邻的位置，如下图： 规范：下图为欧拉七桥问题的示意图，A、B、C、D为4个岛，1、2、3、4、5、6、7为7座桥，现在以差别的数据结构形貌此图，试说明3种差别表现法欧拉七桥是一种复线图，它并不是图论中界说的 图，必须将其剖析，如下图所示：【1】毗邻矩阵Aij = 0表现极点i和极点j没有相邻的边Aij = 1表现极点i和极点j有相邻的边【2】毗邻表法【3】索引表格法。

本文关键词：算法,设计,数据结构,图,前言,图盘,算在,爱游戏官网,数据

本文来源：爱游戏官网-www.btykhb.com