作为数据结构中最难的一个结构，图。可以说是折磨了笔者整个大学时光。本想着终于可以摆脱了，谁能想到阴差阳错的，要去做这个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
|
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;
}
public VRoot getVRoot(V v) {
if (v != null) {
for (VRoot vRoot : vRootList) {
if (vRoot.root != null && v.equals(vRoot.root)) {
return vRoot;
}
}
}
return null;
}
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;
}
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);
}
}
}
}
|
DGraph.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
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
|
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
|
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 +
'}';
}
public void addEdge(Edge<V> e) {
if (getEdge(e.getEnd()) == null) {
rootEdgeList.add(e);
}else {
System.out.println("edge is exit .");
}
}
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;
}
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 ;
|
这里我在贴一下我的测试主类:
TestGraph.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
| 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);
|
基本上一个广度优先遍历的图的创建到使用，我都贴出来了。其中关于深度遍历这块笔者还在纠结这个怎么去确定左右孩子（就是孩子的顺序，有可能不止两个孩子）的问题。这块笔者还没想明白。后面笔者在进行补充。
结论
笔者也是因为工作需要，才来看这个图方面的知识的。必须要承认一点，就是笔者在大学时代对于数据结构与算法没有好好的去学习，现在想起来，还是比较想骂自己的。如果看这篇文章里面有正在学习数据结构的朋友呢，还是建议好好学这门课，其实还是挺有意思的。
