tonglin0325的个人主页

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
package graph;

import java.util.LinkedList;
import java.util.Queue;

import thinkinjava.net.mindview.util.Stack;

//类名:Vertex
//属性:
//方法:
class Vertex{
public char label; //点的名称,如A
public boolean wasVisited;

public Vertex(char lab){ //构造函数
label = lab;
wasVisited = false;
}
}

//类名:Graph
//属性:
//方法:
class Graph{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; //顶点列表数组
private int adjMat[][]; //邻接矩阵
private int nVerts; //当前的顶点
private char sortedArray[];

public Graph(){ //构造函数
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int j=0;j<MAX_VERTS;j++){
for(int k=0;k<MAX_VERTS;k++)
adjMat[j][k] = 0;
}
sortedArray = new char[MAX_VERTS];
}

public void addVertex(char lab){ //添加新的顶点,传入顶点的lab,并修改nVerts
vertexList[nVerts++] = new Vertex(lab);
}

public void addEdge(int start,int end){ //添加边,这里是无向图
adjMat[start][end] = 1;
//adjMat[end][start] = 1;
}

public void displayVertex(int v){ //显示顶点
System.out.print(vertexList[v].label);
}

public int getAdjUnvisitedVertex(int v){ //返回一个和v邻接的未访问顶点
for(int j=0;j<nVerts;j++)
if(adjMat[v][j] == 1 &amp;&amp; vertexList[j].wasVisited == false){
return j;
}
return -1; //如果没有,返回-1
}

public void dfs(){ //深度搜索
Stack<Integer> theStack = new Stack<Integer>();
vertexList[0].wasVisited = true;
displayVertex(0);
theStack.push(0); //把根入栈

while(!theStack.empty()){
int v = getAdjUnvisitedVertex(theStack.peek());//取得一个和栈顶元素邻接的未访问元素
if(v == -1) //如果没有和栈顶元素邻接的元素,就弹出这个栈顶
theStack.pop();
else{ //如果有这个元素,则输出这个元素,标记为已访问,并入栈
vertexList[v].wasVisited = true;
displayVertex(v);
theStack.push(v);
}
}
for(int j=0;j<nVerts;j++) //全部置为未访问
vertexList[j].wasVisited = false;
}

public void bfs(){ //广度搜索
Queue<Integer> theQueue = new LinkedList<Integer>();
vertexList[0].wasVisited = true;
displayVertex(0);
theQueue.offer(0); //把根入队列
int v2;

while(!theQueue.isEmpty()){
int v1 = theQueue.remove();//v1记录第1层的元素,然后记录第2层第1个元素...

while((v2=getAdjUnvisitedVertex(v1)) != -1){//输出所有和第1层邻接的元素,输出和第2层第1个元素邻接的元素...
vertexList[v2].wasVisited = true;
displayVertex(v2);
theQueue.offer(v2);
}
}

for(int j=0;j<nVerts;j++) //全部置为未访问
vertexList[j].wasVisited = false;
}

public void mst(){ //基于深度搜索的最小生成树
Stack<Integer> theStack = new Stack<Integer>();
vertexList[0].wasVisited = true;
theStack.push(0); //把根入栈

while(!theStack.empty()){
int currentVertex = theStack.peek(); //记录栈顶元素,当有为邻接元素的时候,才会输出
int v = getAdjUnvisitedVertex(theStack.peek());//取得一个和栈顶元素邻接的未访问元素
if(v == -1) //如果没有和栈顶元素邻接的元素,就弹出这个栈顶
theStack.pop();
else{ //如果有这个元素,则输出这个元素,标记为已访问,并入栈
vertexList[v].wasVisited = true;
theStack.push(v);

displayVertex(currentVertex);
displayVertex(v);
System.out.println();
}
}
for(int j=0;j<nVerts;j++) //全部置为未访问
vertexList[j].wasVisited = false;
}

public int noSuccessors(){ //使用邻接矩阵找到没有后继的顶点,有后继顶点返回行数,没有返回-1
boolean isEdge;

for(int row=0;row<nVerts;row++){//从第1行开始
isEdge = false;
for(int col=0;col<nVerts;col++){//如果某一行某一列为1,返回这个行的行数
if(adjMat[row][col] > 0){
isEdge = true;
break;
}
}
if(!isEdge)
return row;
}
return -1;
}

public void moveRowUp(int row,int length){
for(int col=0;col<length;col++)
adjMat[row][col] = adjMat[row+1][col];
}

public void moveColLeft(int col,int length){
for(int row=0;row<length;row++)
adjMat[row][col] = adjMat[row][col+1];
}

public void deleteVertex(int delVert){
if(delVert != nVerts-1){
for(int j=delVert;j<nVerts-1;j++)//在数组中去掉这个顶点
vertexList[j] = vertexList[j+1];
for(int row=delVert;row<nVerts-1;row++)//在邻接矩阵中把删除的这一行下的所有行上移
moveRowUp(row,nVerts);
for(int col=delVert;col<nVerts-1;col++)//在邻接矩阵中把删除的这一列下的所有列左移
moveColLeft(col,nVerts-1);
}
nVerts--;
}

public void topo(){ //拓扑排序,必须在无环的有向图中进行,必须在有向图中
int orig_nVerts = nVerts; //记录有多少个顶点

while(nVerts > 0){
int currentVertex = noSuccessors();
if(currentVertex == -1){
System.out.println("错误:图含有环!");
return;
}
sortedArray[nVerts-1] = vertexList[currentVertex].label;
deleteVertex(currentVertex);
}
System.out.println("拓扑排序结果:");
for(int j=0;j<orig_nVerts;j++)
System.out.println(sortedArray[j]);

}

}


public class graph_demo {

public static void main(String[] args) {
// TODO 自动生成的方法存根
Graph theGraph = new Graph();
theGraph.addVertex('A'); //数组元素0
theGraph.addVertex('B'); //数组元素1
theGraph.addVertex('C'); //数组元素2
theGraph.addVertex('D'); //数组元素3
theGraph.addVertex('E'); //数组元素4

// theGraph.addEdge(0, 1); //AB
// theGraph.addEdge(1, 2); //BC
// theGraph.addEdge(0, 3); //AD
// theGraph.addEdge(3, 4); //DE

// System.out.println("dfs访问的顺序:");
// theGraph.dfs();
// System.out.println();
//
// System.out.println("bfs访问的顺序:");
// theGraph.bfs();



// theGraph.addEdge(0, 1); //AB
// theGraph.addEdge(0, 2); //AC
// theGraph.addEdge(0, 3); //AD
// theGraph.addEdge(0, 4); //AE
// theGraph.addEdge(1, 2); //BC
// theGraph.addEdge(1, 3); //BD
// theGraph.addEdge(1, 4); //BE
// //theGraph.addEdge(2, 3); //CD
// //theGraph.addEdge(2, 4); //CE
// theGraph.addEdge(3, 4); //DE

// System.out.println("最小生成树:");
// theGraph.mst();


theGraph.addVertex('F'); //数组元素5
theGraph.addVertex('G'); //数组元素6
theGraph.addVertex('H'); //数组元素6

theGraph.addEdge(0, 3); //AD
theGraph.addEdge(0, 4); //AE
theGraph.addEdge(1, 4); //BE
theGraph.addEdge(2, 5); //CF
theGraph.addEdge(3, 6); //DG
theGraph.addEdge(4, 6); //EG
theGraph.addEdge(5, 7); //FH
theGraph.addEdge(6, 7); //GH

theGraph.topo();
}



}