欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的深度优先搜索(DFS)和广度优先搜索(BFS)及其Java实现

程序员文章站 2022-06-12 19:17:45
...

一、背景知识:

(1)图的表示方法:邻接矩阵(二维数组)、邻接表(链表数组【链表的链表】)。

(2)图的搜索方法:深度优先搜索(DFS)和广度优先搜索(BFS)。

二、图的搜索:

      1、深度优先搜索(DFS)

         (1)用记录下一步的走向。访问一个顶点的过程中要做三件事:

               ①访问顶点

               ②顶点入栈,以便记住它

               ③标记顶点,以便不会再访问它

        (2)访问规则:

                a.如果可能,访问一个邻接的未访问顶点,标记它,并入栈。

                b.当不能执行a时(没有邻接的未访问顶点),如果栈不为空,就从栈中弹出一个顶点。

                c.如果不能执行规则a和b,就完成了整个搜索过程。

        (3)实现:基于以上规则,循环执行,直到栈为空。每次循环各种,它做四件事:

               ①用peek()方法检查栈顶的顶点。

               ②试图找到这个顶点还未访问的邻接点。

               ③如果没有找到,出栈。

               ④如果找到这样的顶点,访问并入栈。

图的深度优先搜索(DFS)和广度优先搜索(BFS)及其Java实现

          比如,采用dfs遍历上图,从A点出发,遍历结果(入栈顺序)为:ABCDE。

      2、广度优先搜索(BFS)

        (1)用队列记录下一步的走向。深度优先搜素表现的好像是尽快远离起点似的,相反,广度优先搜索中,算法好像要尽可能靠近起始点。

        (2)访问规则:

                a.访问下一个未访问的邻接点(如果存在),这个顶点必须是当前顶点的邻接点,标记它,并入队列。

                b.如果因为已经没有未访问顶点而不能执行规则a,那么从队列头取一个顶点(如果存在),并使其成为当前顶点。

                c.如果因为队列为空而不能执行规则b,则完成了整个搜索过程。

        (3)实现:基于以上规则,对下图做bfs遍历,其队列的变化如下表所示:

图的深度优先搜索(DFS)和广度优先搜索(BFS)及其Java实现

图的深度优先搜索(DFS)和广度优先搜索(BFS)及其Java实现

              从而,遍历的结果(入队顺序)为ABCDEFGHI。如果采用bfs遍历3中的图,结果为:ABDCE。

        (4)特性:广度优先搜索首先找到与起始点相距一条边的所有顶点,然后是与起始点相距两条边的顶点,以此类推。如果要寻找起始顶点到指定顶点的最短距离,那么这个属性非常有用。首先执行BFS,当找到指定顶点时,就可以说这条路径是到这个顶点的最短路径。如果有更短的路径,BFS算法就应该已经找到它了。

三、Java实现

DFS、BFS的代码实现如下:

public class Graph {
	private final int MAX_VERTS = 20;
	private Vertex vertexList[];// 顶点数组
	private int adjMat[][];// 邻接矩阵
	private int nVerts;// 当前顶点总数
	private StackX theStack;
	private Queue theQueue;

	public static void main(String[] args) {
		Graph theGraph = new Graph();
		theGraph.addVertex('A');
		theGraph.addVertex('B');
		theGraph.addVertex('C');
		theGraph.addVertex('D');
		theGraph.addVertex('E');

		theGraph.addEdge(0, 1);
		theGraph.addEdge(1, 2);
		theGraph.addEdge(0, 3);
		theGraph.addEdge(3, 4);

		System.out.print("visits:");
		// theGraph.dfs();
		theGraph.bfs();
		System.out.println();
	}

	public Graph() {// 构造图
		vertexList = new Vertex[MAX_VERTS];

		adjMat = new int[MAX_VERTS][MAX_VERTS];
		nVerts = 0;
		for (int i = 0; i < MAX_VERTS; i++) {
			for (int j = 0; j < MAX_VERTS; j++) {
				adjMat[i][j] = 0;
			}
		}
		theStack = new StackX();
		theQueue = new Queue();
	}

	public void addVertex(char lab) {// 添加顶点
		vertexList[nVerts++] = new Vertex(lab);
	}

	public void addEdge(int start, int end) {// 添加边
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}

	public void displayVertex(int v) {// 打印数组中v位置下的顶点名
		System.out.print(vertexList[v].lable);
	}

	public int getAdjUnvisitedVertex(int v) {// 获取和v邻接的未访问的顶点
		for (int i = 0; i < nVerts; i++) {
			if (adjMat[v][i] == 1 && vertexList[i].wasVisited == false) {
				return i;
			}
		}
		return -1;
	}

	public void dfs() {// 深度优先搜索
		vertexList[0].wasVisited = true;
		displayVertex(0);
		theStack.push(0);

		while (!theStack.isEmpty()) {
			int v = getAdjUnvisitedVertex(theStack.peek());
			if (v == -1) {
				theStack.pop();
			} else {
				vertexList[v].wasVisited = true;
				displayVertex(v);
				theStack.push(v);
			}
		}

		for (int i = 0; i < nVerts; i++) {
			vertexList[i].wasVisited = false;// 重置,防止后边再次使用dfs
		}
	}

	public void bfs() {// 广度优先搜索
		vertexList[0].wasVisited = true;
		displayVertex(0);
		theQueue.insert(0);
		int v2;

		while (!theQueue.isEmpty()) {
			int v1 = theQueue.remove();

			while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
				vertexList[v2].wasVisited = true;
				displayVertex(v2);
				theQueue.insert(v2);
			}
		}

		for (int j = 0; j < nVerts; j++) {
			vertexList[j].wasVisited = false;
		}
	}
}

class StackX {// 自定义栈
	private final int SIZE = 20;
	private int[] st;
	private int top;

	public StackX() {
		st = new int[SIZE];
		top = -1;
	}

	public void push(int j) {
		st[++top] = j;
	}

	public int pop() {
		if (top == 0) {
			return -1;
		}
		return st[--top];
	}

	public int peek() {
		return st[top];
	}

	public boolean isEmpty() {
		return (top == -1);
	}
}

class Queue {
	private final int SIZE = 20;
	private int[] queArray;
	private int front;
	private int rear;

	public Queue() {
		queArray = new int[SIZE];
		front = 0;
		rear = -1;
	}

	public void insert(int j) {// 入队
		if (rear == SIZE - 1) {
			rear = -1;
		}
		queArray[++rear] = j;
	}

	public int remove() {// 出队
		if (!isEmpty()) {
			return queArray[front++];
		} else {
			return -1;
		}
	}

	public boolean isEmpty() {
		return (rear + 1 == front);
	}
}

class Vertex {
	public char lable;// 名字
	public boolean wasVisited;

	public Vertex(char lab) {
		lable = lab;
		wasVisited = false;
	}
}

输出:

visits:ABDCE