数据结构-图形介绍与实现

(一)图形介绍以及实现

图形介绍

图的定义

图是一系列顶点(结点)和描述顶点的关系边(弧)组成。图是数据元素的集合,这些数据元素相互连接形成网路,其形式化定义为:

G = (V,E)

其中V为所有顶点的集合,E为所有边的集合。图形共有两种:一是无向图形,一是有向图形。无向图以(V1,V2)表示边线,有向图以<V1,V2>表示边线。

图的常用术语

  1. :在无向图中,顶点的度是指连那个顶点的边的数量。对于有向图来说,分为入度和出度。
  2. 入度:一个顶点的入度是指向当前顶点的边的数量。
  3. 出度:一个顶点的出度是由该顶点出发的边的数量。
  4. :有些图的边(弧)附带有一些数据信息,这些数据信息称为边的权(Weight)。
  5. 完全图:完全图是指任意俩顶点之间都互相有连线的图。无向图中,N个顶点正好有N(N-1)/2条边;在有向图中,N个顶点会有N(N-1)条边。
  6. 子图:一个图中的部分顶点和连接这些顶点的部分弧。
  7. 路径:两个不同顶点之间所经过的边称为路径。
  8. 路径长度:路径上所包含边的总数为路径长度。
  9. 回路:起始顶点及终止顶点为同一节点的简单路径称为回路。
  10. 相连:在无向图中,若顶点Vi到顶点Vj间存在路径,则Vi和Vj之间是相连的。
  11. 相连图:如果图形G中,任两个顶点均相连,则此图形称为相连图形。
  12. 相连单元:图形中相连在一起的最大子图总数。
  13. 强相连:在有向图中,任两顶点间有相反的边称为强相连。

图的基本操作

  1. 插入顶点
  2. 查找顶点
  3. 删除顶点
  4. 插入边
  5. 查找边
  6. 删除边
  7. 求图的边数
  8. 遍历图
  9. 求最短路径

图的实现

图这一数据结构可以通过多种方法来进行实现,下面将介绍四种方法,并且重点介绍一下邻接矩阵表示法与邻接表表示法。

说明:下面的实现代码中关于图形的遍历寻找图的最短路径等内容为后续拓展内容,建议初学者先学习本节内容的其他部分,等全部理解再请依次点击查看。

邻接矩阵表示法★

邻接矩阵法是指用一个n n的二维矩阵来表示一个图,其矩阵的定义如下:对于一个图形G=(V,E),假设有n个顶点,n>=1,则可以将n个顶点的图形,利用一个n n的二维矩阵来表示。其中

  1. 若图的边无权值,若A(i,j)=1,则表示图形中有一条边(Vi,Vj)存在,反之,若A(i,j)=0则表示顶点i与顶点j之间不存在边。

  2. 若图的边有权值,用无穷大A(i,j)=∞表示顶点之间无边,用权值A(i,j)=权值表示俩顶点之间有边,同一点之间的权值为0。

  3. 下面给出无权值的邻接矩阵表示方式:

优缺点

从上述结构可以看出,直观明了,也比较容易实现,但是因为我们默认每个顶点和所有其他的节点都有连线(若没有连线则用0来表示),所以当边很少的时候,会导致内存空间的浪费。因此,应该仅在图是致密的时候使用邻接矩阵实现图

下面给出相应的代码实现,为了方便大家阅读,特意将结构放到下图,另外,代码中也有比较详细的注释,可以方便大家理解。

IGroup.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package com.x1aolin.AdjacencyMatrix;

public interface IGraph<E> {
public int getNumOfVertex(); //获取顶点的个数
public boolean insertVex(E v); //插入顶点
public boolean deleteVex(E v); //删除顶点
public int indexOfVex(E v); //定位顶点的位置
public E valueOfVex(int v); //定位指定位置的顶点
public boolean insertEdge(int v1,int v2,int weight); //插入边
public boolean deleteEdge(int v1,int v2); //删除边
public int getEdge(int v1,int v2); //查找边
public String depthFirstSearch(int v); //深度优先搜索
public String breadFirstSearch(int v); //广度优先搜索
public int[] dijkstra(int v); //查找源点到其他顶点的路径
}

