小贺のBLOG

【数据结构】(图的两种Java实现与经典应用)

发表于 分类于
本文字数： 11k 阅读时长 ≈ 10 分钟

图已经是数据机构基础中最复杂的结构,它几乎涵盖了前面所有的基础数据结构,本篇涉及到了图的两种构造方式(邻接矩阵和邻接表),以及对应的深度优先遍历/广度优先遍历/Dijkstra/最小生成树/等方法,很多的方法代码复杂难以理解,共勉(●’◡’●)ﾉ♥

前言

我们将会遇到的应用使用几乎都是稀疏图——《算法第四版》

邻接矩阵的处理思路是将顶点和关系分别保存到一个一维数组和一个二维数组中。但是，即使我们保存的是int型数据，一旦数据量达到10万。那么这个数组需要使用的内存空间为：100000 * 100000 * 4Byte = 40GB 所以在这个时候邻接表的优势就很明显了.
IMG_5716.jpg

邻接矩阵表示图

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
package Graph;

public class Graph {

	final int VERTEX_MAX = 10;  //最大结点数
	Vertex[] vertex;  //结点
	int num; //目前的结点数
	int [][] adjacency;  //临街矩阵
	//内部类表示结点
	class Vertex{  
		char content;
		boolean isSearch;
		public Vertex(char content) {
			this.content = content;
			this.isSearch = false;
		}
	}
	//内部类表示栈
	class Stack{
		final int STACK_MAX = 10;
		int stack[];
		int top;
		public Stack() {
			stack = new int[STACK_MAX];
			top = -1;
		}
		public void push(int content) {
			if(top==9) {
				System.out.println("栈已满，无法入栈啦");
			}else {
				stack[++top]=content;
			}
		}
		public int pop() {
			if(top==-1) {
				System.out.println("栈已空，无法出栈啦");
				return -1;
			}else {
				return stack[top--];
			}
		}
		public int peek() {
			return stack[top];
		}
		public boolean isEmpty() {
			return top==-1;
		}
	}
	class Queue{
		final int QUEUE_MAX = 10;
		int [] queue;
		int front;
		int rear;
		public Queue() {
			queue = new int[QUEUE_MAX];
			front = 0;
			rear = -1;
		}
		public void insert(int content) {
			if(rear==QUEUE_MAX) {
				rear=-1;
			}
			queue[++rear]=content;
		}
		public int remove() {
			if(front==QUEUE_MAX) {
				front=0;
			}
			int temp = queue[front++];
			return temp;
		}
		public boolean isEmpty() {
			return (rear+1==front || front+QUEUE_MAX-1==rear);
		}
	}
	//初始化图
	public Graph() {
		this.num = 0;
		this.vertex = new Vertex[VERTEX_MAX];
		this.adjacency = new int[VERTEX_MAX][VERTEX_MAX];
		for(int i=0;i<VERTEX_MAX;i++) {  //邻接矩阵的初始化 所有的结点都没有被访问过
			for(int j=0;j<VERTEX_MAX;j++) {
				adjacency[i][j] = 0;
			}
		}
	}
	//添加结点
	public void addVertex(char content) {
		if(num<VERTEX_MAX-1) {
			vertex[num++] = new Vertex(content);
		}else {
			System.out.println("图已满最大结点，不可以再添加结点了喔～");
		}
	}
	//无向图添加边
	public void addNAdj(int start, int end) {
		if(start<VERTEX_MAX && end<VERTEX_MAX) {
			adjacency[start][end] =  1;
			adjacency[end][start] = 1;
		}else {
			System.out.println("连接的图结点位置不合法，无法连接～");
		}
	}
	//有向图添加边
	public void addYAdj(int start, int end) {
		if(start<VERTEX_MAX && end<VERTEX_MAX) {
			adjacency[start][end] = -1;
		}else {
			System.out.println("连接的图结点位置不合法，无法连接～");
		}
	}
	//打印图中的某个结点
	public void printVertex(int index) {
		if(index>=0 && index<VERTEX_MAX) {
			System.out.print(this.vertex[index].content);
		}else {
			System.out.println("打印结点位置不合法，无法打印～");
		}
	}
	//打印邻接矩阵
	public void printAdjacency() {
		for(int i=0;i<num;i++) {
			for(int j=0;j<num;j++) {
				if(j!=num-1) {
					System.out.print(adjacency[i][j]+" ");
				}else {
					System.out.println(adjacency[i][j]);
				}
			}
		}
	}
	//寻找某一结点的未被访问的邻接点
	public int searchUnsearchVertex(int index) {
		for(int i=0;i<num;i++) {
			if(adjacency[i][index]==1 && vertex[i].isSearch==false) {
				return i;
			}
		}
		return -1;
	}
	//图的深度优先遍历 Depth-first traversal
	public void dpt() {
		Stack stack = new Stack();
		vertex[0].isSearch = true;
		printVertex(0);
		stack.push(0);
		while(!stack.isEmpty()) {
			int index = searchUnsearchVertex(stack.peek());
			if(index==-1) {
				stack.pop();
			}else {
				vertex[index].isSearch = true;
				printVertex(index);
				stack.push(index);
			}
		}
		//遍历结束后将原图返回初始值
		for(int i=0;i<num;i++) {
			vertex[i].isSearch=false;
		}
	}
	//图的广度优先遍历 Breadth-first traversal
	public void bpt() {
		Queue queue = new Queue();
		vertex[0].isSearch = true;
		printVertex(0);
		queue.insert(0);
		while(!queue.isEmpty()) {
			int v1 = queue.remove();
			int v2 = searchUnsearchVertex(v1); 
			if(v2!=-1) {
				vertex[v2].isSearch = true;
				printVertex(v2);
				queue.insert(v2);
			}
		}
		for(int i=0;i<num;i++) {
			vertex[i].isSearch = false;
		}
	}
	//最小生成树 Minimum spanning tree
	public void mst() {
		Stack stack = new Stack();
		vertex[0].isSearch = true;
		stack.push(0);
		while(!stack.isEmpty()) {
			int cur = stack.peek();
			int index = searchUnsearchVertex(0);
			if(index == -1) {
				stack.pop();
			}else {
				vertex[index].isSearch = true;
				stack.push(index);
				printVertex(cur);
				printVertex(index);
			}
		}
		for(int i=0;i<num;i++) {
			vertex[i].isSearch = false;
		}
	}
	public static void main(String[] args) {
		Graph graph = new Graph();
		graph.addVertex('F');
		graph.addVertex('O');
		graph.addVertex('R');
		graph.addVertex('E');
		graph.addVertex('V');
		graph.addVertex('E');
		graph.addVertex('R');
		graph.addNAdj(1, 3);
		graph.addNAdj(2, 5);
		graph.addNAdj(3, 6);
		graph.addNAdj(0, 4);
		graph.addNAdj(0, 1);
		graph.printAdjacency();
		graph.printVertex(3);
		System.out.println("深度优先遍历：");
		graph.dpt();
		System.out.println();
		System.out.println("广度优先遍历：");
		graph.bpt();
		System.out.println();
		System.out.println("最小生成树：");
		graph.mst();
	}
}

