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
| import java.util.Stack;
public class Graph {
class Vertex{ //顶点
public char lebel;
public boolean visited;
public Vertex(char lab){
lebel = lab;
visited = false;
}
}
private final int maxVertices = 20 ; //最大顶点数
private Vertex vertexList[];
private int adjMatrix[][];
private int vertexCount;
private Stack theStack;
public Graph(){
vertexList = new Vertex[maxVertices];
adjMatrix = new int[maxVertices][maxVertices];
vertexCount = 0;
for(int y = 0 ; y < maxVertices ; y++){
for(int x = 0 ; x < maxVertices ; x ++){
adjMatrix[x][y] = 0;
}
}
theStack = new Stack();
}
public void addVertex(char lab){
vertexList[vertexCount++]=new Vertex(lab);
}
public void addEdge(int start,int end){
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
public void displayVertex(int v){
System.out.println(vertexList[v].lebel);
}
public void dfs(){
vertexList[0].visited = true;
displayVertex(0);
theStack.push(0);
while (!theStack.isEmpty()){
int v = getAdjUnvisitedVertes((int)theStack.peek());
if(v == -1){
theStack.pop();
}else {
vertexList[v].visited = true;
displayVertex(v);
theStack.push(v);
}
}
for(int j = 0 ; j < vertexCount; j++){
vertexList[j].visited = false;
}
}
public int getAdjUnvisitedVertes(int v){
for(int j = 0 ; j < vertexCount ; j ++){
if(adjMatrix[v][j] == 1 && vertexList[j].visited == false){
return j;
}
}
return -1;
}
public static void main(String[] args) {
int col = 9 ;
int[][] a = new int[col][col];
a[0][1] = 1;a[0][5] = 1;a[1][2] = 1;a[1][6]= 1;a[1][8]= 1;
a[2][3] = 1; a[2][8] = 1;
a[3][8] =1; a[3][6]= 1; a[3][7] = 1;a[3][4] = 1;
a[4][5] =1; a[4][7]= 1; a[5][6] = 1;a[6][7] = 1;
Graph graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addVertex('G');
graph.addVertex('H');
graph.addVertex('I');
for(int y = 0 ; y < col; y ++){
for(int x = 0 ; x < col ; x ++ ){
if(a[y][x] == 1){
graph.addEdge(y,x);
}
}
}
graph.dfs();
}
}
|