探索图论中的关键算法(Java 实现)

“日出东海落西山 愁也一天 喜也一天 遇事不钻牛角尖”

文章目录

  • 前言
    • 文章有误敬请斧正 不胜感恩!||Day03
    • 1. 最短路径算法
      • Dijkstra算法
        • Java 实现:
      • Bellman-Ford算法
        • Java 实现:
    • 2. 最小生成树算法
      • Prim算法
        • Java 实现:
      • Kruskal算法
        • Java 实现:
    • 3. 二分图的最大匹配
      • 匈牙利算法
        • Java 实现:
    • 4. 网络流
      • Dinic算法
        • Java 实现:
  • 总结


前言

今天讲什么?:

图论是计算机科学中一个非常重要的分支,在困难题中,很多时候图论算法都能提供有效的解决方案。
通过学习这些经典的图论算法,我们可以更好地理解有关:
如何用最优的方式在节点和边之间进行数据传递的算法问题。

本文将带你初步探索图论中的几种核心算法,如最短路径算法、最小生成树、二分图匹配、网络流等,并通过Java语言为这些算法提供通俗易懂的实现和讲解。即使你对图论的理解有限,本文也会帮助你轻松掌握这些关键的算法和它们的实际应用场景。并给出我常用的模板供大家参考.


文章有误敬请斧正 不胜感恩!||Day03

提示:以下是本篇文章正文内容,


在这里插入图片描述


图论是计算机科学中的一个重要领域,涉及节点(顶点)和边的相关问题。本文深入探讨了几个关键的图论算法,包括最短路径算法、最小生成树、图匹配算法以及网络流算法,所有的实现都使用Java语言编写。

1. 最短路径算法

最短路径算法用于在加权图中寻找从一个节点到其他节点的最短路径。它们被广泛应用于GPS系统、网络路由等场景。

Dijkstra算法

Dijkstra算法用于找到带有非负权重的图中从源节点到其他节点的最短路径。该算法使用优先队列来扩展当前已知的最短距离。

Java 实现:
import java.util.*;class Dijkstra {static final int INF = Integer.MAX_VALUE;static List<List<int[]>> adj = new ArrayList<>();static int[] dist;static boolean[] visited;static void dijkstra(int start, int n) {dist = new int[n];visited = new boolean[n];Arrays.fill(dist, INF);PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));dist[start] = 0;pq.add(new int[]{0, start});while (!pq.isEmpty()) {int[] curr = pq.poll();int u = curr[1];if (visited[u]) continue;visited[u] = true;for (int[] edge : adj.get(u)) {int v = edge[0], weight = edge[1];if (dist[v] > dist[u] + weight) {dist[v] = dist[u] + weight;pq.add(new int[]{dist[v], v});}}}}public static void main(String[] args) {// 初始化图int n = 5;for (int i = 0; i < n; i++) adj.add(new ArrayList<>());// 添加边 (节点, 权重)adj.get(0).add(new int[]{1, 2});adj.get(1).add(new int[]{2, 1});adj.get(0).add(new int[]{2, 4});dijkstra(0, n);System.out.println(Arrays.toString(dist));}
}

Bellman-Ford算法

Bellman-Ford算法可以处理包含负权重的图,它通过多次松弛所有的边来寻找最短路径,并检测是否存在负权重环。

Java 实现:
import java.util.Arrays;class BellmanFord {static class Edge {int u, v, w;Edge(int u, int v, int w) {this.u = u;this.v = v;this.w = w;}}static final int INF = Integer.MAX_VALUE;static Edge[] edges;static int[] dist;static int n, m;static void bellmanFord(int start) {dist = new int[n];Arrays.fill(dist, INF);dist[start] = 0;for (int i = 0; i < n - 1; i++) {for (Edge e : edges) {if (dist[e.u] != INF && dist[e.u] + e.w < dist[e.v]) {dist[e.v] = dist[e.u] + e.w;}}}}public static void main(String[] args) {n = 5; m = 5;edges = new Edge[]{new Edge(0, 1, -1),new Edge(0, 2, 4),new Edge(1, 2, 3),new Edge(1, 3, 2),new Edge(1, 4, 2)};bellmanFord(0);System.out.println(Arrays.toString(dist));}
}

2. 最小生成树算法

最小生成树(MST)是涵盖图中所有顶点且具有最小边权重和的树。它们广泛应用于网络设计问题,如道路、通信网络的构建等。

Prim算法

Prim算法通过逐步扩展当前树的最小边来构建MST,适用于密集图。

