南风意未起
0%

【图论】你曾虐我千百遍，我却待你如初恋

发表于 更新于 分类于 阅读次数：

作为数据结构中最难的一个结构，图。可以说是折磨了笔者整个大学时光。本想着终于可以摆脱了，谁能想到阴差阳错的，要去做这个DAG。

基础概念

有向无环图

有向无环图指的是一个没有回路的有向图，简单的说就是没有撤退可言。在图论中，如果一个人有向图无法从某个顶点出发，经过若干条边回到该顶点，则这个图是一个有向无环图（DAG图）。那么现在一个小的问题来了。什么是有向图？什么是图？

图

图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)的集合。

概念这玩意从来是让人看的。我知道大家有人肯定没看懂。但这个没关系，我来解释就好了。先看下面的这张图:

现在我们再来看这个概念，什么叫顶点集，图中的 A,B,C,D,E,F ,这就是一个顶点集，也就是一个V的集合。集合内的元素是A,B,C,D,E,F。再来看什么叫做边集。我们可以看到，A->B,是不是有一个连线，去连接AB？这条线就是边。边组成的集合，我们称为边集。也就是说，一个E的集合。集合内元素是 AB,AC,BE,EF,EG 组成的集合。

这就是图的概念。图的概念理解后，现在就是有哪些图了。一般我们会根据图是否是闭合的，分为有环图和无环图。无环图就是指，无论你从哪个顶点走，你都不会回来的。根据我们的边的是否有方向分为有向图和无向图。这里我们讨论有向图。

有向图

前面说了图的概念，现在来看有向图。由于有向图的边是有方向性的，所以我们在表示有向图的时候，需要注意我们的方向不要错了。前面的举的例子，就是一个有向图，而且是无环的。

相关术语

这里的关于图的术语，会比较多，遇到了参考下就好了，一般用用就会了。

  • 顶点：图中的一个点
  • 边：连接两个顶点的线段叫做边，edge
  • 相邻的：一个边的两头的顶点称为是相邻的顶点
  • 度数：由一个顶点出发，有几条边就称该顶点有几度，或者该顶点的度数是几，degree
  • 路径：通过边来连接，按顺序的从一个顶点到另一个顶点中间经过的顶点集合
  • 简单路径：没有重复顶点的路径
  • 环：至少含有一条边，并且起点和终点都是同一个顶点的路径
  • 简单环：不含有重复顶点和边的环
  • 连通的：当从一个顶点出发可以通过至少一条边到达另一个顶点，我们就说这两个顶点是连通的
  • 连通图：如果一个图中，从任意顶点均存在一条边可以到达另一个任意顶点，我们就说这个图是个连通图
  • 无环图：是一种不包含环的图
  • 稀疏图：图中每个顶点的度数都不是很高，看起来很稀疏
  • 稠密图：图中的每个顶点的度数都很高，看起来很稠密
  • 二分图：可以将图中所有顶点分为两部分的图、
    在 有向图 中，我们一般还会有这样的术语：
  • 出度：由一个顶点出发的边的总数
  • 入度：指向一个顶点的边的总数

接着，由于有向图的方向性，一条边的出发点称为头，指向点称为尾。

  • 有向路径：图中的一组顶点可以满足从其中任意一个顶点出发，都存在一条有向边指向这组顶点中的另一个。

  • 有向环：至少含有一条边的起点和终点都是同一个顶点的一条有向路径。

  • 简单有向环：一条不含有重复顶点和边的环。

  • 路径或环的长度就是他们包含的边数。

算法实现

这里我使用的是Java语言。仅供大家参考。
首先看我的程序的基本结构：

大家看到这个结构图，也能知道DAGGraph里面是什么，所以这个接口我就不贴出了。BFS和 DFS是我的两个内部实现类，目前DFS还处于编写状态，但是怎么写，笔者还不确定。如果网友有思路可以和我交流一下。
AbsDGraph.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * @author Mr.Sun
 * @version v.1.0
 * @title AdjacencyListDGraph
 * @description 邻接链表实现的有向图
 * @date 2020/3/23 9:38
 */
public abstract class AbsDGraph<V> {
    private static Logger log = Logger.getLogger(AbsDGraph.class);
    /**
     * 构建一个顶点列表
     */
    protected List<VRoot> vRootList ;

    public List<VRoot> getVRootList() {
        return vRootList;
    }

    public void setVRootList(List<VRoot> vRootList) {
        this.vRootList = vRootList;
    }
    /**
     * 获取根节点
     *
     * @param v
     * @return
     */
    public VRoot getVRoot(V v) {
        if (v != null) {
            for (VRoot vRoot : vRootList) {
                if (vRoot.root != null && v.equals(vRoot.root)) {
                    return vRoot;
                }
            }
        }
        return null;
    }

