算法习题05:图的深度优先遍历

图遍历介绍

所谓图的遍历,即是对结点的访问,一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:1)深度优先遍历(DFS) 2)广度优先遍历

深度优先遍历基本思想

深度优先遍历算法步骤

在链表里的数据的存放顺序如下:

代码实现

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
public class Dfs {
/**
* 存储顶点
*/
private ArrayList<String> vertexList;
/**
* 存储图对应的邻接矩阵
*/
private int[][] edges;
/**
* 表示边的数目
*/
private int numOfEdges;

/**
* 记录某个顶点是否被访问
*/
private boolean[] isVisited;


public static void main(String[] args) {
//结点个数
int n = 5;
//顶点值
String[] vertexs = {"A","B","C","D","E"};
//创建图对象
Dfs graph = new Dfs(n);
//循环添加顶点
for (String vertex : vertexs) {
graph.insertVertex(vertex);
}
//添加边
//A-B A-C B-C B-D B-E
graph.insertEdge(0,1,23);
graph.insertEdge(0,2,12);
graph.insertEdge(1,2,34);
graph.insertEdge(1,3,56);
graph.insertEdge(1,4,41);

//显式邻接矩阵
graph.showGraph();


graph.dfs();
}


/**
* 构造器
* @param n 顶点个数
*/
public Dfs(int n){
//初始化矩阵和vertexList
vertexList = new ArrayList<>(n);
edges = new int[n][n];
isVisited = new boolean[n];
}

/**
* 得到第一个邻接结点的下标
* @param index
* @return
*/
public int getFirstNeighbor(int index){
for (int i = 0; i < vertexList.size(); i++) {
if (edges[index][i] > 0){
return i;
}
}
return -1;
}

/**
* 根据前一个邻接结点的下标获取下一个邻接结点
* @param v1
* @param v2
* @return
*/
public int getNextNeighbor(int v1,int v2){
for (int i = v2 + 1; i < vertexList.size(); i++) {
if (edges[v1][i] > 0){
return i;
}
}
return -1;
}


/**
* 深度优先遍历算法
* @param isVisited
* @param i i第一个就是0
*/
public void dfs(boolean[] isVisited,int i){
System.out.println(getVertexByIndex(i));
//将结点设置为已访问
isVisited[i] = true;

//查找结点i的第一个邻接结点
int w = getFirstNeighbor(i);
//w != -1 说明有
while (w != -1){
//返回下标是否被访问
if (!isVisited[w]){
dfs(isVisited,w);
}
//如果被访问过,查找邻接结点的下一个
w = getNextNeighbor(i,w);
}
}

/**
* 对dfs进行重载,遍历所有的结点,并进行dfs
*/
public void dfs(){
//遍历所有结点,进行dfs
for (int i = 0; i < getNumOfVertex(); i++) {
if (!isVisited[i]){
dfs(isVisited,i);
}
}
}



/**
* 返回结点个数
* @return
*/
public int getNumOfVertex(){
return vertexList.size();
}

/**
* 返回边的数目
* @return
*/
public int getNumOfEdges(){
return numOfEdges;
}

/**
* 返回下标所对应的值
* @param index
* @return
*/
public String getVertexByIndex(int index){
return vertexList.get(index);
}

/**
* 显式邻接矩阵
*/
public void showGraph(){
for (int[] edge : edges) {
System.out.println(Arrays.toString(edge));
}
}

/**
* 返回两个顶点之间的权值
* @param v1
* @param v2
* @return
*/
public int getWeight(int v1,int v2){
return edges[v1][v2];
}

/**
* 插入顶点
* @param vertex 顶点名称
*/
public void insertVertex(String vertex){
vertexList.add(vertex);
}


/**
* 添加边
* @param v1 第一个顶点的下标 (第几个顶点)
* @param v2 第二个顶点的下标
* @param weight 两个顶点之间的距离
*/
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
edges[v2][v1] = weight;
numOfEdges++;
}

}

-------------本文结束感谢您的阅读-------------