Java 实现:
import java.util.Arrays;class Prim {static final int INF = Integer.MAX_VALUE;static int[][] graph;static boolean[] visited;static int[] dist;static int prim(int n) {dist = new int[n];visited = new boolean[n];Arrays.fill(dist, INF);dist[0] = 0;int res = 0;for (int i = 0; i < n; i++) {int t = -1;for (int j = 0; j < n; j++) {if (!visited[j] && (t == -1 || dist[j] < dist[t])) t = j;}if (dist[t] == INF) return -1;visited[t] = true;res += dist[t];for (int j = 0; j < n; j++) {dist[j] = Math.min(dist[j], graph[t][j]);}}return res;}public static void main(String[] args) {int n = 5;graph = new int[n][n];for (int[] row : graph) Arrays.fill(row, INF);graph[0][1] = 2;graph[1][2] = 3;graph[0][2] = 1;System.out.println(prim(n));}
}

Kruskal算法

Kruskal算法是一种贪心算法,通过排序所有边并不断选择最小边来构建MST,确保不会形成环。

Java 实现:
import java.util.*;class Kruskal {static class Edge implements Comparable<Edge> {int u, v, weight;Edge(int u, int v, int weight) {this.u = u;this.v = v;this.weight = weight;}public int compareTo(Edge other) {return Integer.compare(this.weight, other.weight);}}static int[] parent;static int find(int x) {if (parent[x] != x) parent[x] = find(parent[x]);return parent[x];}static void union(int u, int v) {parent[find(u)] = find(v);}static int kruskal(List<Edge> edges, int n) {Collections.sort(edges);parent = new int[n];for (int i = 0; i < n; i++) parent[i] = i;int mstWeight = 0;for (Edge e : edges) {if (find(e.u) != find(e.v)) {mstWeight += e.weight;union(e.u, e.v);}}return mstWeight;}public static void main(String[] args) {List<Edge> edges = new ArrayList<>();edges.add(new Edge(0, 1, 10));edges.add(new Edge(1, 2, 6));edges.add(new Edge(0, 2, 5));System.out.println(kruskal(edges, 3));}
}

3. 二分图的最大匹配

最大匹配问题涉及将二分图中两个不相交的集合顶点进行配对,以使配对数最大。

匈牙利算法

匈牙利算法用于求解二分图中的最大匹配问题。

Java 实现:
import java.util.*;class Hungarian {static List<List<Integer>> adj = new ArrayList<>();static int[] match;static boolean[] visited;static int n;static boolean dfs(int u) {for (int v : adj.get(u)) {if (!visited[v]) {visited[v] = true;if (match[v] == -1 || dfs(match[v])) {match[v] = u;return true;}}}return false;}static int hungarian() {match = new int[n];Arrays.fill(match, -1);int result = 0;for (int i = 0; i < n; i++) {visited = new boolean[n];if (dfs(i)) result++;}return result;}public static void main(String[] args) {n = 5;for (int i = 0; i < n; i++) adj.add(new ArrayList<>());adj.get(0).add(1);adj.get(1).add(2);System.out.println(hungarian());}
}

4. 网络流

网络流算法解决的是关于网络中的传输、循环和流量分配问题。

Dinic算法

Dinic算法通过构建分层图和阻塞流来高效地求解最大流问题。

Java 实现:
import java.util.*;class Dinic {static class Edge {int v, flow, capacity;Edge rev;Edge(int v, int capacity) {this.v = v;this.capacity = capacity;this.flow = 0;}}static List<List<Edge>> adj = new ArrayList<>();static int[] level;static int n;static void addEdge(int u, int v, int capacity) {Edge uv = new Edge(v, capacity);Edge vu = new Edge(u, 0);uv.rev = vu;vu.rev = uv;adj.get(u).add(uv);adj.get(v).add(vu);}static boolean bfs(int s, int t) {Arrays.fill(level, -1);Queue<Integer> q = new LinkedList<>();level[s] = 0;q.add(s);while (!q.isEmpty()) {int u = q.poll();for (Edge e : adj.get(u)) {if (level[e.v] == -1 && e.flow < e.capacity) {level[e.v] = level[u] + 1;q.add(e.v);}}}return level[t] != -1;}static int dfs(int u, int t, int flow) {if (u == t) return flow;int totalFlow = 0;for (Edge e : adj.get(u)) {if (level[e.v] == level[u] + 1 && e.flow < e.capacity) {int currFlow = dfs(e.v, t, Math.min(flow, e.capacity - e.flow));if (currFlow > 0) {e.flow += currFlow;e.rev.flow -= currFlow;totalFlow += currFlow;flow -= currFlow;if (flow == 0) break;}}}return totalFlow;}static int dinic(int s, int t) {int maxFlow = 0;level = new int[n];while (bfs(s, t)) {maxFlow += dfs(s, t, Integer.MAX_VALUE);}return maxFlow;}public static void main(String[] args) {n = 6;for (int i = 0; i < n; i++) adj.add(new ArrayList<>());addEdge(0, 1, 16);addEdge(0, 2, 13);addEdge(1, 2, 10);addEdge(2, 3, 14);addEdge(3, 4, 7);System.out.println(dinic(0, 4));}
}