    /**
     * 判断节点是否存在
     *
     * @param v
     * @param vIterator
     * @return
     */
    public boolean vinList(V v, Iterator<V> vIterator) {
        if (v != null && vIterator != null) {
            while (vIterator.hasNext()) {
                V next = vIterator.next();
                if (next != null && v.equals(next)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 删除顶点
     * @param v
     * @return
     */
    public VRoot removeRoot(V v) {
        if (v != null) {
            for (VRoot vRoot : vRootList) {
                if (vRoot.root != null && v.equals(vRoot.root)){
                    vRootList.remove(vRoot);
                    return vRoot;
                }
            }
        }
        return null;
    }

    public void removeRootEdge(V v){
        if (v != null ){
            for (VRoot vRoot : vRootList) {
                vRoot.removeEdge(v);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
```java
/**
 * @author Mr.Sun
 * @version v.1.0
 * @title DGraph
 * @description
 * @date 2020/3/23 14:29
 */
public class DGraph<V> extends AbsDGraph<V> implements DAGGraph<V> {
    private static Logger log = Logger.getLogger(DGraph.class);
    public DGraph(){
        List<VRoot> vRootList = new LinkedList<VRoot>();
        setVRootList(vRootList);
    }
    @Override
    public int add(V v) {
        int index = -1;
        if (v != null) {
            VRoot vRoot = new VRoot(v);
            getVRootList().add(vRoot);
            index = getVRootList().indexOf(vRoot);
        }
        return index;
    }

    @Override
    public void add(Edge<V> e) {
        if (e != null) {
            VRoot vRoot = getVRoot(e.getStart());
            if (vRoot != null) {
                vRoot.addEdge(e);
            } else {
                System.out.println(System.out.printf("error: can not find v: %s", e.getStart()));
            }
        }
    }

    @Override
    public V remove(V v) {
        VRoot vRoot = removeRoot(v);
        if (vRoot != null) {
            removeRootEdge(v);
            return (V) vRoot.root;
        }
        return null;
    }

    @Override
    public Edge<V> remove(Edge<V> e) {
        if (e != null) {
            VRoot vRoot = getVRoot(e.getStart());
            if (vRoot != null) {
                return vRoot.removeEdge(e.getEnd());
            }
        }
        return null;
    }

    @Override
    public V get(int index) {
        if (index >= 0 || index < getVRootList().size()) {
            VRoot vRoot = getVRootList().get(index);
            if (vRoot != null) {
                return (V) vRoot.root;
            }
        }
        return null;
    }

    @Override
    public Edge<V> get(int start, int end) {
        V v1 = get(start);
        V v2 = get(end);

        if (v1 != null && v2 != null) {
            VRoot vRoot = getVRoot(v1);
            if (vRoot != null) {
                return vRoot.getEdge(v2);
            }
        }
        return null;
    }

    @Override
    public Iterator<V> iterator(int type, V root) {
        Iterator<V> vIterator = null;
        if (type == TRAVERSAL_TYPE_BFS) {
            vIterator = new BFS(root);
        }else if (type == TRAVERSAL_TYPE_DFS){
            vIterator = new DFS(root);
        }
        return vIterator;
    }

    @Override
    public boolean convertDAG() {
        return false;
    }

    /**
     * 广度遍历（队列实现）
     */
    private class BFS implements Iterator<V> {
        /**
         * 已经访问过的顶点列表
         */
        private List<V> vList = null;
        /**
         * 待访问的顶点队列
         */
        private Queue<V> vQueue = null;

        public BFS(V root) {
            this.vList = new LinkedList<V>();
            this.vQueue = new LinkedList<V>();
            // 初始节点进入队列
            vQueue.offer(root);
        }

        @Override
        public boolean hasNext() {
            if (vQueue.size() > 0) {
                return true;
            }
            return false;
        }

        @Override
        public V next() {
            V poll = vQueue.poll();
            if (poll != null) {
                VRoot vRoot = getVRoot(poll);
                if (vRoot != null) {
                    List<Edge<V>> list = vRoot.getRootEdgeList();
                    for (Edge<V> vEdge : list) {
                        V end = vEdge.getEnd();
                        if (!vinList(end, vList.iterator()) && !vinList(end, vQueue.iterator())) {
                            vQueue.offer(end);
                        }
                    }
                }
                vList.add(poll);
            }
            return poll;
        }

    }

    private class DFS implements Iterator<V> {

        /**
         * 已经访问过的顶点列表
         */
        private List<V> vList = null;
        /**
         * 待访问的顶点队列
         */
        private Stack<V> vStack = null;

        public DFS(V root){
            this.vList = new LinkedList<V>();
            this.vStack = new Stack<V>();
            // 初始节点进入栈
            vStack.push(root);
        }
        @Override
        public boolean hasNext() {
            if (vStack.size() > 0) {
                return true;
            }
            return false;
        }

        @Override
        public V next() {

            return null;
        }
    }
}

这里面，我会用到一个顶点类 VRoot.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/**
 * @author Mr.Sun
 * @version v.1.0
 * @title VRoot
 * @description
 * @date 2020/3/23 10:40
 */
public class VRoot<V> extends AbsDGraph {
    private static Logger log = Logger.getLogger(VRoot.class);
    /**
     * 当前顶点
     */
    public V root;

    /**
     * 以此点为起点的边的集合
     */
    public List<Edge<V>> rootEdgeList;

    public VRoot(V root) {
        this.root = root;
        this.rootEdgeList = new LinkedList<Edge<V>>();
        System.out.println(System.out.printf("the VRoot construct: %s ", root));

    }

    public List<Edge<V>> getRootEdgeList() {
        return rootEdgeList;
    }

    @Override
    public String toString() {
        return "VRoot{" +
                "root=" + root +
                ", rootEdgeList=" + rootEdgeList +
                '}';
    }

    /**
     * 添加边
     *
     * @param e
     * @return
     */
    public void addEdge(Edge<V> e) {
        if (getEdge(e.getEnd()) == null) {
            rootEdgeList.add(e);
        }else {
            System.out.println("edge is exit .");
        }

    }

    /**
     * 获取边
     *
     * @param end
     * @return
     */
    public Edge<V> getEdge(V end) {
        Edge<V> temp = null;
        if (end != null) {
            for (Edge<V> vEdge : rootEdgeList) {
                if (vEdge.getEnd() != null && end.equals(vEdge.getEnd())) {
                    temp = vEdge;
                    break;
                }
            }
        }
        return temp;
    }

    /**
     * 删除边
     * @param end
     * @return
     */
    public Edge<V> removeEdge(V end) {
        if (end != null) {
            for (Edge<V> vEdge : rootEdgeList) {
                if (vEdge != null && end.equals(vEdge.getEnd())) {
                    rootEdgeList.remove(end);
                    return vEdge;
                }
            }
        }
        return null;
    }
}

表是边的类： Edge.java ,这里面是对Edge做的一个简单的封装，相关方法大家看就好了。

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 定义边的起点
 */
private V start ;
/**
 * 定义边的终点
 */
private V end ;
/**
 * 定义权值
 */
private double weight ;

这里我在贴一下我的测试主类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

```java
        DGraph dGraph = new DGraph();
        System.out.println("添加端点");
        dGraph.add("1");
        dGraph.add("2");
        dGraph.add("3");
        dGraph.add("4");
        dGraph.add("5");
        dGraph.add("6");
        dGraph.add("7");
        dGraph.add("8");
        System.out.println("添加边");
        dGraph.add(new Edge<String>("1" , "2"));
        dGraph.add(new Edge<String>("1" , "3"));
        dGraph.add(new Edge<String>("2" , "4"));
        dGraph.add(new Edge<String>("2" , "5"));
        dGraph.add(new Edge<String>("4" , "6"));
        dGraph.add(new Edge<String>("5" , "7"));
        dGraph.add(new Edge<String>("4" , "8"));

        Iterator<String> iterator = dGraph.iterator(DAGGraph.TRAVERSAL_TYPE_BFS, "1");

        while (iterator.hasNext()){
            String next = iterator.next();
            System.out.println(next + " ");
        }

        Iterator<String> iterator1 = dGraph.iterator(DAGGraph.TRAVERSAL_TYPE_BFS, "2");
        while (iterator1.hasNext()){
            String next = iterator1.next();
            System.out.println(next + " ");
        }

        Edge edge = dGraph.get(0, 1);
        System.out.println(edge);

基本上一个广度优先遍历的图的创建到使用，我都贴出来了。其中关于深度遍历这块笔者还在纠结这个怎么去确定左右孩子（就是孩子的顺序，有可能不止两个孩子）的问题。这块笔者还没想明白。后面笔者在进行补充。

结论

笔者也是因为工作需要，才来看这个图方面的知识的。必须要承认一点，就是笔者在大学时代对于数据结构与算法没有好好的去学习，现在想起来，还是比较想骂自己的。如果看这篇文章里面有正在学习数据结构的朋友呢，还是建议好好学这门课，其实还是挺有意思的。

相关文章
这是打赏的地方...

本文标题:【图论】你曾虐我千百遍，我却待你如初恋

文章作者:Mr.Sun

发布时间:2020年03月23日 - 17:51:14

最后更新:2020年06月10日 - 10:01:45

原始链接:http://www.blog.sun-iot.xyz/posts/dd7f37bf

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

---------Thanks for your attention---------