数据结构和算法6-非线性-图-白红宇

数据结构和算法6-非线性-图

阅读量：4302 次

发布时间：2019-05-27

本文共 11084 字，大约阅读时间需要 36 分钟。

数据结构和算法系列共八篇

1.图概念

图是元素之间是多对多的关系，由顶点V集和边E集构成，因此图可以表示成G=(V,E)

图又分为：无向图和有向图。

1-1.无向图

上图就是无向图，我们可以说这张图中,在无向图中，边(u,v)和边(v,u)是一样的，因此只要记录一个就行了。也就是说方向是无关的。

有点集V={1,2,3,4,5,6}

边集E={(1,2),(1,5),(2,3),(2,5),(3,4),(4,5),(4,6)}。

1-2.有向图

有向图也很好理解，就是加上了方向性，顶点<u,v>之间的关系和顶点<v,u>之间的关系不同。例如你欠我的钱和我欠你的钱是万万不能混淆的。

下面介绍一些基本名称

弧头：箭头直线的顶点被称为终端点或弧头

弧尾: 无箭头一端的顶点通常被称为初始点或弧尾

入度：对于有向图中的一个顶点V来说,箭头指 V的弧的数量为V的入度, InDegree，记为 ID(V)

出度：箭头远离V的弧的数量为V的出度，OutDegree，记为OD(V)

路径：无论是无向图还是有向图，从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径

简单路径：没有重复顶点的路径称为简单路径。说白了，这一趟路里没有出现绕了一圈回到同一点的情况，也就是没有环。

权：在某些实际场景中，图中的每条边（或弧）会赋予一个实数来表示一定的含义，这种与边（或弧）相匹配的实数被称为权（如下图）

1-3.图分类

根据不同的特征，图又可分为完全图，连通图、稀疏图和稠密图：

1-3-1.完全图

完全图：各个顶点都与除自身外的其他顶点有关系，这样的无向图称为完全图

有向完全图: 满足此条件的有向图则称为有向完全图

具有n个顶点的完全图，图中边的数量为n(n-1)/2；而对于具有n个顶点的有向完全图，图中弧的数量为n(n-1)。

1-3-2.稀疏和稠密图

稀疏图: 图中具有很少的边（或弧），满足 e<nlogn

稠密图: 图中具有很多的边（或弧）e>nlogn

e 表示图中边（或弧）的数量，n 表示图中顶点的数量

1-3-3.连通图

图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通着的（不一定要直接连通、间接连通也可以）

大白话讲: 不存在孤立的顶点(子图)

其中:a无向图不是连通图。可以分解为3个"最大子图"，它们都满足连通图的性质，因此都是连通分量。

强连通图

有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图

与此同时，若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。

整个有向图虽不是强连通图，但其含有两个强连通分量。

2.存储结构

邻接矩阵 (二维数组顺序结构)

邻接表 (链表链表存储)

2-1.邻接矩阵

无向图：对角对称

假定图中顶点数为v,邻接矩阵通过长、宽都为v的二维数组实现，若稀疏图(图中边的数目较少)通过邻接矩阵，会浪费很多内存空间。

使用数组存储图时，需要使用两个数组，

一个数组存放图中顶点本身的数据（一维数组）

另外一个数组用于存储各顶点之间的关系（二维数组）。

不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：图和网

图: 包括无向图和有向图；
网: 是指带权的图，包括无向网和有向网;

2-2.链式

通常，图更多的是采用链表存储，具体的存储方法有3种，分别是邻接表、邻接多重表和十字链表。

这只介绍下邻接表,有兴趣可以自己查下。

2-2-1.邻接表

邻接表既适用于存储无向图，也适用于存储有向图

邻接点: 如果两个点相互连通，即通过其中一个顶点，可直接找到另一个顶点，则称它们互为邻接点。

邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的临界点。

为了便于管理这些链表，通常会将所有链表的头节点存储到数组中

3.图搜索

分两种方式

深度优先搜索: (DFS depth-fisrt-search)，类似tree的先序遍历，可以使用递归和栈方式实现

广度优先搜索: (BFS bredth-fisrt-search)，类似tree的层次遍历，可以使用队列实现

