1. 云栖博客>
  2. 专辑列表>
  3. 专辑详情

简介:数据结构 有关图的一些算法,包括图的存储,图的最小生成树,图的最短路径等

  • 数据结构——图的十字链表表示法

    发布时间:2018-11-24 19:01:56 评论:0

    图的十字链表,添加,删除,出度,入度

  • 数据结构——图的深度遍历

    发布时间:2018-11-26 18:45:43 评论:1

    图的遍历方式有两种, 深度优先 广度优先 深度优先采用的是递归的方式来来实现,思想如下: 假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点),**则深度优先遍历可定义如下:首先访问出发点v,并将其标记为已访问过;然后依次从v出发搜索v的每个邻接点w。

  • 数据结构——图的广度遍历

    发布时间:2018-11-27 16:24:01 评论:0

    图的广度遍历和深度遍历思想不一样。后者是用递归的方法来实现的,这个是要借助队列来实现的。实现的基本思想如下:1、从图中某个顶点V0出发,并访问此顶点;2、从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点;3、重复步骤2,直到全部顶点都被访问为止。

  • 图的最小生成树——Kruskal算法

    发布时间:2018-12-02 00:41:52 评论:0

    Kruskal算法的思想如下 假设有n个顶点的连通图。首先先构造有顶点构成的集合0,每个顶点都是一个集合,不含有任何边。 在边找一个最小权值的边 判断这个边的俩个顶点是否来自于两个不同的集合,若是就将它俩归并为一个集合,然后将这个边添加到要构成的图的集合中。

  • 图的最小生成树——Prim算法

    发布时间:2018-12-14 12:43:32 评论:0

    Prim算法思想如下:首先将图的点分为两部分,一种是访问过的u,一种是没有访问过的v1:首先在访问过的顶点中找一条到u到v的一条权值最小的边2:然后将这条边中的v中的顶点添加到u中,直到边的个数=顶点数-1如下图所示,下面是prim算法的图示(原图)(a -1)(a -2)(a -3)(a -4) (a -5) (a -6) 算法的流程图如下: 代码如下:// // main.

  • 图的最短路径—— dijkstra算法

    发布时间:2018-12-15 00:32:25 评论:0

    算法的思想如下:规定一个 出发点,然后先初始化距离数组。数组中的每个下标就对应一个结点,每个数据项就是出发点到每个结点的距离。1:将一个集合分为两部分,一个是已经找过的结点U,一个是没有找到过的v2:在距离的数组中,没有访问过的结点中找一个权重最小的边,然后将这个结点添加到u中,并且以这个结点作为中间结点,来更新数组,判断条件是i到temp+temp到j 的距离是不是小于i到j的距离,若是,则就要更新。