Обход графов очень важен для таких задач, как графы, но реализация графов очень сложна. Здесь я представляю обход в ширину и обход в глубину на следующем рисунке и рассказываю об идее алгоритма.
1. Структура хранения графа
Матрица соседних представляет:
Структура хранения матрицы смежности FIG определяется следующим образом:
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 (n ^ 2), а пространственная сложность также равна O (n ^ 2). n представляет количество вершин в графе.
В списке смежности написано:
Структура хранения списка смежности графа определяется следующим образом:
//顶点的数量
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);
}
}
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);
}
}