3-1.深度优先搜索

深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。

a. 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以，需要标记 V1 的状态为访问过；
b. 然后遍历 V1 的邻接点，例如访问 V2 ，并做标记，然后访问 V2 的邻接点，例如 V4 （做标记），然后 V8 ，然后 V5 ；
c. 当继续遍历 V5 的邻接点时，根据之前做的标记显示，所有邻接点都被访问过了。此时，从 V5 回退到 V8 ，看 V8 是否有未被访问过的邻接点，如果没有，继续回退到 V4 ， V2 ， V1 ；
d. 通过查看 V1 ，找到一个未被访问过的顶点 V3 ，继续遍历，然后访问 V3 邻接点 V6 ，然后 V7 ；
e. 由于 V7 没有未被访问的邻接点，所有回退到 V6 ，继续回退至 V3 ，最后到达 V1 ，发现没有未被访问的；
f. 最后一步需要判断是否所有顶点都被访问，如果还有没被访问的，以未被访问的顶点为第一个顶点，继续依照上边的方式进行遍历。

根据上边的过程，可以得到通过深度优先搜索获得的顶点的遍历次序为：

V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7

从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。

然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。

访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。

3-2.广度优先搜索

广度优先搜索类似于树的层次遍历。从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。

a. 假设 V1 作为起始点，遍历其所有的邻接点 V2 和 V3 ，
b. 以 V2 为起始点，访问邻接点 V4 和 V5 ，
c. 以 V3 为起始点，访问邻接点 V6 、 V7 ，
d. 以 V4 为起始点访问 V8 ，以 V5 为起始点，由于 V5 所有的起始点已经全部被访问，所有直接略过，
e. V6 和 V7 也是如此。

V1 为起始点的遍历过程结束后，判断图中是否还有未被访问的点，由于图 1 中没有了，所以整个图遍历结束。遍历顶点的顺序为：

V1 -> V2 -> v3 -> V4 -> V5 -> V6 -> V7 -> V8

4.最短路径

两类最短路径问题：

根据顶点树最少而计算出的最小值 (DFS)

根据权重计算出的最小值 (狄克斯特拉算法、弗洛伊德算法)

4-1.最少顶点

最少顶点，对应我们生活中示例，比如乘坐地铁或者公交里最少停站点类似。

使用深度优先搜索，即可解决问题。可以通过队列方式来实现。

4-2.狄克斯特拉算法

根据权重来计算出结果。对应我们生活中示例，比如交通的最短时间、最短路径等。

说明；

a.使用两个数组，一个数组S[]存处理过后的顶点，一个数组T[]存未处理过的顶点

b.比如从v1出发，那么就将v1方法到S[v1]中,而T为其他T[v2,v3,v4,v5,v6,v7,v8]，这时对应的权重为无穷大(∞)

c.从v1的出发能到达的顶点，的权重列出来作为临时权重，跟确定权重的权重比较，选择较小的，并设置其前一节点。

d.接着从T[v2,v3,v4,v5,v6,v7,v8]中找到确定权重最小的顶点放到S[]中，所以s变为S[v1,v2]

e.继续从v2出发找到能到达的顶带你，将其权重和和v2的确定权重权重相加得到临时权重，，跟确定权重的权重比较，选择较小的，并设置其前一节点。

f.接着从T[v3,v4,v5,v6,v7,v8]中找到确定权重最小的顶点放到S[]中，所以s变为S[v1,v2,v3]

重复e、f步骤

]

5.狄克斯特拉算法实现

5-1.顶点定义

根据上面分析的，写出实现代码，代码里有注释，不多解释了。

public class GNode {
       private Object data;    public GNode(Object data) {
           this.data = data;    }    public Object getData() {
           return data;    }    public void setData(Object data) {
           this.data = data;    }    @Override    public boolean equals(Object o) {
           if (this == o) {
               return true;        }        if (o == null || getClass() != o.getClass()) {
               return false;        }        GNode gNode = (GNode) o;        return Objects.equals(data, gNode.data);    }    @Override    public int hashCode() {
           return Objects.hash(data);    }    @Override    public String toString() {
           return "GNode{" + "data=" + data + '}';    }}