总结

在这里插入图片描述


通过本文的学习,我们深入探讨了图论中的几个核心算法,并且用Java进行了详细的实现。这些算法不仅仅是理论上的工具,它们在实际问题中有着广泛的应用:

  • 最短路径算法 帮助我们在各种网络中找到最有效的传输路径,比如导航系统或通信网络。
  • 最小生成树算法 能帮助我们以最低成本构建网络,广泛应用于电网、道路建设等。
  • 二分图匹配算法 则在资源分配、任务调度等问题中提供了最佳的解决方案。
  • 网络流算法 通过优化资源流动,解决了物流、流量控制等领域中的实际问题。

掌握这些经典算法,
记住这些模板
不仅能提升帮我们打比赛,还可以为我们在实际开发中提供强大的工具。
希望通过本文的学习,图论算法我们已经初步了解了
多做题,并不断应用才能更好的掌握.

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/424461.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++速通LeetCode简单第9题-二叉树的最大深度

深度优先算法递归&#xff1a; /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right…

Conmi的正确答案——MySQL的层级递归查询(递归公共表表达式,CTE)

数据库&#xff1a;oceanbase-ce 递归sql主体&#xff1a; WITH RECURSIVE country_area_tree AS (-- 非递归部分&#xff0c;初始化查询SELECT id, area_name, parent_id, 0 AS levelFROM country_areaWHERE id 589004044419077UNION ALL-- 递归部分&#xff0c;找到子节点S…

聚类_K均值

import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import make_blobs1.数据预处理 #创建基于高斯分布的样本点, x是点的坐标&#xff0c;y是所属聚类值 x, y make_blobs(n_samples100, centers6, random_state100, cluster_std0.6) # 设置图形尺寸…

2. 变量和指令(omron 机器自动化控制器)——1

机器自动化控制器——第二章 变量和指令 1 2-1 变量一览表MC通用变量轴变量▶ 轴组变量 运动控制指令的输入变量输入变量的有效范围▶ 枚举体一览表 运动控制指令的输出变量运动控制指令的输入输出变量 2-1 变量一览表 MC功能模块使用的变量分为两类。 一类是监视轴等的状态及…

电脑提示丢失mfc140u.dll的详细解决方案,mfc140u.dll文件是什么

遇到电脑显示“缺少 mfc140u.dll 文件”的错误其实是比较常见的。这种提示通常表示某个应用程序在尝试运行时未能找到它所需的关键 DLL 文件&#xff0c;导致无法正常启动。不过&#xff0c;别担心&#xff0c;本文将一步步引导你通过几种不同的方法来解决这个问题&#xff0c;…

VSCode拉取远程项目

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…

el-input设置后缀显示单位并阻止滚轮微调

项目中收集form表单信息时&#xff0c;有时会需要在el-input后面显示单位&#xff0c;效果如图&#xff1a; 当然&#xff0c;我们可以直接在输入框后面加上单位&#xff0c;但直接给输入框上加单位不管是视图上还是用户体验上看起来都要好一点 element-plus / element-ui给我…

[基于 Vue CLI 5 + Vue 3 + Ant Design Vue 4 搭建项目] 01 安装 nodejs 环境

文章目录 下载安装测试 这里让我们去看看如何安装一下 nodejs 的环境 下载 通过官网进行下载安装包 官网 https://nodejs.org/zh-cn点击 下载 Node.js (LTS) 开始下载 安装 下载完成之后&#xff0c;双击进行安装 开始进行安装了 这样&#xff0c;node.js 就安装好了 测试 …

unity3d入门教程三