GraphAdjMatrix.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
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
package com.x1aolin.AdjacencyMatrix;
import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class GraphAdjMatrix<E> implements IGraph<E> {
private E[] vexs; //存储图的顶点的一维数组
private int[][] edges; //存储图的边的二维数组
private int numOfVexs; //顶点的实际数量
private int maxNumOfVexs; //顶点的最大数量
private boolean[] visited; //判断顶点是否被访问过
//初始化
public GraphAdjMatrix(int maxNumOfVexs,Class<E> type) {
super();
this.maxNumOfVexs = maxNumOfVexs;
edges = new int[maxNumOfVexs][maxNumOfVexs];
vexs = (E[])Array.newInstance(type, maxNumOfVexs);
}
//get set当前顶点个数
public int getNumOfVexs() {
return numOfVexs;
}

public void setNumOfVexs(int numOfVexs) {
this.numOfVexs = numOfVexs;
}
//得到顶点的数目
public int getNumOfVertex(){
return numOfVexs;
}
//插入顶点
public boolean insertVex(E v){
if(numOfVexs>=maxNumOfVexs){
return false;
}
vexs[numOfVexs++] = v;
return true;
}
//删除顶点
public boolean deleteVex(E v){
for(int i=0;i<numOfVexs;i++){
//寻找到该结点
if(vexs[i].equals(v)){
//在顶点数组中删除顶点,前移,最后一个置空。
for(int j=i;j<numOfVexs-1;j++){
vexs[j] = vexs[j+1];
}
vexs[numOfVexs-1] = null;
//删除与该顶点相关的边
int col,row;
//操作行
for(col=i;col<numOfVexs-1;col++){
for(row=0;row<numOfVexs;row++){
edges[col][row] = edges[col+1][row];
}
}
//操作列
for(row=i;row<numOfVexs-1;row++){
for(col=0;col<numOfVexs-1;col++){
edges[col][row] = edges[col][row+1];
}
}
setNumOfVexs(numOfVexs-1);
return true;
}
}
return false;
}
//寻找顶点的位置
public int indexOfVex(E v){
for(int i=0;i<numOfVexs;i++){
if(vexs[i].equals(v)){
return i;
}
}
return -1;
}
//寻找指定位置的顶点
public E valueOfVex(int v){
if(v<0||v>numOfVexs){
return null;
}
return vexs[v];
}
//插入边
public boolean insertEdge(int v1,int v2,int weight){
if(v1<0 || v2<0 || v1>=numOfVexs || v2>=numOfVexs ){
throw new ArrayIndexOutOfBoundsException();
}
edges[v1][v2] = weight;
edges[v2][v1] = weight;
return true;
}
//删除边
public boolean deleteEdge(int v1,int v2){
if(v1<0 || v2<0 || v1>=numOfVexs || v2>=numOfVexs ){
throw new ArrayIndexOutOfBoundsException();
}
edges[v1][v2] = 0;
edges[v2][v1] = 0;
return true;
}
//查找边
public int getEdge(int v1,int v2){
if(v1<0 || v2<0 || v1>=numOfVexs || v2>=numOfVexs ){
throw new ArrayIndexOutOfBoundsException();
}
return edges[v1][v2];
}
//深度优先搜索
public String depthFirstSearch(int v){
if(v<0||v>=numOfVexs)
throw new ArrayIndexOutOfBoundsException();
visited = new boolean[numOfVexs];
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
stack.push(v);
visited[v] = true;
while(!stack.isEmpty()){
v = stack.pop();
sb.append(vexs[v]+",");
for(int i=numOfVexs-1;i>=0;i--){
if((edges[v][i]!=0&&edges[v][i]!=Integer.MAX_VALUE)&&!visited[i]){
stack.push(i);
visited[i] = true;
}
}
}
if(sb.length()>0){
return sb.substring(0, sb.length()-1);
}
return null;
}
//广度优先搜索
public String breadFirstSearch(int v){
if(v<0||v>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
visited = new boolean[numOfVexs];
StringBuilder s = new StringBuilder();
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(v);
visited[v] = true;
while(!queue.isEmpty()){
v = queue.poll();
s.append(vexs[v] + ",");
for(int i=0;i<numOfVexs;i++){
if((edges[v][i]!=0&&edges[v][i]!=Integer.MAX_VALUE)&&!visited[i]){
queue.offer(i);
visited[i] = true;
}
}
}
if(s.length()>0) return s.substring(0, s.length()-1);
return null;
}
//实现Dijkstra算法
public int[] dijkstra(int v){
if(v<0||v>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
boolean[] st = new boolean[numOfVexs];
int[] distance = new int[numOfVexs];

for(int i=0;i<numOfVexs;i++){
for(int j=0;j<numOfVexs;j++){
if(edges[i][j] == 0){
edges[i][j] = Integer.MAX_VALUE;
edges[j][i] = Integer.MAX_VALUE;
}
}
}
//初始化
for(int i=0;i<numOfVexs;i++){
distance[i] = edges[i][v];
}
st[v] = true;
distance[v] = 0;
//步骤撒三和四
for(int i = 0;i<numOfVexs;i++){
//从未访问顶点中选择路径长度最短的顶点加入访问集合。
int min = Integer.MAX_VALUE;
int index = -1;
//选择最小值
for(int j=0;j<numOfVexs;j++){
if(!st[j]&&distance[j]<min){
min = distance[j];
index = j;
}
}
if(index!=-1) st[index] = true;
//修改未访问顶点的最短路径。
for(int k=0;k<numOfVexs;k++){
if(!st[k])
if(edges[index][k]!=Integer.MAX_VALUE
&& distance[k]>min+edges[index][k]){
distance[k] = min + edges[index][k];
}
}
}
return distance;
}
}

TestCode.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
package com.x1aolin.AdjacencyMatrix;

import java.util.Scanner;


public class TestCode {
@SuppressWarnings("rawtypes")
public static void main(String[] args) {
String[] vexs ={"V1","V2","V3","V4","V5","V6"};
int[][] edges = {{0,20,0,10,0,0},
{20,0,10,0,0,35},
{0,10,0,20,25,5},
{10,0,20,0,15,0},
{0,0,25,15,0,0},
{0,35,5,0,0,0}

};
@SuppressWarnings("unchecked")
IGraph<String> graph = new GraphAdjMatrix(10,String.class);

Scanner sc = new Scanner(System.in);
System.out.println("-------------------------");
System.out.println("a.添加顶点");
System.out.println("b.添加边");
System.out.println("c.显示邻接矩阵");
System.out.println("d.删除顶点");
System.out.println("e.删除边");
System.out.println("f.深度优先遍历");
System.out.println("g.广度优先遍历");
System.out.println("h.求最短路径");
System.out.println("t.退出");
System.out.println("-------------------------");
char ch;
while(true){
System.out.println("请输入操作选项:");
ch = sc.next().charAt(0);
if(ch=='t') break;
String vex;
switch(ch){
case 'a':
for(int i=0;i<vexs.length;i++){
graph.insertVex(vexs[i]);
}
System.out.println("添加顶点完成!");
break;

case 'b':
for(int i =0;i<edges.length;i++){
for(int j=0;j<edges.length;j++){
graph.insertEdge(i, j, edges[i][j]);
}
}
System.out.println("边添加完成");
break;

case 'c':
int num = graph.getNumOfVertex();
if(num==0){
System.out.println("还没有创建图,请先创建一个图!");
break;
}
System.out.println("该图的邻接矩阵是");
//输出顶点
for(int i=0;i<num;i++){
System.out.print(graph.valueOfVex(i)+"\t");
}
System.out.println();
//输出邻接矩阵
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
System.out.print(graph.getEdge(i, j)+"\t");
}
System.out.println();
}
break;
case 'd':
System.out.println("请输入要删除结点的名称:");
vex = sc.next();
graph.deleteVex(vex);
System.out.println(vex+"删除成功!");
break;

case 'e':
System.out.println("请输入要删除边的一个顶点:");
vex = sc.next();
System.out.println("请输入要删除边的另外一个顶点:");
String vex2 = sc.next();
int a = graph.indexOfVex(vex);
int b = graph.indexOfVex(vex2);
if(a<0||b<0){
System.out.println("您输入的顶点有误,请重新输入");
break;
}
graph.deleteEdge(a, b);
System.out.println(vex+"与"+vex2+"之间的边被删除!");
break;
case 'f':
System.out.println("请输入出发的顶点名称:");
vex = sc.next();
String path = graph.depthFirstSearch(graph.indexOfVex(vex));
System.out.println("深度优先遍历结果为"+path);
break;
case 'g':
System.out.println("请输入出发的顶点名称:");
vex = sc.next();
String path1 = graph.breadFirstSearch(graph.indexOfVex(vex));
System.out.println("广度优先遍历结果为"+path1);
break;
case 'h':
System.out.print("请输入出发的顶点名称: ");
vex = sc.next();
int[] dis = graph.dijkstra(graph.indexOfVex(vex));
System.out.println("顶点"+vex+"到各顶点的最短距离时:");
for(int i=0;i<graph.getNumOfVertex();i++){
System.out.print(graph.valueOfVex(i)+"\t");
}
System.out.println();
for(int i=0;i<dis.length;i++){
System.out.print(dis[i]+"\t");
}
System.out.println();
break;
default:
System.out.println("您输入有误,请重新输入");
break;
}
}
sc.close();
}
}

