图的深度优先搜索和广度优先搜索

遍历

图的遍历,所谓遍历,即是对结点的访问。一个图有那么多个结点,如何遍历这些结点,需要特定策略,一般有两种访问策略:

  • 深度优先遍历
  • 广度优先遍历

深度优先

深度优先遍历,从初始访问结点出发,我们知道初始访问结点可能有多个邻接结点,深度优先遍历的策略就是首先访问第一个邻接结点,然后再以这个被访问的邻接结点作为初始结点,访问它的第一个邻接结点。总结起来可以这样说:每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。

我们从这里可以看到,这样的访问策略是优先往纵向挖掘深入,而不是对一个结点的所有邻接结点进行横向访问。

具体算法表述如下:

  1. 访问初始结点v,并标记结点v为已访问。
  2. 查找结点v的第一个邻接结点w。
  3. 若w存在,则继续执行4,否则算法结束。
  4. 若w未被访问,对w进行深度优先遍历递归(即把w当做另一个v,然后进行步骤123)。
  5. 查找结点v的w邻接结点的下一个邻接结点,转到步骤3。

例如下图,其深度优先遍历顺序为 1->2->4->8->5->3->6->7

img

广度优先

类似于一个分层搜索的过程,广度优先遍历需要使用一个队列以保持访问过的结点的顺序,以便按这个顺序来访问这些结点的邻接结点。

具体算法表述如下:

  1. 访问初始结点v并标记结点v为已访问。

  2. 结点v入队列

  3. 当队列非空时,继续执行,否则算法结束。

  4. 出队列,取得队头结点u。

  5. 查找结点u的第一个邻接结点w。

  6. 若结点u的邻接结点w不存在,则转到步骤3;否则循环执行以下三个步骤:

    1
    2
    3
    1). 若结点w尚未被访问,则访问结点w并标记为已访问。
    2). 结点w入队列
    3). 查找结点u的继w邻接结点后的下一个邻接结点w,转到步骤6

如下图,其广度优先算法的遍历顺序为:1->2->3->4->5->6->7->8

img

Java实现

邻接矩阵图模型类 AMWGraph.java,在原先类的基础上增加了两个遍历的函数,分别是 depthFirstSearch()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
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
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @description 邻接矩阵模型类
* @author beanlam
* @time 2015.4.17
*/
public class AMWGraph {
private ArrayList vertexList;//存储点的链表
private int[][] edges;//邻接矩阵,用来存储边
private int numOfEdges;//边的数目
public AMWGraph(int n) {
//初始化矩阵,一维数组,和边的数目
edges=new int[n][n];
vertexList=new ArrayList(n);
numOfEdges=0;
}
//得到结点的个数
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);
}
}
}
//私有函数,广度优先遍历
private void broadFirstSearch(boolean[] isVisited,int i) {
int u,w;
LinkedList queue=new LinkedList();
//访问结点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);
}
}
}
}

上面的public声明的depthFirstSearch()和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
public class TestSearch {
public static void main(String args[]) {
int n=8,e=9;//分别代表结点个数和边的数目
String labels[]={"1","2","3","4","5","6","7","8"};//结点的标识
AMWGraph graph=new AMWGraph(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();
}
}
坚持原创技术分享,您的支持将鼓励我继续创作!