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

【数据结构】——图的深度优先搜索和广度优先搜索

程序员文章站 2022-05-20 20:23:48
...

关于邻接矩阵和邻接表

下面都以此图进行遍历：
【数据结构】——图的深度优先搜索和广度优先搜索

1.深度优先搜索

深度优先搜索，Depth First Search，简称DFS。

对于一个连通图，深度优先遍历的过程：

  1. 从图中一个顶点 v v v 出发并访问 v v v 。
  2. 找到刚访问顶点的第一个未被访问的邻接点并访问，并继续以该邻接点作为刚访问过的顶点，重复此步骤直到刚访问过的结点没有未被访问的邻接点为止。
  3. 返回上一个访问过的且还有未被访问邻接点的顶点，继续访问这个顶点的下一个未被访问的邻接点。
  4. 重复2, 3，直到图中所有顶点都被访问。

它的思想是从一个顶点 v v v 开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个结点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。类似树的先序遍历。

邻接矩阵的深度优先遍历

对上面这个图深度优先遍历的一个顺序为：ABDHECFG。深度优先遍历的顺序不唯一，因为顶点B的第一个邻接点既可以认为是顶点D，也可以认为是顶点E。

java代码：

public class DFS_AM {
	char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
	int[][] matrix = new int[8][8];

	// 创建邻接矩阵
	private void creatMartix() {
		matrix[locate('A')][locate('B')] = matrix[locate('B')][locate('A')] = 1;
		matrix[locate('B')][locate('D')] = matrix[locate('D')][locate('B')] = 1;
		matrix[locate('B')][locate('E')] = matrix[locate('E')][locate('B')] = 1;
		matrix[locate('D')][locate('H')] = matrix[locate('H')][locate('D')] = 1;
		matrix[locate('E')][locate('H')] = matrix[locate('H')][locate('E')] = 1;
		matrix[locate('A')][locate('C')] = matrix[locate('C')][locate('A')] = 1;
		matrix[locate('C')][locate('F')] = matrix[locate('F')][locate('C')] = 1;
		matrix[locate('C')][locate('G')] = matrix[locate('G')][locate('C')] = 1;
		matrix[locate('F')][locate('G')] = matrix[locate('G')][locate('F')] = 1;
	}

	private int locate(char v) {
		int i = 0;
		for (; i < vertex.length; i++) {
			if (v == vertex[i])
				break;
		}
		return i;
	}

	// 顶点访问标记，visited[i]=false表示顶点vertex[i]未被访问，反之表示已经访问过，初始默认值false
	boolean[] visited = new boolean[vertex.length];

	private void dfs(char v) {
		// 访问第一个顶点
		System.out.print(v + " ");
		// 标记该顶点被访问过
		visited[locate(v)] = true;
		for (int j = 0; j < matrix.length; j++) {
			// 找到刚访问顶点的一个未被访问过的邻接点
			if (matrix[locate(v)][j] == 1 && visited[j] == false) {
				// 以该邻接点作为新的顶点递归访问
				dfs(vertex[j]);
			}
		}
	}

	public static void main(String[] args) {
		DFS_AM am = new DFS_AM();
		am.creatMartix();
		am.dfs('A');
	}
}

邻接表的深度优先遍历

public class DFS_AL {
	class VertexNode {
		char verName;
		EdgeNode next;

		public VertexNode(char verName) {
			this.verName = verName;
		}
	}

	class EdgeNode {
		int index;
		EdgeNode next;

		public EdgeNode(int index) {
			this.index = index;
		}
	}

	VertexNode[] vertex = { new VertexNode('A'), 
							new VertexNode('B'), 
							new VertexNode('C'), 
							new VertexNode('D'),
							new VertexNode('E'), 
							new VertexNode('F'), 
							new VertexNode('G'), 
							new VertexNode('H') };

	private int locate(char v) {
		int index = 0;
		for (; index < vertex.length; index++) {
			if (v == vertex[index].verName)
				break;
		}
		return index;
	}

	// 创建邻接表
	private void creatList() {
		vertex[locate('A')].next = new EdgeNode(locate('B'));
		vertex[locate('A')].next.next = new EdgeNode(locate('C'));

		vertex[locate('B')].next = new EdgeNode(locate('A'));
		vertex[locate('B')].next.next = new EdgeNode(locate('D'));
		vertex[locate('B')].next.next.next = new EdgeNode(locate('E'));

		vertex[locate('C')].next = new EdgeNode(locate('A'));
		vertex[locate('C')].next.next = new EdgeNode(locate('F'));
		vertex[locate('C')].next.next.next = new EdgeNode(locate('G'));

		vertex[locate('D')].next = new EdgeNode(locate('B'));
		vertex[locate('D')].next.next = new EdgeNode(locate('H'));

		vertex[locate('E')].next = new EdgeNode(locate('B'));
		vertex[locate('E')].next.next = new EdgeNode(locate('H'));

		vertex[locate('F')].next = new EdgeNode(locate('C'));
		vertex[locate('F')].next.next = new EdgeNode(locate('G'));

		vertex[locate('G')].next = new EdgeNode(locate('C'));
		vertex[locate('G')].next.next = new EdgeNode(locate('F'));

		vertex[locate('H')].next = new EdgeNode(locate('D'));
		vertex[locate('H')].next.next = new EdgeNode(locate('E'));
	}