unity3d入门教程三 8.1游戏脚本8.2脚本的使用8.3认识脚本组件8.4帧率9.1游戏脚本9.2获取节点和组件9.3MonoBehaviour9.4父节点与子节点9.5组件的属性9.6脚本的单步调试 8.1游戏脚本 通过程序控制对象属性&#xff08;如运动&#xff0c;修改transform的位置属性&#xff09; …

SpringCloudAlibaba:Seata

1. 面试题 2.1 你简历上写用微服务boot/cloud做过项目&#xff0c;你不可能只有一个数据库吧&#xff1f;谈谈多个数据库之间如何处理分布式事务&#xff1f; 2.2 阿里巴巴的Seata-AT模式如何做到对业务的无侵入&#xff1f; 在一阶段&#xff0c;Seata 会拦截“业务 SQL”&a…

逆向学习系列(三)adb的使用

由于是记录学习&#xff0c;我就用结合自己的理解&#xff0c;用最通俗的语言进行讲解。 adb是android debug bridge的简写&#xff0c;其作用就是将电脑和手机相连接&#xff0c;用电脑控制手机。 一、adb哪里来 我使用的adb一般都是安装模拟器的时候&#xff0c;模拟器自带…

MySQL基础——DQL

DQL&#xff08;Data Query Language&#xff0c;数据查询语言&#xff09;是SQL中的一个子集&#xff0c;主要用于查询数据库中的数据。DQL的核心语句是 SELECT&#xff0c;它用于从一个或多个表中提取数据&#xff0c;并能够通过各种条件进行过滤、排序和聚合操作。下面是DQL…

【学习笔记】手写Tomcat 二

目录 响应静态资源 HTTP协议请求格式 1. 解析请求信息 创建解析请求类 HttpRequest 2. 创建静态资源目录 webs 3. 封装响应信息 创建静态资源处理器 StaticResourceHandler 创建响应类 HttpResponse 然后就可以调用响应类了 测试 静态资源的路径说明 作业 1. 绘制…

JNI 详细介绍

一 介绍 java调⽤c&#xff0c;c代码可以通过JNIEnv执行java代码。 安卓NDK 已经对JNI环境进行了集成&#xff0c;我们可以通过android studio来快速搭建一个项目。 二 项目搭建 打开android studio 创建工程&#xff0c;创建工程选择模板Native C 三 模板格式介绍 生成的…

非关系型数据库Redis

文章目录 一&#xff0c;关系型数据库和非关系型数据可区别1.关系型数据库2.非关系型数据库3.区别3.1存储方式3.2扩展方式3.2事务性的支持 二&#xff0c;非关系型数据为什么产生三&#xff0c;Redis1.Redis是什么2.Redis优点3.Redis适用范围4. Redis 快的原因4.1 基于内存运行…

直播标准权威发布,阿里云RTS获首批卓越级评估认证

近期举办的2024“可信云大会”上&#xff0c;中国信通院正式发布了2024年上半年音视频领域最新评估结果。阿里云超低延时直播&#xff0c;以首批卓越级&#xff0c;通过中国信通院超低延时直播性能及服务质量分级测试。 标准发布&#xff0c;权威量化直播体验质量 从直播元年发…

神经网络通俗理解学习笔记(0) numpy、matplotlib

Numpy numpynumpy 基本介绍Ndarray对象及其创建Numpy数组的基础索引numpy数组的合并与拆分&#xff08;重要&#xff09;numpy数组的矩阵运算Numpy数组的统计运算numpy中的arg运算numpy中的神奇索引和比较 Matplotlib numpy numpy 基本介绍 numpy 大多数机器学习库都用了这个…

【Echarts】使用多横坐标轴展示近十五天天气预报

现在手机都有天气app,使用echarts展示十五天天气预报的需要你遇到过这样离大谱的需求吗&#xff1f;如果没有或许你能从中找到些许思路。 效果 看效果是不是有点那么个意思,开局一张图,代码全靠ctrl c。不多说上代码。 vue模板引擎代码 <template><div ref"xA…

从头开始学MyBatis—02基于xml和注解分别实现的增删改查

首先介绍此次使用的数据库结构&#xff0c;然后引出注意事项。 通过基于xml和基于注解的方式分别实现了增删改查&#xff0c;还有获取参数值、返回值的不同类型对比&#xff0c;帮助大家一次性掌握两种代码编写能力。 目录 数据库 数据库表 实体类 对应的实体类如下&#x…

【LeetCode每日一题】——912.排序数组

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 优先队列 二【题目难度】 中等 三【题目编号】 912.排序数组 四【题目描述】 给你一个整数…