与图相关的一些算法
与图相关的一些算法
作者：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;
}
}
