与图相关的一些算法
2023-02-18 16:35:16 时间
与图相关的一些算法
作者: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;
}
}
更多
参考资料
相关文章
- abp(net core)+easyui+efcore实现仓储管理系统——EasyUI前端页面框架 (十八)
- 结对编程,到底是双剑合璧还是脚趾抠地?
- 个性化联邦学习算法框架发布,赋能AI药物研发
- 2021年中国DevOps现状调查报告发布!
- 以两种异步模型应用案例,深度解析Future接口
- AI论文解读丨融合视觉、语义、关系多模态信息的文档版面分析架构VSR
- 云图说 | 华为云医疗智能体,智联大健康,AI药物研发
- 带你走进“华为链”
- Vue组件间的传值五大场景,你造吗?
- 初学者入门知识图谱必看的能力:推理
- 带你探索CPU调度的奥秘
- 鸿蒙轻内核定时器Swtmr:不受硬件和数量限制,满足用户需求
- 云图说|云上应用监控神器——应用性能监控APM2.0
- 带你了解弯曲文本检测算法的两种思路:区域重组和像素分割
- 带你认识MindSpore量子机器学习库MindQuantum
- 论文解读丨Zero-Shot场景下的信息结构化提取
- CWE发布2021年最危险的25种软件缺陷
- AI开发者十问:10分钟了解AI开发的基本过程
- 队列Queue:任务间的消息读写,安排起来~
- 云图说|ROMA演进史:一个ROMA与应用之间不得不说的故事