教程集 > Golang编程 > golang教程 > 正文数据结构-图(下)-golang

数据结构-图(下)-golang

发布时间：2022-03-05 编辑：jiaochengji.com

教程集为您提供数据结构-图(下)-golang等资源，欢迎您收藏本站，我们将为您提供最新的数据结构-图(下)-golang资源

之前总结了图的上篇大部分是基本概念，今天把图的应用有关算法设计问题总结一下。

1最小生成树问题

一个连通图的生成树包含图的所有顶点，并且只含尽可能少的边。对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

对于一个带权连通无向图G= (V, E)，生成树不同，每棵树的权（即树中所有边上的权值之和也可能不同）。设R为G的所有生成树的集合，若T为R中边的权值之和最小的那棵生成树，则T称为G的最小生成树（Minimum-Spanning-Tree, MST）。

最小生成树具有以下特点：

最小生成树不是唯一的，即最小生成树的树形不唯一，R中可能有多个最小生成树。当图G中的各边权值互不相等时，G的最小生成树是唯一的;若无向连通图G的边数比顶点数少1，即G本身是一棵树时，贝ljG的最小生成树就是它本身。

</li><li>

最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。

</li><li>

最小生成树的边数为顶点数减1

</li></ol>

接下来，总结两种算法，我们需要掌握算法的本质含义和基本思想，并能够手工模拟实现算法步骤。

Prim算法

Prim算法的执行非常类似于寻找图的最短路径的Dijkstra算法。

【算法模拟过程】

可以说，Prim算法是针对点的操作，每次加入树中的是点(通过边的权值比较找点)

【算法步骤描述】

【算法实现】