邻接表表示法★

这种表示法以表结构来表示图形,有点类似与相邻矩阵,不过忽略掉矩阵中为0的部分,直接把1的部分放入节点里,如此一来可以有效避免浪费存储空间。该存储方法是一种顺序存储与链式存储相结合的表示方法,顺序存储部分用来保存图中顶点的信息,链式存储部分用来保存图中边(或弧)的信息。

具体做法

使用一个一维数组保存图中顶点的信息,数组中每个数组元素包含两个域:

  • 顶点域datal:存放与顶点相关的信息。
  • 头指针域firstadj:与当前顶点相关链表的头指针。

邻接单链表中每个结点表示依附于该顶点的一条表,称为边结点。其中,边结点的存储结构包含三个域:

  • 邻接点域adjvex:顶点的序号。
  • 数据域info:记录当前结点与顶点之间边的权值。
  • 链域nextadj:指向与该顶点相邻的下一个边结点的指针。

下面给出一个不含权值的图给大家大致的感受,若有权值直接在图中加上即可:

代码实现

代码结构如图:

InGraph.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package com.x1aolin.GraphAdjList;

public interface InGraph<E> {
public int getNumOfVertex(); //获取顶点的个数
public boolean insertVex(E v); //插入顶点
public boolean deleteVex(E v); //删除顶点
public int indexOfVex(E v); //定位顶点的位置
public E valueOfVex(int v); //定位指定位置的顶点
public boolean insertEdge(int index1,int v2,int weight); //插入边
public boolean deleteEdge(int v1,int v2); //删除边
public int getEdge(int v1,int v2); //查找边
public String depthFirstSearch(int v); //深度优先搜索
public String breadFirstSearch(int v); //广度优先搜索
public int[] dijkstra(int v); //查找源点到其他顶点的路径
}

