数据结构-深度优先与广度优先

(二)图的遍历–深度优先搜索与广度优先搜索

图形的遍历

概念:图的遍历是指从图中的任一节点出发,对图中的所有顶点访问一次且仅访问一次。在图中,若没有特殊的顶点被指定为起始顶点,图的遍历可以从任何顶点开始。图的遍历主要有深度优先搜索和广度优先搜索两种方式,下面进行逐一介绍。

说明:代码实现部分是基于上节图形的介绍与实现中定义的结构,有基于邻接矩阵和邻接表两种方式,请结合上节进行学习。

DFS-深度优先搜索

算法思想:

从图中某一顶点 x 出发,访问 x,然后遍历任何一个与 x 相邻的未被访问的顶点 y,再遍历任何一个与 y 相邻的未被访问的顶点 z……依此类推,直到到达一个所有邻接点都被访问的顶点为止;然后,依次回退到尚有邻接点未被访问过的顶点,重复上述过程,直到图中全部顶点都被访问过为止。

算法实现讲解

深度优先遍历背后基于堆栈,我们这里主要说明显示构造堆栈,利用压栈出栈操作实现遍历,当然,利用递归来隐式调用也可以。

以上图为例,遍历过程如下:

  1. 访问起始顶点V1,并将V1压入栈。
  2. 从栈中弹出顶点V1,将与V1相邻的未被访问的所有顶点V4和V2压入栈。
  3. 从栈中弹出顶点V2,将与V2相邻的未被访问的所有顶点V6和V3压入栈。
  4. 从栈中弹出顶点V3,将与V3相邻的未被访问的所有顶点V5压入栈。
  5. 从栈中弹出顶点V5,顶点V5没有任何未被访问的邻接顶点,因此没有顶点入栈。
  6. 从栈中弹出顶点V6,顶点V6没有任何未被访问的邻接顶点,因此没有顶点入栈。
  7. 从栈中弹出顶点V6,顶点V6没有任何未被访问的邻接顶点,因此没有顶点入栈;此时栈为空,遍历完成。

说明:入栈之后就算是被访问过,不是等从栈中弹出才算访问过,因为栈中有了该顶点,等后面从栈中弹出即可。

基于邻接矩阵法的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
}

基于邻接表法的代码实现:

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
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;
}

BFS-广度优先搜索

算法思想

图的广度优先算法是从图的某个顶点 x 出发,访问 x。然后访问与 x 相邻的所有未被访问的顶点 x1,x2,…,xn;接着再依次访问与 x1,x2,…,xn相邻接的未被访问过的所有顶点。以此类推,直至图的每个顶点都被访问。

算法实现讲解

可以使用队列来实现广度优先搜索算法,使用队列对上图中的顶点进行的广度优先搜索过程如下:

  1. 访问起始顶点V1,并将它插入到队列。
  2. 从队列中删除队头顶点V1,访问所有它未被访问的邻接顶点V2和V4,并将它们插入到队列。
  3. 从队列中删除队头结点V2,访问所有它未被访问过的邻接顶点V3和V6,并将它们插入到队列。
  4. 从队列中删除队头结点V4,访问所有它未被访问过的邻接顶点V5,并将其插入到队列。
  5. 从队列中删除队头结点V3,V3没有任何未被访问的邻接顶点,因此无需入队。
  6. 从队列中删除队头结点V6,V3没有任何未被访问的邻接顶点,因此无需入队。
  7. 从队列中删除队头结点V5,V3没有任何未被访问的邻接顶点,因此无需入队。
  8. 此时队列为空,图的遍历完成

说明:只要入队即为被访问过,出入队过程如下图所示:

代码实现

基于邻接矩阵的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

基于邻接表的代码实现:

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
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;
}
您的每一份支持将鼓励我继续创作!
-------------本文结束感谢您的阅读-------------