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

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<GNode, List<GEdge>> gNodeMap) {
        GNode startGNode = new GNode(start);
        List<GNode> sList = new ArrayList<>();
        List<GNode> tList = initTList(startGNode, gNodeMap);

        Map<GNode, GMapResult> gResultMap = initResultMap(startGNode, tList);

        doshortestPath(startGNode, sList, tList, gNodeMap, gResultMap);

        System.out.println("end");
    }


    private static void doshortestPath(GNode startNode, List<GNode> sList, List<GNode> tList,
                                       Map<GNode, List<GEdge>> gNodeMap, Map<GNode, GMapResult> 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<GEdge> 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<GNode> tList,
                                                   Map<GNode, GMapResult> gResultMap) {
        GNode gNode = tList.stream().min(Comparator.comparingInt(a -> gResultMap.get(a).getWeight())).get();
        return gResultMap.get(gNode);
    }

    private static Map<GNode, GMapResult> initResultMap(GNode startGNode, List<GNode> tList) {
        return tList.stream().collect(Collectors.toMap(item -> item, item -> new GMapResult(startGNode, item)));
    }

    private static List<GNode> initTList(GNode startGNode, Map<GNode, List<GEdge>> gNodeMap) {

        List<GNode> 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<GNode, List<GEdge>> gNodeMap = genGraph();
        Object start = "v1";
        Dijkstra.shortestPath(start, gNodeMap);
    }

    private static Map<GNode, List<GEdge>> 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<GEdge> 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<GEdge> gNode2OutEdges = Arrays.asList(gEdge2to3, gEdge2to5, gEdge2to6);

        GEdge gEdge3to4 = new GEdge(1, gNode3, gNode4);
        GEdge gEdge3to6 = new GEdge(2, gNode3, gNode6);
        List<GEdge> gNode3OutEdges = Arrays.asList(gEdge3to4, gEdge3to6);

        GEdge gEdge4to6 = new GEdge(3, gNode4, gNode6);
        GEdge gEdge4to7 = new GEdge(5, gNode4, gNode7);
        List<GEdge> gNode4OutEdges = Arrays.asList(gEdge4to6, gEdge4to7);


        GEdge gEdge5to8 = new GEdge(6, gNode5, gNode8);
        List<GEdge> 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<GEdge> gNode6OutEdges = Arrays.asList(gEdge6to5, gEdge6to7, gEdge6to8);

        GEdge gEdge7to8 = new GEdge(5, gNode7, gNode8);
        List<GEdge> gNode7OutEdges = Collections.singletonList(gEdge7to8);

        Map<GNode, List<GEdge>> 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}

6.链接


转载请注明来源,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 157162006@qq.com

文章标题:数据结构和算法6-非线性-图

字数:3.6k

本文作者:沐雨云楼

发布时间:2020-07-04, 16:09:47

最后更新:2020-09-12, 21:21:47

原始链接:https://iworkh.gitee.io/blog/2020/07/04/data-structures-algorithms-graph/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏

pgmanor iworkh gitee