Java实现深度优先和广度优先遍历
其实这两个算法思想很好理解。
深度优先遍历：
- 在一个图中选择一个起始点v0，然后遍历其子节点。
- 再以子节点为起始点，遍历子节点的子节点。
- 就这样一直递归下去，重复2。
- 然后一直遍历到没有子节点，开始回溯。
广度优先遍历：
- 从图中某个顶点v0出发，并访问此顶点。
- 从v0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点。
- 重复步骤2，直到全部顶点都被访问为止。
(显然，从v0出发广度优先遍历图，将得到v0到它的各个可达到的路径）
下面开始上菜：
前期造图代码准备：
import java.io.IOException;
import java.util.Scanner;
public class graphTraversal {
private char[] vertex; //顶点集合
private int[][] matrix; //邻接矩阵
private static final int INF = 999999; //最大值
private static int count = 0;
/**
* 创建图
*/
public graphTraversal() {
Scanner sca = new Scanner(System.in);
int vertexNum = sca.nextInt(); //顶点数
int matrixNum = sca.nextInt(); //边数
vertex = new char[vertexNum];
vertex = sca.next().toCharArray(); //初始化顶点
//初始化矩阵
matrix = new int [vertexNum][vertexNum];
for(int i = 0; i < vertexNum; i++)
for(int j = 0; j < vertexNum; j++)
matrix[i][j] = (i == j) ? 0 : INF;
for(int i = 0; i < matrixNum; i++) { //初始化边的权值
char start = readChar(); //边的起点
char end = readChar(); //边的终点
int weight = sca.nextInt(); //边的权值
int startInedx = getLocation(start); //获取边的起点坐标
int endIndex = getLocation(end); //获取边的终点坐标
if(startInedx == -1 || endIndex == -1) return;
matrix[startInedx][endIndex] = weight;
matrix[endIndex][startInedx] = weight;
}
sca.close();
}
/**
* 深度优先搜索遍历图
*/
public void DFS() {
boolean[] visited = new boolean[vertex.length]; //记录顶点访问标记
//初始化所有顶点都没被访问
for(int i = 0; i < vertex.length; i++)
visited[i] = false;
System.out.println("DFS遍历:" );
for(int i = 0; i < vertex.length; i++) {
if(!visited[i])
DFS(i, visited);
}
System.out.println();
}
/**
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
count++;
visited[i] = true;
if(count == vertex.length) {
System.out.println(vertex[i]);
}else {
System.out.print(vertex[i] + "————>");
}
//遍历该顶点的所有邻接顶点，若是没有访问过，Go on
for(int j = firstVertex(i); j >= 0; j = nextVertex(i, j)) {
if(!visited[j])
DFS(j, visited);
}
}
/**
* 广度优先搜索(类比树的层次遍历)
*/
public void BFS() {
count = 0; //遍历点数归0
int head = 0;
int rear = 0;
int[] queue = new int[vertex.length]; //辅助队列
boolean[] visited = new boolean[vertex.length]; //顶点访问标记
for(int i = 0; i < vertex.length; i++)
visited[i] = false;
System.out.println("BFS:");
for(int i = 0; i < vertex.length; i++) {
if(!visited[i]) {
count++;
visited[i] = true;
if(count == vertex.length) {
System.out.print(vertex[i]);
}else {
System.out.print(vertex[i] + "————>");
}
queue[rear++] = i; //入队列
}
while(head != rear) {
int j = queue[head++]; //出队列
for(int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) { //k是为访问的邻接顶点
if(!visited[k]) {
visited[k] = true;
count++;
if(count == vertex.length) {
System.out.print(vertex[k]);
}else {
System.out.print(vertex[k] + "————>");
}
queue[rear++] = k;
}
}
}
}
System.out.println();
}
/**
* 返回顶点v的第一个邻接顶点的索引，失败返回-1
*/
private int firstVertex(int v) {
if(v < 0 || v > (vertex.length - 1))
return -1;
for(int i = 0; i < vertex.length; i++) {
if(matrix[v][i] != 0 && matrix[v][i] != INF) {
return i;
}
}
return -1;
}
/**
* 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
*/
private int nextVertex(int v, int j) {
if(v < 0 || v > (vertex.length - 1) || j < 0 || j > (vertex.length - 1))
return -1;
for(int i = j + 1; i < vertex.length; i++) {
if(matrix[v][i] != 0 && matrix[v][i] != INF)
return i;
}
return -1;
}
/**
* 读取一个输入字符
* @return
*/
private char readChar() {
char ch = '0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
e.printStackTrace();
}
}while(!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')));
return ch;
}
/**
* 返回字符的位置
*/
private int getLocation(char c) {
for(int i = 0; i < vertex.length; i++)
if(vertex[i] == c) return i;
return -1;
}
public static void main(String[] args) {
graphTraversal gra = new graphTraversal();
gra.DFS(); //深度优先遍历
gra.BFS(); //广度优先遍历
}
}
测试数据：
输入：
8 9
ABCDEFGH
A B 1
A C 1
B D 1
B E 1
D H 1
E H 1
C F 1
C G 1
F G 1
输出：