图的BFS和DFS
2019-06-24 本文已影响0人
Michaelhbjian
图的遍历对于图这类题目来说非常重要，但是图的实现又非常的难。在这里我介绍下图的广度优先遍历和深度优先遍历，讲一下其中的算法思想。
1.图的存储结构
邻接矩阵表示：
DA2A674FD8873E6A42FFC1BCE0DFCD26.jpg
图的邻接矩阵存储结构定义如下：
int n;
boolean[][] a;
Node(int n){
this.n=n;
a = new boolean[n][n];
}
void addEdge(int i, int j) {
a[i][j] = true;
}
void removeEdge(int i, int j) {
a[i][j] = false;
}
boolean hasEdge(int i, int j) {
return a[i][j];
}
邻接矩阵表示法的时间复杂度为O(n2)，空间复杂度也是O(n2)。n代表图中顶点的个数。
邻接表表示：
BA4F709248944B0E15982967F382428A.jpg
图的邻接表存储结构定义如下：
//顶点的数量
private int V;
//邻接表-数组类型的链表
private LinkedList<Integer> adj[];
//构造一个图
DepthFirstSearch(int v){
V = v;
//数组链表
adj = new LinkedList[v];
for (int i = 0; i < v; i++) {
adj[i]=new LinkedList();
}
}
//加入与顶点v相连的边v-w
void addEdge(int v,int w){
adj[v].add(w);
}
时间复杂度为：O（V + E）其中V是图中顶点的数量，E是图中边的数量 。
还是看以前的书比较有亲和感！
2.广度优先遍历（Breadth-First-Search，BFS）
广度优先遍历类似与二叉树的层序遍历。它是一种分层的查找过程，每向前走一步能访问一批顶点，不像深度优先遍历那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问顶点的下一层顶点。
package com.zhoujian.solutions.dataStructure.graph;
import java.util.*;
/**
* @author zhoujian123@hotmail.com 2018/4/26 10:28
* 图的广度优先遍历----借助队列
* 广度优先遍历类似于二叉树的层序遍历
* 图是用邻接表来存储（对于稀疏图来说，邻接表比较合适）
* 时间复杂度：O(V+E)，其中V是图中顶点的数量，E是图中边的数量
*/
public class BreadthFirstSerch {
private int V; //顶点
private LinkedList<Integer> adj[]; //领接表
//构造器，利用链表。v是顶点的个数
BreadthFirstSerch(int v){
V=v;
adj = new LinkedList[v];
for (int i = 0; i <v; i++) {
adj[i]=new LinkedList();
}
}
//加入一条边到图中
void addEdge(int v,int w){
adj[v].add(w);
}
//从给定的顶点开始遍历
void BFS(int s){
//默认将所有的顶点设置为未被访问（false）
boolean visited[] = new boolean[V];
//创建一个队列
LinkedList<Integer> queue = new LinkedList<Integer>();
//把当前顶点设置为已访问并且入队
visited[s] = true;
queue.add(s);
while (queue.size()!=0){
//出队并打印出来
s=queue.poll();
System.out.println(s+"");
//获取与s相关联的全部的顶点，如果邻接的点未被访问，则设置为已被访问且入队
//i是一种list列表的迭代器，用于存储相邻节点的列表
ListIterator<Integer> i = adj[s].listIterator();
while (i.hasNext()){
int n = i.next();
if (!visited[n]){
visited[n]=true;
queue.add(n);
}
}
}
}
public static void main(String[] args) {
BreadthFirstSerch g = new BreadthFirstSerch(4);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,2);
g.addEdge(2,0);
g.addEdge(2,3);
g.addEdge(3,3);
//这个函数只能从指定顶点开始遍历。要是打印所有顶点，可以需要修改BFS函数，逐个从所有节点开始遍历
System.out.println("广度优先遍历从0开始遍历");
g.BFS(0);
System.out.println("广度优先遍历从1开始遍历");
g.BFS(1);
System.out.println("广度优先遍历从2开始遍历");
g.BFS(2);
System.out.println("广度优先遍历从3开始遍历");
g.BFS(3);
}
}
image.png
3.深度优先遍历（Depath-First-Search，DFS）
深度优先遍历类似于树的先序遍历。DFS算法是一个递归的算法，需要借助一个递归的工作栈，故它的空间复杂度为O(V)。总的时间复杂度为O(V+E)。
package com.zhoujian.solutions.dataStructure.graph;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
/**
* @author zhoujian123@hotmail.com 2018/4/25 21:19
* 图的深度优先遍历：需要借助栈
* 深度优先遍历类似于二叉树的先序遍历
* 使用邻接表表示
* 时间复杂度：当以领接表表示时，查找所有顶点的邻接点所需为O(V)，然后每条边至少访问一次所需时间为O(E),
* 总的时间复杂度为O(V+E)
*
*/
public class DepthFirstSearch {
//顶点的数量
private int V;
//邻接表-数组类型的链表
private LinkedList<Integer> adj[];
//构造一个图
DepthFirstSearch(int v){
V = v;
//数组链表
adj = new LinkedList[v];
for (int i = 0; i < v; i++) {
adj[i]=new LinkedList();
}
}
//加入与顶点v相连的边v-w
void addEdge(int v,int w){
adj[v].add(w);
}
/**
* 从顶点v开始深度遍历
* @param v 顶点v
* @param visited 访问标识符
*/
void DFSUtil(int v,boolean visited[]){
//把当前节点设置为被访问并打印出来
visited[v]=true;
System.out.println(v+" ");
ListIterator<Integer> i = adj[v].listIterator();
while (i.hasNext()){
//返回与v相邻的节点
Integer n = i.next();
if (!visited[n]){
DFSUtil(n,visited);
}
}
}
void DFS(int v){
//初始化所有顶点并默认为false（数组）
boolean[] visited = new boolean[V];
DFSUtil(v,visited);
}
public static void main(String[] args) {
DepthFirstSearch g = new DepthFirstSearch(4);
g.addEdge(0,1);
g.addEdge(0,2);
g.addEdge(1,2);
g.addEdge(2,0);
g.addEdge(2,3);
g.addEdge(3,3);
System.out.println("深度优先遍历从顶点2开始");
g.DFS(2);
}
}
image.png