5-2.边定义

public class GEdge {
       private int wight;    private GNode from;    private GNode to;    public GEdge(int wight, GNode from, GNode to) {
           this.wight = wight;        this.from = from;        this.to = to;    }    public int getWight() {
           return wight;    }    public void setWight(int wight) {
           this.wight = wight;    }    public GNode getFrom() {
           return from;    }    public void setFrom(GNode from) {
           this.from = from;    }    public GNode getTo() {
           return to;    }    public void setTo(GNode to) {
           this.to = to;    }}

5-3.结果定义

public class GMapResult {
       private Object start;    private GNode previousNode;    private GNode selfNode;    private int weight;    public GMapResult() {
           this.weight = Integer.MAX_VALUE;    }    public GMapResult(Object start, GNode selfNode) {
           this.start = start;        this.selfNode = selfNode;        this.weight = Integer.MAX_VALUE;    }    public GMapResult(GNode selfNode) {
           this.selfNode = selfNode;        this.weight = Integer.MAX_VALUE;    }    public Object getStart() {
           return start;    }    public void setStart(Object start) {
           this.start = start;    }    public GNode getPreviousNode() {
           return previousNode;    }    public void setPreviousNode(GNode previousNode) {
           this.previousNode = previousNode;    }    public GNode getSelfNode() {
           return selfNode;    }    public void setSelfNode(GNode selfNode) {
           this.selfNode = selfNode;    }    public int getWeight() {
           return weight;    }    public void setWeight(int weight) {
           this.weight = weight;    }    @Override    public String toString() {
           return "{ previousNode=" + previousNode + ", selfNode=" + selfNode + ", weight=" + weight + '}';    }}

5-4.算法实现

public class Dijkstra {
       public static void shortestPath(Object start, Map
   
    > gNodeMap) {
           GNode startGNode = new GNode(start);        List
    
      sList = new ArrayList<>();        List
     
       tList = initTList(startGNode, gNodeMap);        Map
      
        gResultMap = initResultMap(startGNode, tList);        doshortestPath(startGNode, sList, tList, gNodeMap, gResultMap);        System.out.println("end");    }    private static void doshortestPath(GNode startNode, List
       
         sList, List
        
          tList, Map
         
          > gNodeMap, Map
          
            gResultMap) { while (!tList.isEmpty()) { GMapResult minWeightGNodeInT = getMinWeightGNodeInT(tList, gResultMap); int tmpMin = 0; if (minWeightGNodeInT.getWeight() == Integer.MAX_VALUE) { // 将起点从T中移除，加入到S中 tList.remove(startNode); sList.add(startNode); } else { // 从T中移除，加入到S中 tList.remove(minWeightGNodeInT.getSelfNode()); sList.add(minWeightGNodeInT.getSelfNode()); tmpMin = minWeightGNodeInT.getWeight(); } // 取出s里最后一个元素，对其所有的出边进行遍历 GNode sEndGNode = sList.get(sList.size() - 1); List
           
             sEndGNodeOutGedge = gNodeMap.get(sEndGNode); if (sEndGNodeOutGedge != null) { for (GEdge gEdge : sEndGNodeOutGedge) { GNode to = gEdge.getTo(); GMapResult oneResult = gResultMap.get(to); int tmpWeight = tmpMin + gEdge.getWight(); if (oneResult.getWeight() > tmpWeight) { oneResult.setPreviousNode(sEndGNode); oneResult.setWeight(tmpWeight); } } } } gResultMap.entrySet() .stream() .map(Map.Entry::getValue) .filter(item -> item.getSelfNode() != startNode) .collect(Collectors.toList()) .forEach(System.out::println); } private static GMapResult getMinWeightGNodeInT(List
            
              tList, Map
             
               gResultMap) { GNode gNode = tList.stream().min(Comparator.comparingInt(a -> gResultMap.get(a).getWeight())).get(); return gResultMap.get(gNode); } private static Map
              
                initResultMap(GNode startGNode, List
               
                 tList) { return tList.stream().collect(Collectors.toMap(item -> item, item -> new GMapResult(startGNode, item))); } private static List
                
                  initTList(GNode startGNode, Map
                 
                  > gNodeMap) { List
                  
                    tList = gNodeMap.entrySet() .stream() .map(Map.Entry::getValue) .flatMap(Collection::stream) .map(GEdge::getTo) .distinct() .collect(Collectors.toList()); tList.add(startGNode); return tList; }}

5-5.测试类

public class DijkstraTest {
       public static void main(String[] args) {
           Map
   
    > gNodeMap = genGraph();        Object start = "v1";        Dijkstra.shortestPath(start, gNodeMap);    }    private static Map
    