	boolean[] visited = new boolean[vertex.length];

	private void dfs(char v) {
		// 访问第一个顶点
		System.out.print(v + " ");
		// 标记
		visited[locate(v)] = true;
		// 找到访问顶点的一个邻接点
		EdgeNode node = vertex[locate(v)].next;

		while (node != null) {
			// 如果这个邻接点没有被访问，作为新顶点递归访问
			if (visited[node.index] == false) {
				dfs(vertex[node.index].verName);
			}
			// 遍历作为底层顶点的所有邻接点
			node = node.next;
		}
	}

	public static void main(String[] args) {
		DFS_AL al = new DFS_AL();
		al.creatList();
		al.dfs('A');
	}
}

深度优先遍历的时间复杂度及空间复杂度分析

时间复杂度
遍历图时，对图中的每个顶点最多调用一次dfs方法，某个顶点被标记访问过，就不再从它出发调用。因此遍历图的过程其实是对每个顶点查找其邻接点的过程。对于一个含有 n 个顶点和 e 条边的图：

  • 邻接矩阵因为对每个顶点 v 都要通过遍历一次一维数组 matrix[v][ ]找到它的所有邻接点，对应的时间复杂度 O ( n ) Ο(n) O(n)，所以总的时间复杂度 O ( n 2 ) Ο(n^2) O(n2)。
  • 邻接表因为本身存储的就是有相连关系的邻接点，所以查找所有顶点的邻接点的时间复杂度为 O ( e ) Ο(e) O(e)。又因为对每个顶点都要进行一次查找，所以总的时间复杂度 O ( n + e ) Ο(n+e) O(n+e)。

空间复杂度
都包括标记数组的空间和递归过程中开辟的系统空间栈。

2.广度优先搜索

广度优先搜索，Breadth First Search，简称BFS。

对一个连通图进行广度优先遍历的步骤是：

  1. 从图中的一个顶点 v v v 出发并访问。
  2. 访问顶点 v v v 的所有邻接点。
  3. 按照邻接点的访问顺序访问邻接点的所有邻接点。
  4. 重复步骤3，直到图中所有的顶点都被访问。

可以看出广度优先遍历是从图中的某个顶点出发，以这个顶点为中心由内往外一层一层的完成遍历，类似树的层序遍历。

因为根据算法先被访问的顶点的邻接点也先被访问，所以遍历过程需要借助队列来保存访问过的顶点。

邻接矩阵的广度优先遍历

上图的一个广度优先遍历序列为：ABCDEFGH。广度优先遍历得到的序列也不唯一，因为对一个顶点的所有邻接点进行访问的时候这些邻接点的先后访问顺序可以不同。

import java.util.LinkedList;
import java.util.Queue;

public class BFS_AM {
	char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };
	int[][] matrix = new int[8][8];

	// 创建邻接矩阵
	private void creatMartix() {
		matrix[locate('A')][locate('B')] = matrix[locate('B')][locate('A')] = 1;
		matrix[locate('B')][locate('D')] = matrix[locate('D')][locate('B')] = 1;
		matrix[locate('B')][locate('E')] = matrix[locate('E')][locate('B')] = 1;
		matrix[locate('D')][locate('H')] = matrix[locate('H')][locate('D')] = 1;
		matrix[locate('E')][locate('H')] = matrix[locate('H')][locate('E')] = 1;
		matrix[locate('A')][locate('C')] = matrix[locate('C')][locate('A')] = 1;
		matrix[locate('C')][locate('F')] = matrix[locate('F')][locate('C')] = 1;
		matrix[locate('C')][locate('G')] = matrix[locate('G')][locate('C')] = 1;
		matrix[locate('F')][locate('G')] = matrix[locate('G')][locate('F')] = 1;
	}

	private int locate(char v) {
		int i = 0;
		for (; i < vertex.length; i++) {
			if (v == vertex[i])
				break;
		}
		return i;
	}

	boolean[] visited = new boolean[vertex.length];
	// 辅助队列，保存访问过的顶点
	Queue<Character> q = new LinkedList<>();

	private void bfs(char v) {
		// 访问第一个顶点
		System.out.print(v + " ");
		// 访问标记
		visited[locate(v)] = true;
		// 访问过的顶点入队
		q.add(v);
		while(!q.isEmpty()) {
			char c =  q.remove();
			for(int i=0;i<matrix.length;i++) {
				// 访问出队顶点的所有未被访问过的邻接点
				if(matrix[locate(c)][i]==1 && visited[i]==false) {
					System.out.print(vertex[i]+" ");
					visited[i]=true;
					q.add(vertex[i]);
				}
			}
		}
	}

	public static void main(String[] args) {
		BFS_AM am = new BFS_AM();
		am.creatMartix();
		am.bfs('A');
	}
}

