数据结构-图(下)-golang

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

1最小生成树问题

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

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

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

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

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

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

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

Prim算法

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

【算法模拟过程】

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

【算法步骤描述】

【算法实现】

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

Kruskal算法

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

【算法模拟过程】

【算法过程描述】

【算法实现】   

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

2
最短路径问题

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

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

Dijkstra算法

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

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

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

    【算法过程】

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

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

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

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

   
   

    【算法操作过程】

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

【算法实现】

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

上述代码所需要的graph图

3拓扑排序

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

【算法步骤】

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

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

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

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

   
   

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

    我们一个具体问题来实现以下拓扑排序：

问题描述：有一串数字1到5，按照下面的关于顺序的要求，重新排列并打印出来。要求如下：2在5前出现，3在2前出现，4在1前出现，1在3前出现。

    一般解决拓扑排序的方案是采用DFS-深度优先算法。先将排序要求声明成map（把map的key，value看作对顺序的要求，key应在value前出现），然后遍历1-5这几个数，将每次遍历取出的数在map中key查找是否存在，如果存在就按map中key，value的关系，放入结果数组中。再用刚map[key]获取的value去map中的key查找是否存在，如果存在就将新的key和value放入结果数组的一头一尾，以此类推，最终打印结果数组，应满足本题的要求。

package main
import (    "fmt"    "strconv")
//edge 要求的顺序var edge map[string]string = map[string]string{    "2": "5",    "3": "2",    "4": "1",    "1": "3",}
func main() {    //结果数组    var q []string = make([]string, 0)    //已访问数组    var visited []string = make([]string, 0)    for i := 0; i < 5; i++ {        tupusort(&q, &visited, strconv.Itoa(i))    }    // fmt.Printf("visited: %v \n", visited)    reverse(q)    fmt.Printf("topusort: %v \n", q)}
//拓扑排序-DFSfunc tupusort(q *[]string, visited *[]string, element string) {    if !isVisited(visited, element) {        *visited = append(*visited, element)        if edge[element] != "" {            tupusort(q, visited, edge[element])        }        *q = append(*q, element)    }}
//检查是否存在已访问的数组中func isVisited(visited *[]string, element string) bool {    var isVisited bool = false    for _, item := range *visited {        if item == element {            isVisited = true            break        }    }    return isVisited}
//反转数组顺序func reverse(arr []string) {    for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {        arr[i], arr[j] = arr[j], arr[i]    }}

    在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。

    在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

    上述这些经典的图算法应用，需要掌握其实现过程，至于算法实现明白关键代码如何实现即可，我推荐大家还是自己实现一下。

有疑问加站长微信联系（非本文作者）