大话数据结构(第七章 图)

图(Graph)是由定点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V表示图中顶点的集合,E是图G中边的集合。

注意:线性表中的数据元素叫元素,树中将数据元素叫做节点,在图中数据元素,我们称之为顶点(Vertex)。

  线性表妹有元素叫做空表,树没有节点叫做空树,但是在图结构中,不允许没有顶点,强调了顶点集合V有穷非空。

  线性表中,相邻的元素之间具有线性关系,树结构中,相邻两层的节点具有层次关系,而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系可以用边来表示。

1、各种图的定义

  无向边(Edge):用无序偶对(Vi,Vj)表示,Vi,Vj表示顶点。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图(Undirected graphs)。

  有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称弧(Arc),起点叫做弧尾,终点是弧头。

  (注意,无相边用小括号表示,有向边用尖括号表示)

  简单图:不存在顶点到自身的边,且一条边不重复出现。

  无向完全图:任意两个顶点都存在边的无向图;

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

  稀疏图:有很少边或弧的图(模糊概念)

  稠密图:不是稀疏图的图(模糊概念)

  权(weight):与图的边或弧相关的数

  网(Network):带权的图;

  子图(Subgraph):假设两个图G=(V,{E})和G’=(V',{E'}),如果V包含于V,E’包含于E,则G’为G的子图。

  邻接点(Adjacent):无向图中有边相连的两个顶点,互为邻接点;

  顶点v的度(Degree):与v相关联的边的数目,记为TD(v);

  入度(InDegree):以定点v为头的弧的数目;

  出度(OutDegree):以定点v为头的弧的数目;

  无向图中从定点v到顶点v’的路径是一个顶点序列;

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

  第一个定点到最后一个顶点相同的路径称之为回路或者环;???

  序列中顶点不重复出现的路径称为简单路径,除了第一个定点和最后一个顶点外,其余定点不重复出现的回路,称为简单回路或简单环。

  在无向图中,如果从定点v到顶点v’有路径,则称v到v’是连通的,如果对于图中任意两个顶点,都是连通的,则该图为连通图;

  无向图中极大连通子图称为连通分量。(是子图;子图连通;子图含有极大顶点数;具有极大顶点数的连通子图包含依附于这些顶点的所有边)

  有向图中,任意两个不同的顶点之间存在正反路径,则该图为强连通图;

。。。

(图的定义以及术语真。。。特么多!)

  总结一下:按照有无向分为无向图和有向图,无向图由定点和边组成,有向图由顶点和弧组成,弧有弧尾和弧头组成。

  稠密图、稀疏图、完全图、有向完全图、简单图、邻接点、

  路径回到起点的叫做环,不重复的叫简单路径,有向的称强连通图,图中有子图,子图极大联通称为连通分量。

  无向图中连通n个顶点n-1条边叫做生成树,有向图一个顶点入度为0其它为1叫做有向树,一个有向图由若干棵树组成则是森林。

2.图中的存储结构

  图的结构很复杂,任意两点都可能有联系;

  存储方案:

  1、邻接矩阵(Adjacency Matrix):用两个数组表示图,一维装顶点信息,二维数组(邻接矩阵)存储图中边或者弧的信息。

  顶点不分大小,由一个一维数组存储;

  边用二维数组存储;

  设图G有n个顶点,则邻接矩阵是一个n*n的方阵,定义为:

    arc[i][j] = 若(vi,vj)存在,值weight1,否则0.

  对于无向图来说,每一个边对应邻接矩阵中,两个顶点正反两个值,因此这个邻接矩阵式一个对称矩阵。

  通过矩阵我们可以很容易判断图中的一些信息:比如两个顶点有无边,一个顶点的度,邻接点寻找。

  

  2、邻接表:如果边过少,那么邻接矩阵对空间有浪费

  顶点用一个一维数组表示,每个顶点还存储指向第一个邻接点的指针;

  每一个顶点的邻接点构成一个线性表,使用单链表存储。

  3、十字链表:对于有向图,邻接表有缺陷,不能同时处理出度入度问题,十字链表结合邻接表盒逆邻接表,处理有向图;

  顶点加两个指针,一个指向入边表第一个节点,一个指向出边表第一个节点;

  4、邻接多重表。。。忘记保存

  5、边集数组

3、图的遍历

  深度优先

  广度优先

4、最小生成树

  普利姆(Prim)算法

  克鲁斯卡尔(Kruskal)算法

5、最短路径

  迪杰斯特拉算法:。。。

  Floyd佛洛依德算法

6、拓扑排序

  在一个表示工程的有向图中,顶点表示活动,弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网。

  设G=(V,E)是一个具有n个顶点的有向图,V中定点序列v1,v2,。。。,vn,满足若从定点vi到vj有一条路径,且在定点vi必在定点vi之前,则我们称这样的定点序列为一个拓扑序列。

  所谓的拓扑排序,其实就是对一个有向图构造拓扑序列的过程。

  拓扑排序算法:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,重复此步骤,直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

7、关键路径

  AOE网

  关键路径算法

  

  

原文地址:https://www.cnblogs.com/cwyblogs/p/8317167.html