與圖相關的一些算法
與圖相關的一些算法
作者：Grey
原文地址：
圖的說明
線性表中的元素是「一對一」的關係，樹中的元素是「一對多」的關係，圖結構中的元素則是「多對多」的關係。
圖（Graph）是一種複雜的非線性結構，在圖結構中，每個元素都可以有零個或多個前驅，也可以有零個或多個後繼，也就是說，元素之間的關係是任意的。
圖中包括點集和邊集，可以用以下代碼來表示
點
import java.util.ArrayList;
public class Node {
// 點的值
public int value;
// 入度
public int in;
// 出度
public int out;
// 鄰居節點
public ArrayList<Node> nexts;
// 鄰邊
public ArrayList<Edge> edges;
public Node(int value) {
this.value = value;
in = 0;
out = 0;
nexts = new ArrayList<>();
edges = new ArrayList<>();
}
}
邊
public class Edge {
// 權值
public int weight;
// 起點
public Node from;
// 終點
public Node to;
public Edge(int weight, Node from, Node to) {
this.weight = weight;
this.from = from;
this.to = to;
}
}
圖
import java.util.HashMap;
import java.util.HashSet;
public class Graph {
// 點集
public HashMap<Integer, Node> nodes;
// 邊集
public HashSet<Edge> edges;
public Graph() {
nodes = new HashMap<>();
edges = new HashSet<>();
}
}
以上只是一種圖的定義方式，每個人可以根據自己的習慣來定義自己熟悉的圖數據結構，面對一個不熟悉的圖結構，可以通過寫一個轉換方法來將不熟悉的圖結構轉換成自己熟悉的圖結構。
比如，一個整數類型的二維矩陣也可以表示圖，見圖的二維數組表示，
我們可以通過寫一個轉換函數把二維數組的圖轉換成自己熟悉的圖結構
// 二維數組轉換成自己熟悉的圖結構
public class GraphGenerator {
public static Graph createGraph(Integer[][] matrix) {
Graph graph = new Graph();
for (int i = 0; i < matrix.length; i++) {
// matrix[0][0], matrix[0][1] matrix[0][2]
Integer weight = matrix[i][0];
Integer from = matrix[i][1];
Integer to = matrix[i][2];
if (!graph.nodes.containsKey(from)) {
graph.nodes.put(from, new Node(from));
}
if (!graph.nodes.containsKey(to)) {
graph.nodes.put(to, new Node(to));
}
Node fromNode = graph.nodes.get(from);
Node toNode = graph.nodes.get(to);
Edge newEdge = new Edge(weight, fromNode, toNode);
fromNode.nexts.add(toNode);
fromNode.out++;
toNode.in++;
fromNode.edges.add(newEdge);
graph.edges.add(newEdge);
}
return graph;
}
}
圖的深度優先遍歷(DFS)
流程如下
-
利用棧實現;
-
從源節點開始把節點按照深度放入棧，然後彈出;
-
每彈出一個點，把該節點下一個沒有進過棧的鄰接點放入棧;
-
直到棧變空。
完整代碼如下
import snippet.graph.Node;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Code_DFS {
// 迭代版本
public static List<Node> dfs(Node node) {
if (node == null) {
return new ArrayList<>();
}
List<Node> ans = new ArrayList<>();
Deque<Node> stack = new ArrayDeque<>();
HashSet<Node> set = new HashSet<>();
stack.add(node);
set.add(node);
ans.add(node);
while (!stack.isEmpty()) {
Node cur = stack.pop();
for (Node next : cur.nexts) {
if (!set.contains(next)) {
stack.push(cur);
stack.push(next);
set.add(next);
ans.add(next);
break;
}
}
}
return ans;
}
// 遞歸版本
public static List<Node> dfs2(Node node) {
if (node == null) {
return new ArrayList<>();
}
List<Node> ans = new ArrayList<>();
Set<Node> set = new HashSet<>();
dfs(node, ans, set);
return ans;
}
private static void dfs(Node node, List<Node> ans, Set<Node> set) {
ans.add(node);
set.add(node);
if (node.nexts != null && !node.nexts.isEmpty()) {
for (Node n : node.nexts) {
if (!set.contains(n)) {
dfs(n, ans, set);
}
}
}
}
}
圖的寬度優先遍歷(BFS)
流程如下
-
利用隊列實現；
-
從源節點開始依次按照寬度進隊列，然後彈出；
-
每彈出一個點，把該節點所有沒有進過隊列的鄰接點放入隊列；
-
直到隊列變空。
import snippet.graph.Node;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Code_BFS {
public static List<Node> bfs(Node node) {
if (null == node) {
return new ArrayList<>();
}
List<Node> ans = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
HashSet<Node> set = new HashSet<>();
queue.offer(node);
set.add(node);
while (!queue.isEmpty()) {
Node cur = queue.poll();
// System.out.println(cur.value);
ans.add(cur);
if (cur.nexts != null && !cur.nexts.isEmpty()) {
for (Node t : cur.nexts) {
if (!set.contains(t)) {
queue.offer(t);
set.add(t);
}
}
}
}
return ans;
}
}