邻接表的对应实现

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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
package Graph;

import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class GraphAdj<E> {

	VNode<E>[] vers; //用来存储图的结点
	int max_size; //图的最大结点数量
	int numofvers; //图的当前结点数量
	//邻接表建立图的结点
	class VNode<E>{
		E data; //存储定点数据
		LNode first; //结点的邻接表的第一个结点
		boolean isvisited = false;
	}
	//邻接表建立图的邻接表的结点
	class LNode{
		int weight; //存储权值
		int firstadj; //邻接表结点的序号
		LNode nextvex; //下一个邻接结点
		public LNode(int weight, int firstadj) {
			this.weight = weight;
			this.firstadj = firstadj;
		}
	}
	//邻接表建立图的初始化
	public GraphAdj(int max_size) {
		this.max_size = max_size;
		vers = (VNode[])Array.newInstance(VNode.class, max_size);
	}
	//获取图结点的树木
	public int getNumOfGraph() {
		return numofvers;
	}
	//向图中插入结点
	public boolean insert(E e) {
		if(numofvers>=max_size) {
			return false;
		}
		VNode<E> ver = new VNode<E>();
		ver.data = e;
		vers[numofvers++] = ver;
		return true;
	}
	//获取某结点的位置
	public int getIndex(E e) {
		for(int i=0;i<numofvers;i++) {
			if(vers[i].data == e) {
				return i;
			}
		}
		return -1;
	}
	//获取指定位置的结点
	public E gerData(int index) {
		if(index<0 || index>=numofvers) {
			return null;
		}else {
			return vers[index].data;
		}
	}
	//向图中插入边
	public boolean insertEdg(int v1, int v2, int weight) {
		if(v1<0 || v2<0 || v1>=numofvers || v2>=numofvers) { //合法性判断
			return false;
		}
		LNode vers1 = new LNode(v2, weight);
		LNode vers2 = new LNode(v1, weight);
		//当v1结点没有邻接结点时
		if(vers[v1].first==null) {
			vers[v1].first=vers1;
		}else {//当v1结点有邻接结点时
			vers1.nextvex = vers[v1].first;
			vers[v1].first = vers1;
		}
		//当v2结点没有邻接结点时
		if(vers[v2].first==null) {
			vers[v2].first = vers2;
		}else {//当v2结点有邻接结点时
			vers2.nextvex = vers[v2].first;
			vers[v2].first = vers2;
		}
		return true;
	}
	//删除图中的某条边
	public boolean deleteEdg(int v1, int v2) {
		if(v1<0 || v2<0 || v1>=numofvers || v2>=numofvers) {
			return false;
		}
		LNode current = vers[v1].first;
		LNode pre = null;
		//判断v1到v2之间是否存在边
		while(current!=null && current.firstadj!=v2) {
			pre = current;
			current = current.nextvex;
		}
		//v1到v2之间存在边则删除
		if(current!=null) {
			pre.nextvex = current.nextvex;
		}
		//判断v2到v1之间是否存在边
		current = vers[v2].first;
		while(current!=null && current.firstadj!=v1) {
			pre = current;
			current = current.nextvex;
		}
		//v2到v1之间存在边则删除
		if(current!=null) {
			pre.nextvex = current.nextvex;
		}
		return true;
	}
	//获得指定的结点间的边
	public boolean getEdg(int v1, int v2) {
		if(v1<0 || v2<0 || v1>=numofvers || v2>=numofvers) {
			return false;
		}
		LNode current = vers[v1].first;
		while(current!=null) {
			if(current.firstadj == v2) {
				System.out.println("结点v"+v1+"->"+"结点v"+v2+"边的权值为："+current.weight);
			}
		}
		current = vers[v2].first;
		while(current!=null) {
			if(current.firstadj == v2) {
				System.out.println("结点v"+v2+"->"+"结点v"+v1+"边的权值为："+current.weight);
			}
		}
		return true;
	}
	//深度优先遍历 Deep-first traversal
	public void DFT(int v) {
		if(v<0 || v>=numofvers) {
			return;
		}
		Stack<Integer> stack = new Stack<Integer>();
		vers[v].isvisited = true;
		LNode current;
		stack.push(v);
		while(stack!=null) {
			v = stack.pop();
			System.out.println(vers[v].data+" ");
			current = vers[v].first;
			while(current!=null) {
				if(vers[current.firstadj].isvisited==false) {
					stack.push(current.firstadj);
					vers[current.firstadj].isvisited = true;
				}
				current = current.nextvex;
			}
		}
		//遍历完成后恢复初始状态
		for(int i=0;i<numofvers;i++) {
			vers[i].isvisited = false;
		}
	}
	//广度优先遍历 Breadth-first traversal
	public void BFT(int v) {
		if(v<0 || v>=numofvers) {
			return;
		}
		Queue<Integer> queue = new LinkedList<Integer>();
		LNode current;
		vers[v].isvisited = true;
		queue.offer(v);
		while(queue!=null) {
			v = queue.poll();
			System.out.println(vers[v].data+" ");
			current = vers[v].first;
			while(current!=null) {
				if(vers[current.firstadj].isvisited==false) {
					queue.offer(current.firstadj);
					vers[current.firstadj].isvisited = true;
				}
				current = current.nextvex;
			}
		}
		//遍历完成后恢复初始状态
		for(int i=0;i<numofvers;i++) {
			vers[i].isvisited = false;
		}
	}
	//Dijkstra最短路径
	/*
	 * 基本思路就是先建立一个源点与各个结点的距离库
	 * 然后将结点作为入度的结点与源点通过的的各个结点距离相加 若小于最初的距离 则更新 直到全部更新完毕
	 */
	public int[] Dijkstra(int v) {
		if(v<0 || v>numofvers) {
			return null;
		}
		LNode current;
		current = vers[v].first;
		int[] distance = new int[numofvers];
		for(int i=0;i<numofvers;i++) {
			distance[i] = Integer.MAX_VALUE;  //即∞
		}
		while(current!=null) {
			distance[current.firstadj] = current.weight;
			current = current.nextvex;
		}
		distance[v] = 0;
		vers[v].isvisited = true;
		for(int i=0;i<numofvers;i++) {
			int min = Integer.MAX_VALUE;
			int index = -1;
			// 比较从源点到其余顶点的路径长度
			for (int j = 0; j < numofvers; j++) {
				// 从源点到j顶点的最短路径还没有找到
				if (vers[j].isvisited == false) {
					// 从源点到j顶点的路径长度最小
					if (distance[j] < min) {
						index = j;
						min = distance[j];
					}
				}
			}
			// 找到源点到索引为index顶点的最短路径长度
			if (index != -1)
				vers[index].isvisited = true;
			// 更新当前最短路径及距离
			for (int t = 0; t < numofvers; t++)
				if (vers[t].isvisited == false) {
					current = vers[t].first;
					while (current != null) {
						if (current.firstadj == index)
							if ((min + current.weight) < distance[t]) {
								distance[t] = min + current.weight;
								break;
							}
						current = current.nextvex;
					}
				}
		}
		return distance;
		}
}
如果觉得还不错的话，把它分享给朋友们吧(ง •̀_•́)ง