<pre style="margin-top:0px;margin-bottom:0px;padding:1em 1em 1em 0px;max-width:1000%;white-space:normal;"><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">package main</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">import (</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> "fmt"</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> "bufio"</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> "os"</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">const N=510 // 1≤n≤500</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">const M=100010 // 1≤m≤10^5 , 稠密图，邻接矩阵存储</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">const MaxDist = N*10000*2 // 图中涉及边的边权的绝对值均不超过10000</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">var (</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> reader=bufio.NewReader(os.Stdin)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> writer=bufio.NewWriter(os.Stdout)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> n,m int // 第一行包含两个整数n和m。</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> u,v,w int // 接下来m行，每行包含三个整数u，v，w，表示点u和点v之间存在一条权值为w的边。</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> g [N][N]int // 稠密图，邻接矩阵存储</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> dist [N]int // 节点和现有生成树节点集合的距离，这一点比较特殊！！</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> st[N]bool // 是否已加入生成树</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">// prim 返回最小生成树权值</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">//</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">// prim 算法：</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">// 1. 从其中一点开始，加入最小生成树</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">// 2. 从尚未加入树的节点中选择和已选中集合距离最小的点加入到生成树。如果其他点都不可达，则不存在最小生成树。</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">// 3. 重复第2步，直到所有点加入树；</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">// </code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">func prim() int{</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for i:=1;i<=n;i {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> dist[i] = MaxDist</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> res:=0</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for i:=1;i<=n;i {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> t:=-1</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 1. 寻找离集合距离最小的点t</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for j:=1;j<=n;j {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if !st[j] && (t==-1 || dist[t] > dist[j]) {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> t = j</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 非第一个点，且找不到关联边</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if i>1 && dist[t] == MaxDist {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> return -1</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 2. 将节点t加入集合，并统计权值</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> st[t] = true</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if t>1{</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 从第二个点开始统计权值</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> res = dist[t]</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 3. 新加入点t，更新一下其他所有点离集合的距离，以便下次循环查找</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for j:=1;j<=n;j {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if !st[j] && dist[j] > g[t][j]{</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> dist[j] = g[t][j]</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> return res</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">func main(){</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> fmt.Fscan(reader, &n, &m)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> //初始化邻接矩阵</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for i:=1;i<=n;i {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> g[1][i] = MaxDist</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for i:=2;i<=n;i {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> copy(g[i][:], g[1][:])</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for i:=0;i<m;i {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> fmt.Fscan(reader, &u,&v,&w)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if g[u][v] > w {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 无向边，即双向边</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> g[u][v] , g[v][u] = w,w</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> res:=prim()</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if res==-1{</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> fmt.Println("impossible")</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }else{</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> fmt.Println(res)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code></pre>

Kruskal算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal（克鲁斯卡尔）算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

【算法模拟过程】

【算法过程描述】

【算法实现】

使用golang算法改写克鲁斯卡尔算法还未完成，大家可以自行搜索C实现方法。

2
最短路径问题

当图是带权图时，把从一个顶点V0到图中其余任意一个顶点Vi的一条路径（可能不止一条）所经过边上的权值之和，定义为该路径的带权路径长度，把带权路径长度最短的那条路径称为最短路径。

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图G的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可通过经典的Dijkstra（迪杰斯特拉）算法求解；二是求每对顶点问的最短路径，可通过Floyd（弗洛伊德）算法来求解。

Dijkstra算法

通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。

</li><li>

此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。

</li><li>

初始时，S中只有起点s；U中是除s之外的顶点，并且U中顶点的路径是”起点s到该顶点的路径”。然后，从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。然后，再从U中找出路径最短的顶点，并将其加入到S中；接着，更新U中的顶点和顶点对应的路径。… 重复该操作，直到遍历完所有顶点

</li></ul>

【算法过程】

初始时，S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为”起点s到该顶点的距离”[例如，U中顶点v的距离为(s,v)的长度，然后s和v不相邻，则v的距离为∞]。

</li><li>

从U中选出”距离最短的顶点k”，并将顶点k加入到S中；同时，从U中移除顶点k。

</li><li>

更新U中各个顶点到起点s的距离。之所以更新U中顶点的距离，是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，(s,v)的距离可能大于(s,k) (k,v)的距离。

</li><li>

重复步骤(2)和(3)，直到遍历完所有顶点。

</li></ol>

【算法操作过程】

Dijsktra算法是基于贪心策略实现的。

【算法实现】

<pre style="margin-top:0px;margin-bottom:0px;padding:1em 1em 1em 0px;max-width:1000%;white-space:normal;"><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">package main</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">import (</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> "fmt"</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">const MAXVEX int = 9</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">const MAXWEIGHT int = 1000</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">//shortTablePath存放着V0到Vx某节点的最短路径</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">var shortTablePath = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">func main() {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph := NewGraph()</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var TablePathMin int //存放shortTablePath中,未遍历的最小结点的值</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var Vx int //存放shortTablePath中,未遍历的最小结点的下标</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var isgetPath [MAXVEX]bool //记录结点是否已经找到v0到vx的最小路径</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> // 获取v0这一行的权值数组</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for v := 0; v < len(graph); v {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> shortTablePath[v] = graph[0][v]</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> shortTablePath[0] = 0</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> isgetPath[0] = true</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> //遍历v1 ~ v8</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for v := 1; v < len(graph); v {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> TablePathMin = MAXWEIGHT</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> //找出shortTablePath中,未遍历的最小结点的值</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for w := 0; w < len(graph); w {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if !isgetPath[w] && shortTablePath[w] < TablePathMin {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> Vx = w</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> TablePathMin = shortTablePath[w]</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> isgetPath[Vx] = true</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for j := 0; j < len(graph); j {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> if !isgetPath[j] && TablePathMin graph[Vx][j] < shortTablePath[j] {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> shortTablePath[j] = TablePathMin graph[Vx][j]</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> fmt.Println("遍历完V", v, "后:", shortTablePath)</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> //输出</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> for i := 0; i < len(shortTablePath); i {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> fmt.Println("V0到V", i, "最小路径:", shortTablePath[i])</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> }</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">
</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">//该算法,第一次先将V0的节点连接的权值存入shortTablePath,没连接的,用MAXWEIGHT表示.</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">func NewGraph() [MAXVEX][MAXVEX]int {</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var graph [MAXVEX][MAXVEX]int</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v0 = [MAXVEX]int{0, 1, 5, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v1 = [MAXVEX]int{1, 0, 3, 7, 5, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v2 = [MAXVEX]int{5, 3, 0, MAXWEIGHT, 1, 7, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v3 = [MAXVEX]int{MAXWEIGHT, 7, MAXWEIGHT, 0, 2, MAXWEIGHT, 3, MAXWEIGHT, MAXWEIGHT}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v4 = [MAXVEX]int{MAXWEIGHT, 5, 1, 2, 0, 3, 6, 9, MAXWEIGHT}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v5 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, 7, MAXWEIGHT, 3, 0, MAXWEIGHT, 5, MAXWEIGHT}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v6 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 3, 6, MAXWEIGHT, 0, 2, 7}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v7 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 9, 5, 2, 0, 4}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> var v8 = [MAXVEX]int{MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, MAXWEIGHT, 7, 4, 0}</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[0] = v0</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[1] = v1</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[2] = v2</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[3] = v3</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[4] = v4</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[5] = v5</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[6] = v6</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[7] = v7</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> graph[8] = v8</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;"> return graph</code><code style="padding:0px;max-width:1000%;text-align:left;white-space:pre;font-family:Consolas, 'Liberation Mono', Menlo, Courier, monospace;">}</code></pre>

上述代码所需要的graph图

3拓扑排序

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：①每个顶点出现且只出现一次。②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径

【算法步骤】

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

从AOV网中选择一个没有前驱的顶点并输出。

</li><li>

从网中删除该顶点和所有以它为起点的有向边。

</li><li>

重复1和2，直到当前的AOV网为空或当前网中不存在元前驱的顶点为止

</li></ol>

每次选择一个入度为0，即没有前驱的结点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到的拓扑排序结果为{1，2，3，4，5}。

我们一个具体问题来实现以下

您可能感兴趣的文章：
数据结构和算法(Golang实现)(28)查找算法-AVL树
 数据结构和算法(Golang实现)(1)简单入门Golang-前言
 数据结构和算法(Golang实现)(7)简单入门Golang-标准库
 数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法
 数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
 解剖Go语言map底层实现
 GO--接口开发，空结构体如何返回一个空数组
 Golang常见数据结构-可变长数组
 Golang笔记——结构体
 golang基础教程

上一篇：go那些事儿|defer必掌握知识下一篇：golang异或字符串XOR

[关闭]

数据结构-图(下)-golang

最近更新

浏览排行