GraphAdjList.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
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
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
package com.x1aolin.GraphAdjList;
import java.lang.reflect.Array;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class GraphAdjList<E> implements InGraph<E> {
//边结点
private static class ENode{
int adjvex; //邻接顶点序号
int weight; //权值
ENode nextadj;
public ENode(int adjvex,int weight){
this.adjvex = adjvex;
this.weight = weight;
}
}
//顶点节点
private static class VNode<E>{
E data;
ENode firstadj;
public VNode(E data){
this.data = data;
}
public VNode(){}
}
private VNode<E>[] vexs; //顶点数组
private int numOfVexs; //顶点数量
private int maxNumOfVexs; //顶点最大数量
private boolean[] visited; //判断结点是否被访问过

public GraphAdjList(int maxNumOfVexs){
this.maxNumOfVexs = maxNumOfVexs;
//开辟数组
vexs = (VNode<E>[])Array.newInstance(VNode.class,maxNumOfVexs);
}
//获取顶点的个数
public int getNumOfVertex(){
return numOfVexs;
}
//插入顶点
public boolean insertVex(E v){
if(numOfVexs>=maxNumOfVexs){
return false;
}
VNode<E> newVex = new VNode<E>(v);
vexs[numOfVexs] = newVex;
numOfVexs++;
return true;
}
//删除顶点
public boolean deleteVex(E v){
for(int i=0;i<numOfVexs;i++){
if(vexs[i].data.equals(v)){
//将该结点后面的结点进行前移
for(int j=i;j<numOfVexs-1;j++){
vexs[j] = vexs[j+1];
}
vexs[numOfVexs-1] = null;
numOfVexs--;
//完成删除该节点后,还要在邻接表中删除与该结点相关的边信息
ENode current;
ENode previous;
for(int j=0;j<numOfVexs;j++){
if(vexs[j].firstadj==null) continue;

current = vexs[j].firstadj;
while(current!=null){
previous = current;
current = current.nextadj;
if(current!=null&&current.adjvex == i){
previous.nextadj = current.nextadj;
break;
}
}
}
//将结点编号大于被删结点的全部减一
for(int j=0;j<numOfVexs;j++){
current = vexs[j].firstadj;
while(current!=null){
if(current!=null){
if(current.adjvex>i){
current.adjvex--;
}
current = current.nextadj;
}
}
}
return true;
}
}
return false;
}
//定位顶点的位置
public int indexOfVex(E v){
for(int i=0;i<numOfVexs;i++){
if(vexs[i].data.equals(v)){
return i;
}
}
return -1;
}
//定位指定位置的顶点
public E valueOfVex(int v){
if(v<0||v>=numOfVexs){
return null;
}
return vexs[v].data;
}
//插入边(针对无向)
public boolean insertEdge(int index1,int index2,int weight){
if(index1<0||index2<0||index1>=numOfVexs||index2>=numOfVexs)
throw new ArrayIndexOutOfBoundsException();
ENode newVex = new ENode(index2,weight);
//索引为index1的顶点没有邻接顶点
if(vexs[index1].firstadj==null){
vexs[index1].firstadj = newVex;
}
//索引为index1的顶点有邻接顶点
else{
//放最后需要遍历,所以放前面效率较高
newVex.nextadj = vexs[index1].firstadj;
vexs[index1].firstadj = newVex;
}
newVex = new ENode(index1,weight);
if(vexs[index2].firstadj==null){
vexs[index2].firstadj = newVex;
}
else{
newVex.nextadj = vexs[index2].firstadj;
vexs[index2].firstadj = newVex;
}
return true;
}
//删除边
public boolean deleteEdge(int index1,int index2){
if(index1<0||index2<0||index1>=numOfVexs||index2>=numOfVexs)
throw new ArrayIndexOutOfBoundsException();
//删除索引为index1顶点的边
ENode current = vexs[index1].firstadj;
ENode previous = null;
while(current!=null&&current.adjvex!=index2){
previous = current;
current = current.nextadj;
}
if(current!=null){
previous.nextadj = current.nextadj;
}
else return false;
//删除索引为index2顶点的边
current = vexs[index2].firstadj;
previous = null;
while(current!=null&&current.adjvex!=index1){
previous = current;
current = current.nextadj;
}
if(current!=null){
previous.nextadj = current.nextadj;
}
else return false;
return true;
}
//查找边
public int getEdge(int v1,int v2){
if(v1<0||v2<0||v1>=numOfVexs||v2>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
ENode current = vexs[v1].firstadj;
while(current!=null){
if(current.adjvex==v2){
return current.weight;
}
current = current.nextadj;
}
return 0; //默认0为无边,不再权值范围内
}
//深度优先搜索
public String depthFirstSearch(int v){
if(v<0||v>=numOfVexs)
throw new ArrayIndexOutOfBoundsException();
visited = new boolean[numOfVexs];
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
stack.push(v);
visited[v] = true;
ENode current;
while(!stack.isEmpty()){
v = stack.pop();
sb.append(vexs[v].data+"->");
current = vexs[v].firstadj;
while(current!=null){
if(!visited[current.adjvex]){
stack.push(current.adjvex);
visited[current.adjvex] = true;
}
current = current.nextadj;
}
}
if(sb.length()>0){
return sb.substring(0,sb.length()-2);
}
return null;
}
//广度优先搜索
public String breadFirstSearch(int v){
if(v<0||v>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
visited = new boolean[numOfVexs];
StringBuilder sb = new StringBuilder();
Queue<Integer> queue = new LinkedList<>();
queue.offer(v);
visited[v] = true;
ENode current;
while(!queue.isEmpty()){
int tmp = queue.poll();
sb.append(vexs[tmp].data + ",");
current = vexs[tmp].firstadj;
while(current!=null){
if(!visited[current.adjvex]){
queue.offer(current.adjvex);
visited[current.adjvex] = true;
}
current = current.nextadj;
}
}
if(sb.length()>0) return sb.substring(0, sb.length()-1);
return null;
}
//实现Dijkstra算法
public int[] dijkstra(int v){
if(v<0||v>=numOfVexs){
throw new ArrayIndexOutOfBoundsException();
}
boolean[] st = new boolean[numOfVexs];
int[] distance = new int[numOfVexs];
//初始化
ENode current = vexs[v].firstadj;
while(current!=null){
distance[current.adjvex] = current.weight;
current = current.nextadj;
}
for(int i=0;i<numOfVexs;i++){
if(distance[i]==0)
distance[i] = Integer.MAX_VALUE;
}
st[v] = true;
distance[v] = 0;
//开始循环
for(int i=0;i<numOfVexs;i++){
//从未访问顶点中选择路径长度最短的顶点加入访问集合
int min = Integer.MAX_VALUE;
int index = -1;
for(int j=0;j<numOfVexs;j++){
if(!st[j]&&distance[j]<min){
index = j;
min = distance[j];
}
}
if(index!=-1){
st[index] = true;
//找到源点到索引为index顶点的最短路径长度
for(int k=0;k<numOfVexs;k++){
if(!st[k]){
int[] tmp = new int[numOfVexs];
ENode cur = vexs[index].firstadj;
while(cur!=null){
tmp[cur.adjvex] = cur.weight;
cur = cur.nextadj;
}
if(tmp[k]!=0&&distance[k]>min+tmp[k])
distance[k] = min + tmp[k];
}
}
}
}
return distance;
}
}

Test.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
package com.x1aolin.GraphAdjList;
import java.util.Scanner;

public class Test {
public static void main(String[] args) {
String[] vexs ={"V1","V2","V3","V4","V5","V6"};
InGraph<String> graph = new GraphAdjList<String>(10);
Scanner sc = new Scanner(System.in);
System.out.println("-------------------------");
System.out.println("a.添加顶点");
System.out.println("b.添加边");
System.out.println("c.显示邻接表");
System.out.println("d.删除顶点");
System.out.println("e.删除边");
System.out.println("f.深度优先遍历");
System.out.println("g.广度优先遍历");
System.out.println("h.求最短路径");
System.out.println("t.退出");
System.out.println("-------------------------");
char ch;
while(true){
System.out.println("请输入操作选项:");
ch = sc.next().charAt(0);
if(ch=='t') break;
switch(ch){
case 'a':
for(int i=0;i<vexs.length;i++){
graph.insertVex(vexs[i]);
}
System.out.println("添加顶点完成!");
break;
case 'b':
graph.insertEdge(0, 1, 20);
graph.insertEdge(1, 2, 10);
graph.insertEdge(1, 5, 35);
graph.insertEdge(2, 5, 5);
graph.insertEdge(2, 3, 20);
graph.insertEdge(0, 3, 10);
graph.insertEdge(2, 4, 25);
graph.insertEdge(3, 4, 15);
System.out.println("边添加完成");
break;
case 'c':
int num = graph.getNumOfVertex();
if(num==0){
System.out.println("还没有创建图,请先创建一个图!");
break;
}
System.out.println("该图的邻接图是");
for(int i=0;i<num;i++){
System.out.print(graph.valueOfVex(i)+":");
for(int j=0;j<num;j++){
if(graph.getEdge(i, j)!=0){
System.out.print(graph.valueOfVex(i)+"->"+
graph.valueOfVex(j)+":"+graph.getEdge(i, j)+"\t");
}
}
System.out.println();
}
break;
case 'd':
System.out.println("请输入要删除结点的名称:");
String vex = sc.next();
graph.deleteVex(vex);
System.out.println(vex+"删除成功!");
break;
case 'e':
System.out.println("请输入要删除边的一个顶点:");
String vex1 = sc.next();
System.out.println("请输入要删除边的另外一个顶点:");
String vex2 = sc.next();
int a = graph.indexOfVex(vex1);
int b = graph.indexOfVex(vex2);
if(a<0||b<0){
System.out.println("您输入的顶点有误,请重新输入");
break;
}
graph.deleteEdge(a, b);
System.out.println(vex1+"与"+vex2+"之间的边被删除!");
break;
case 'f':
System.out.println("请输入出发的顶点名称:");
String vex3 = sc.next();
String path = graph.depthFirstSearch(graph.indexOfVex(vex3));
System.out.println("遍历结果为"+path);
break;
case 'g':
System.out.println("请输入出发的顶点名称:");
String vex4 = sc.next();
String path1 = graph.breadFirstSearch(graph.indexOfVex(vex4));
System.out.println("遍历结果为"+path1);
break;
case 'h':
System.out.print("请输入出发的顶点名称: ");
vex = sc.next();
int[] dis = graph.dijkstra(graph.indexOfVex(vex));
System.out.println("顶点"+vex+"到各顶点的最短距离时:");
for(int i=0;i<graph.getNumOfVertex();i++){
System.out.print(graph.valueOfVex(i)+"\t");
}
System.out.println();
for(int i=0;i<dis.length;i++){
System.out.print(dis[i]+"\t");
}
System.out.println();
break;
default:
System.out.println("您输入有误,请重新输入。");
break;
}
}
sc.close();
}
}

相邻多元列表法

上面我们介绍的两种图形表示方法都是从顶点的观点出发,但如果要处理的是“边”,则必须使用相邻多元列表,其结构如下:

M V1 V2 LINK1 LINK2
记录单元 弧的起点 弧的终点 起点指针 终点指针

说明

M:记录该边是否为被找过的一个字段。

LINKn:在尚有其他顶点与Vn相连的情况下,此字段会指向下一个与Vn相连的边结点,如果没有则指向null

索引表格法

索引表格表示法,利用一维数组来按序存储与各顶点相邻的所有顶点,并建立索引表格,以此来记录各顶点的在此一维数组中第一个与该顶点相邻的位置。具体请自行百度,本博客仅提供一个概念,谢谢。

您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------