当前位置: 首页 > 数据结构&&算法 > 正文

数据结构小结(八)图的使用

最小生成树

prim 算法

(1).输入:一个加权连通图,其中顶点集合为V,边集合为E;

(2).初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;

(3).重复下列操作,直到Vnew = V:

a.在集合E中选取权值最小的边,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并 且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);

b.将v加入集合Vnew中,将边加入集合Enew中; 4).输出:使用集合Vnew和Enew来描述所得到的最小生成树。

PS:时间复杂度为O(n^2),适合稠密图。

Kruskal 算法

这个算法思想不难,就是用代码实现费点事。

思想:适用贪心准则从剩下的边中选择不会产生回路且具有最小权值的边加入到生成树的边集中。

步骤:根据每一条边的权值,将边集排序

代码实现步骤: 1.建立邻接表或邻接矩阵

 

拓扑排序和关键路径

拓扑排序

有向图的弧可以看成是顶点之间的一种制约关系的一种描述。我们将顶点表示活动,弧表示活动优先关系的有向无环图,称为顶点表示活动的网,简称AOV 网,图中不允许出现回路。

对于一个AOV 网一般满足以下的情况的时候我们称之为拓扑序列。 (1)网中的所有顶点都在序列中。 (2)若顶点Vi到Vj存在一条关键路径,则在线性序列中,Vi一定存在Vj之前

构造一个拓扑序列的操作称之为拓扑排序。 实际上,拓扑排序就是离散数学中由某个集合上的一个偏序集上的一个偏序得到该集合上的一个全序操作。

代码实现步骤: 1.建立邻接表 2.初始化入度数组 3.开始拓扑 4.在拓扑的过程中依次打印出入度为0的结点

关键路径

一些概念

关键路径一般有如下的性质: (1)只有在某项顶点所代表的事件发生后,从该顶点发出的所有有向边所代表的活动才能开始;

(2)只有在进入某一顶点的各个有向边所代表的活动均已完成,该顶点所代表的事件才能发生;

源点

汇点

关键路径

思想以及步骤

关键路径的求解步骤:

1.根据拓扑排序求出每一个结点的最早发生时间和最迟发生时间

2.计算出每一个活动的最早开始时间和最晚发生时间

3.比较每一个活动的最早开始时间和最晚发生时间,如果相同这就是关键活动

这里我是分别求出了这4个数组的值。然后进行处理,确实比书上的逻辑复杂太多,仅仅就这个算法而言书上的逻辑与代码就很好了,我自己写的确实复杂了。

我写的代码在附录,有兴趣的可以看下,不过真心复杂难懂,自己看着都难受。

 

最短路径

前言

Dijkstra 算法

最短路径一般分为两种情况:

这个算法就是解决单源点最短路径的一个常用算法是Dijkstra ,说白一点就是求解一个点,到各个点 之间的最短路径的方法。

我尽量描述清楚这个算法的步骤吧。 存在一个集合S,存放源点逐步到达的顶点。

1.确定源点到它可以到达的顶点之间的距离。

2.选择一个最短距离,并将这个顶点入集合S。

3.将已经入过集合的顶点置为空,表示以后都不会选择它。

4.继续从1开始,直到所有顶点都被置空。

Floyd 算法

我还是尽量描述清楚这个算法的步骤吧。

前提:建立矩阵F,用于记录路径长度。能到达的路径都直接给于权值,不能到达的则设置无穷值。

这就是我们的F0矩阵,显然只是初始化了而已。

1.让顶点经过第一个顶点V0,然后比较路径(Vi,Vj)与路径(Vi,V0,Vj)的路径长度较短的一个。

2.往复这个步骤,然后经过n 次后就把n个顶点都考虑在路径中了。

3.最终得到的这个F矩阵就保存了所有的路径之间的关系了,注意中间斜对角线始终是0

这个代码比较好理解,就是循环多。

 

 

本文固定链接: http://zmrlinux.com/2015/12/20/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%b0%8f%e7%bb%93%ef%bc%88%e5%85%ab%ef%bc%89%e5%9b%be%e7%9a%84%e4%bd%bf%e7%94%a8/ | Kernel & Me

该日志由 root 于2015年12月20日发表在 数据结构&&算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 数据结构小结(八)图的使用 | Kernel & Me