剑指Offer–图的操作

前言

  企业笔试过程中会涉及到数据结构的方方面面，现将有关图的深度优先搜索与广度优先搜索进行整理归纳，方便日后查阅。
  在已做过的笔试题目中，可用DFS解决的题目有:

1. “地牢逃脱”–网易
2. “遍历最短路径长度”–携程
3. “小青蛙走迷宫”–滴滴

  三道题目都是DFS的经典应用，主要采用递归+回溯的方式。
  下面主要讲解一下DFS与BFS的具体实现。

深度优先搜索(DFS) && 广度优先搜索(BFS)

package cn.edu.ujn.graph;
import java.util.ArrayList;
import java.util.LinkedList;
/**
 * @description 邻接矩阵模型类
 * @author SHQ
 * @time 2016.09.12 
 */
public class DFS_BFS { private ArrayList<Object> vertexList;// 存储点的链表 private int[][] edges; // 邻接矩阵，用来存储边 private int numOfEdges; // 边的数目 boolean[] isVisited; // 遍历标志位 public DFS_BFS(int n) { //初始化矩阵，二维数组，和边的数目 edges = new int[n][n]; vertexList = new ArrayList<Object>(n); numOfEdges = 0; // 将所有节点访问标志位均置为未访问 isVisited = new boolean[n]; for(int i = 0; i < n; i++){ isVisited[i] = false; } } // 得到结点的个数 public int getNumOfVertex() { return vertexList.size(); } // 得到边的数目 public int getNumOfEdges() { return numOfEdges; } // 返回结点i的数据 public Object getValueByIndex(int i) { return vertexList.get(i); } // 返回v1,v2的权值 public int getWeight(int v1,int v2) { return edges[v1][v2]; } //插入结点 public void insertVertex(Object vertex) { vertexList.add(vertexList.size(),vertex); } //插入结点 public void insertEdge(int v1,int v2,int weight) { edges[v1][v2]=weight; numOfEdges++; } //删除结点 public void deleteEdge(int v1,int v2) { edges[v1][v2] = 0; numOfEdges--; } // 得到第一个邻接结点的下标 public int getFirstNeighbor(int index) { for(int j = 0; j < vertexList.size(); j++) { if (edges[index][j] > 0) { return j; } } return -1; } // 根据前一个邻接结点的下标来取得下一个邻接结点 public int getNextNeighbor(int v1, int v2) { for (int j = v2+1; j < vertexList.size(); j++) { if (edges[v1][j]>0) { return j; } } return -1;
} // 私有函数，深度优先遍历 private void depthFirstSearch(boolean[] isVisited,int  i) { // 首先访问该结点，在控制台打印出来 System.out.print(getValueByIndex(i) + "  "); // 置该结点为已访问 isVisited[i] = true; int w = getFirstNeighbor(i); while (w != -1) { if (!isVisited[w]) { depthFirstSearch(isVisited,w); } w = getNextNeighbor(i, w); } } // 对外公开函数，深度优先遍历，与其同名私有函数属于方法重载 public void depthFirstSearch() { for(int i = 0; i < getNumOfVertex(); i++) { //因为对于非连通图来说，并不是通过一个结点就一定可以遍历所有结点的。 if (!isVisited[i]) { depthFirstSearch(isVisited,i); } }
} /** * 私有函数，广度优先遍历 * 遍历步骤: *  1.访问初始结点v并标记结点v为已访问。 *  2.结点v入队列 *  3.当队列非空时，继续执行，否则算法结束。 *  4.出队列，取得队头结点u。 *  5.查找结点u的第一个邻接结点w。 *  6.若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤： * 1)若结点w尚未被访问，则访问结点w并标记为已访问。 * 2)结点w入队列 * 3)查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。 * @param isVisited * @param i */ private void broadFirstSearch(boolean[] isVisited, int i) { int u, w; // 借助辅助队列，记录访问顺序 LinkedList<Object> queue = new LinkedList<Object>(); // 访问结点i System.out.print(getValueByIndex(i) + "  "); isVisited[i] = true; // 结点入队列 queue.addLast(i); while (!queue.isEmpty()) { u = ((Integer)queue.removeFirst()).intValue(); w = getFirstNeighbor(u); while(w != -1) { if(!isVisited[w]) { //访问该结点 System.out.print(getValueByIndex(w)+"  "); //标记已被访问 isVisited[w] = true; //入队列 queue.addLast(w); } //寻找下一个邻接结点 w = getNextNeighbor(u, w); } } } //对外公开函数，广度优先遍历 public void broadFirstSearch() { for(int i = 0; i < getNumOfVertex(); i++) { if(!isVisited[i]) { broadFirstSearch(isVisited, i); } } }
}
  

 

  
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
 

Main.java

package cn.edu.ujn.graph;

public class Main { public static void main(String args[]) { int n = 8, e = 9;   // 分别代表结点个数和边的数目 String labels[]={"1","2","3","4","5","6","7","8"};  // 结点的标识 DFS_BFS graph = new DFS_BFS(n); for(String label : labels) { graph.insertVertex(label);  // 插入结点 } //插入九条边 graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.insertEdge(3, 7, 1); graph.insertEdge(4, 7, 1); graph.insertEdge(2, 5, 1); graph.insertEdge(2, 6, 1); graph.insertEdge(5, 6, 1); graph.insertEdge(1, 0, 1); graph.insertEdge(2, 0, 1); graph.insertEdge(3, 1, 1); graph.insertEdge(4, 1, 1); graph.insertEdge(7, 3, 1); graph.insertEdge(7, 4, 1); graph.insertEdge(6, 2, 1); graph.insertEdge(5, 2, 1); graph.insertEdge(6, 5, 1);

/* System.out.println("深度优先搜索序列为："); graph.depthFirstSearch(); System.out.println();*/ System.out.println("广度优先搜索序列为："); graph.broadFirstSearch(); }
}
  

 

  
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
 

文章来源: shq5785.blog.csdn.net，作者：No Silver Bullet，版权归原作者所有，如需转载，请联系作者。

原文链接：shq5785.blog.csdn.net/article/details/52605864