邻接表的广度优先遍历

import java.util.LinkedList;
import java.util.Queue;

public class BFS_AL {
	class VertexNode {
		char verName;
		EdgeNode next;

		public VertexNode(char verName) {
			this.verName = verName;
		}
	}

	class EdgeNode {
		int index;
		EdgeNode next;

		public EdgeNode(int index) {
			this.index = index;
		}
	}

	VertexNode[] vertex = { new VertexNode('A'), 
							new VertexNode('B'), 
							new VertexNode('C'), 
							new VertexNode('D'),
							new VertexNode('E'), 
							new VertexNode('F'), 
							new VertexNode('G'), 
							new VertexNode('H') };

	private int locate(char v) {
		int index = 0;
		for (; index < vertex.length; index++) {
			if (v == vertex[index].verName)
				break;
		}
		return index;
	}

	// 创建邻接表
	private void creatList() {
		vertex[locate('A')].next = new EdgeNode(locate('B'));
		vertex[locate('A')].next.next = new EdgeNode(locate('C'));

		vertex[locate('B')].next = new EdgeNode(locate('A'));
		vertex[locate('B')].next.next = new EdgeNode(locate('D'));
		vertex[locate('B')].next.next.next = new EdgeNode(locate('E'));

		vertex[locate('C')].next = new EdgeNode(locate('A'));
		vertex[locate('C')].next.next = new EdgeNode(locate('F'));
		vertex[locate('C')].next.next.next = new EdgeNode(locate('G'));

		vertex[locate('D')].next = new EdgeNode(locate('B'));
		vertex[locate('D')].next.next = new EdgeNode(locate('H'));

		vertex[locate('E')].next = new EdgeNode(locate('B'));
		vertex[locate('E')].next.next = new EdgeNode(locate('H'));

		vertex[locate('F')].next = new EdgeNode(locate('C'));
		vertex[locate('F')].next.next = new EdgeNode(locate('G'));

		vertex[locate('G')].next = new EdgeNode(locate('C'));
		vertex[locate('G')].next.next = new EdgeNode(locate('F'));

		vertex[locate('H')].next = new EdgeNode(locate('D'));
		vertex[locate('H')].next.next = new EdgeNode(locate('E'));
	}

	boolean[] visited = new boolean[vertex.length];
	Queue<Character> q = new LinkedList<>();

	private void bfs(char v) {
		// 访问第一个顶点
		System.out.print(v + " ");
		// 访问标记
		visited[locate(v)] = true;
		q.add(v);
		while (!q.isEmpty()) {
			char c = q.remove();
			// 找到访问顶点的第一个邻接点
			EdgeNode node = vertex[locate(c)].next;
			while (node != null) {
				// 邻接点存在访问并修改访问标记，并且将访问过的邻接点入队
				if (visited[node.index] == false) {
					System.out.print(vertex[node.index].verName + " ");
					visited[locate(vertex[node.index].verName)] = true;
					q.add(vertex[node.index].verName);
				}
				// 寻找访问顶点的下一个邻接点
				node = node.next;
			}
		}
	}

	public static void main(String[] args) {
		BFS_AL al = new BFS_AL();
		al.creatList();
		al.bfs('A');
	}
}

广度优先遍历的时间复杂度及空间复杂度分析

时间复杂度
广度优先遍历每个顶点最多进入一次队列，与深度优先的区别仅是对不同顶点邻接点的访问顺序不同，所以广度优先的时间复杂度与深度优先相等。

  • 对于邻接矩阵，广度优先的时间复杂度 O ( n 2 ) Ο(n^2) O(n2)。
  • 对于邻接表，广度优先的时间复杂度 O ( n + e ) Ο(n+e) O(n+e)。

空间复杂度
与深度优先相比少用了递归时占用的系统空间栈，多了一个辅助队列。

相关标签： 数据结构与算法

上一篇： LeetCode 993. 二叉树的堂兄弟节点（前序遍历判断是否一个父亲+层次遍历判断是否在同一层）

下一篇： LeetCode 103. 二叉树的锯齿形层次遍历(层序遍历加一个变量判断奇偶数层)

推荐阅读