数据结构与算法之图
图
基本概念
无向图和有向图
前一个不带箭头的就是无向图,后一个带尖头的就是有向图
子图
如果图G中包含G1,那么G1就是G的子图
完全图
在无向图中,若每对顶点之间都有一条边相连,则称该图为完全图。
在有向图中,若每对顶点之间都有两条有向边相连,则称该图为完全图。
连通分量
这个图中1和2分别是a和b的连通分量
图的存储
邻接矩阵
邻接表
图的遍历
图的遍历分为深度优先和广度优先
深度优先:首先从顶点出发,依次从顶点出发搜索它的每个邻接点,然后再以邻接点为顶点,以此访问邻接点的邻接点
此图的深度优先遍历顺序为:1,2,4,8,5,3,6,7
广度优先:首先从顶点出发,然后依次遍历与顶点相连接的点,然后再以这些点为顶点,依次遍历与他们相连的顶点
此图的广度优先遍历顺序为:1,2,3,4,5,6,7,8
图的最小生成树
普里姆算法:从顶点出发,依次寻找最小的边
克鲁斯卡尔算法:先找图中最小的边,然后依次寻找最小的边进行连接
AOV网络
用有向边表示活动之间开始的先后关系,这种有向图成为用顶点表示活动网络,简称AOV网络
拓扑序列
上图中的拓扑序列有:02143567,01243657,02143657,01243567
怎样的到拓扑序列
①首先寻找图中入度为零的定点为0,所以开始的顶点为零,然后去掉0
②去掉之后发现入度为零的点为2和1,此时从哪一个点开始都可以,所以此时会有多种拓扑序列012或者021
③以此类推,得到最后的拓扑序列
AOE网络
AOV网络中,如果边上的权表示完成该活动所需的时间,则成这样的AOV为AOE网络
关键路径(最长路径)的几个重要概念:
顶点j事件的最早发生时间:即从源点到顶点J的最长路径长度,记作Ve(j);
活动的最早开始时间:Ve(j)是以顶点j为起点的出边所表示的活动ai的最早开始时间,记作e(i);
顶点j事件的最迟发生时间:即在不推迟整个工程完成的前提下,一个事件允许最迟的发生时间,记作Vl(j);
活动ai的最迟开始时间:Vl(j)-(ai所需的时间),就是活动ai的最迟开始时间,其中j是活动的终点,记作l(i)。