     > genGraph() {
           GNode gNode1 = new GNode("v1");        GNode gNode2 = new GNode("v2");        GNode gNode3 = new GNode("v3");        GNode gNode4 = new GNode("v4");        GNode gNode5 = new GNode("v5");        GNode gNode6 = new GNode("v6");        GNode gNode7 = new GNode("v7");        GNode gNode8 = new GNode("v8");        // 简单起见只用长度来演示        GEdge gEdge1to2 = new GEdge(3, gNode1, gNode2);        GEdge gEdge1to3 = new GEdge(5, gNode1, gNode3);        GEdge gEdge1to4 = new GEdge(6, gNode1, gNode4);        List
     
       gNode1OutEdges = Arrays.asList(gEdge1to2, gEdge1to3, gEdge1to4);        GEdge gEdge2to3 = new GEdge(1, gNode2, gNode3);        GEdge gEdge2to5 = new GEdge(7, gNode2, gNode5);        GEdge gEdge2to6 = new GEdge(4, gNode2, gNode6);        List
      
        gNode2OutEdges = Arrays.asList(gEdge2to3, gEdge2to5, gEdge2to6);        GEdge gEdge3to4 = new GEdge(1, gNode3, gNode4);        GEdge gEdge3to6 = new GEdge(2, gNode3, gNode6);        List
       
         gNode3OutEdges = Arrays.asList(gEdge3to4, gEdge3to6);        GEdge gEdge4to6 = new GEdge(3, gNode4, gNode6);        GEdge gEdge4to7 = new GEdge(5, gNode4, gNode7);        List
        
          gNode4OutEdges = Arrays.asList(gEdge4to6, gEdge4to7); GEdge gEdge5to8 = new GEdge(6, gNode5, gNode8); List
         
           gNode5OutEdges = Collections.singletonList(gEdge5to8); GEdge gEdge6to5 = new GEdge(2, gNode6, gNode5); GEdge gEdge6to7 = new GEdge(1, gNode6, gNode7); GEdge gEdge6to8 = new GEdge(9, gNode6, gNode8); List
          
            gNode6OutEdges = Arrays.asList(gEdge6to5, gEdge6to7, gEdge6to8); GEdge gEdge7to8 = new GEdge(5, gNode7, gNode8); List
           
             gNode7OutEdges = Collections.singletonList(gEdge7to8); Map
            
             > gMap = new HashMap<>(); gMap.put(gNode1, gNode1OutEdges); gMap.put(gNode2, gNode2OutEdges); gMap.put(gNode3, gNode3OutEdges); gMap.put(gNode4, gNode4OutEdges); gMap.put(gNode5, gNode5OutEdges); gMap.put(gNode6, gNode6OutEdges); gMap.put(gNode7, gNode7OutEdges); return gMap; }}

结果：

{ previousNode=GNode{data=v6}, selfNode=GNode{data=v7}, weight=7}{ previousNode=GNode{data=v7}, selfNode=GNode{data=v8}, weight=12}{ previousNode=GNode{data=v1}, selfNode=GNode{data=v2}, weight=3}{ previousNode=GNode{data=v2}, selfNode=GNode{data=v3}, weight=4}{ previousNode=GNode{data=v3}, selfNode=GNode{data=v4}, weight=5}{ previousNode=GNode{data=v6}, selfNode=GNode{data=v5}, weight=8}{ previousNode=GNode{data=v3}, selfNode=GNode{data=v6}, weight=6}