【算法基础实验】图论-构建无向图

2024-04-26 19:36

本文主要是介绍【算法基础实验】图论-构建无向图,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

构建无向图

前提

JAVA实验环境

理论

无向图的数据结构为邻接表数组,每个数组中保存一个Bag抽象数据类型(Bag类型需要专门讲解)
在这里插入图片描述

实验数据

我们的实验数据是13个节点和13条边组成的无向图,由一个txt文件来保存,本实验的目的就是将这个txt文件的图构建出来,并且依次打印出每个节点的所有邻接节点

实验数据下载地址: https://algs4.cs.princeton.edu/code/algs4-data.zip

在这里插入图片描述

完整代码

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;public class myGraph
{private final int V;private int E;private myBag<Integer>[] adj;private static final String NEWLINE = System.getProperty("line.separator");public myGraph(int V){this.V = V; this.E = 0;adj = (myBag<Integer>[]) new myBag[V];for (int v = 0; v < V; v++){adj[v] = new myBag<Integer>();}}public myGraph(In in){this(in.readInt());int E = in.readInt();for (int i = 0; i < E; i++){int v = in.readInt();int w = in.readInt();addEdge(v, w);}}public int V() { return V; }public int E() { return E; }public void addEdge(int v, int w){adj[v].add(w);adj[w].add(v);E++;}public Iterable<Integer> adj(int v){ return adj[v]; }public String toString() {StringBuilder s = new StringBuilder();s.append(V + " vertices, " + E + " edges " + NEWLINE);for (int v = 0; v < V; v++) {s.append(v + ": ");for (int w : adj[v]) {s.append(w + " ");}s.append(NEWLINE);}return s.toString();}public static void main(String[] args) {In in = new In(args[0]);myGraph G = new myGraph(in);StdOut.println(G);}
}

代码解读

这段代码是一个用Java编写的图(Graph)数据结构的实现。下面是对这段代码的逐行解读,可以帮助你向其他人详细介绍这个程序:

类定义

public class myGraph

这行定义了一个名为 myGraph 的类,用于表示一个无向图。

成员变量

private final int V;   // 图的顶点数
private int E;         // 图的边数
private myBag<Integer>[] adj; // 邻接表数组
private static final String NEWLINE = System.getProperty("line.separator"); // 系统换行符
  • V 是图的顶点数,定义为 final 因为一旦图被创建顶点数是不变的。
  • E 是图的边数。
  • adj 是一个数组,每个索引处的元素是一个 myBag<Integer> 类型,用来存储与每个顶点相邻的顶点列表,实现邻接表。
  • NEWLINE 是系统相关的换行符,用于输出。

构造方法

public myGraph(int V

这是一个构造方法,接受一个整数 V 作为参数,初始化一个有 V 个顶点但没有边的图。

this.V = V; this.E = 0;
adj = (myBag<Integer>[]) new myBag[V];
for (int v = 0; v < V; v++) {adj[v] = new myBag<Integer>();
}
  • 初始化顶点数 V 和边数 E
  • 创建邻接表数组,每个顶点对应一个新的空 myBag 对象。

从输入流构造图

public myGraph(In in)

这个构造方法从输入流 in 构建图。首先读取顶点数和边数,然后读取每一条边的两个顶点,并调用 addEdge 方法添加边。

this(in.readInt()); // 初始化图的顶点
int E = in.readInt(); // 读取边数
for (int i = 0; i < E; i++) {int v = in.readInt(); // 读取一条边的起点int w = in.readInt(); // 读取一条边的终点addEdge(v, w); // 添加边
}

方法定义

public int V() { return V; }
public int E() { return E; }

这两个方法分别返回图的顶点数和边数。

public void addEdge(int v, int w)

此方法用于添加一条连接顶点 vw 的边,并更新邻接表和边数。

adj[v].add(w);
adj[w].add(v);
E++;
  • 在顶点 vw 的邻接表中互相添加对方。
  • 边数 E 自增。
public Iterable<Integer> adj(int v)
{ return adj[v]; }

这个方法返回顶点 v 的邻接顶点列表。

toString 方法

public String toString() {StringBuilder s = new StringBuilder();s.append(V + " vertices, " + E + " edges " + NEWLINE);for (int v = 0; v < V; v++) {s.append(v + ": ");for (int w : adj[v]) {s.append(w + " ");}s.append(NEWLINE);}return s.toString();
}

这个方法返回图的字符串表示形式,包含所有顶点和它们的邻接顶点。

main 方法

public static void main(String[] args) {In in = new In(args[0]);myGraph G = new myGraph(in);StdOut.println(G);
}

main 方法从文件读取图数据,创建 myGraph 实例,并打印图的内容。

这段代码完整地展示了如何在Java中实现一个简单的无向图数据结构,并提供了读取图数据

实验

java myGraph data\tinyG.txt
13 vertices, 13 edges 
0: 6 2 1 5 
1: 0 
2: 0 
3: 5 4 
4: 5 6 3 
5: 3 4 0 
6: 0 4 
7: 8
8: 7
9: 11 10 12
10: 9
11: 9 12
12: 11 9

参考资料

算法(第4版)人民邮电出版社

这篇关于【算法基础实验】图论-构建无向图的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/938472

相关文章

Three.js构建一个 3D 商品展示空间完整实战项目

《Three.js构建一个3D商品展示空间完整实战项目》Three.js是一个强大的JavaScript库,专用于在Web浏览器中创建3D图形,:本文主要介绍Three.js构建一个3D商品展... 目录引言项目核心技术1. 项目架构与资源组织2. 多模型切换、交互热点绑定3. 移动端适配与帧率优化4. 可

从基础到高级详解Python数值格式化输出的完全指南

《从基础到高级详解Python数值格式化输出的完全指南》在数据分析、金融计算和科学报告领域,数值格式化是提升可读性和专业性的关键技术,本文将深入解析Python中数值格式化输出的相关方法,感兴趣的小伙... 目录引言:数值格式化的核心价值一、基础格式化方法1.1 三种核心格式化方式对比1.2 基础格式化示例

redis-sentinel基础概念及部署流程

《redis-sentinel基础概念及部署流程》RedisSentinel是Redis的高可用解决方案,通过监控主从节点、自动故障转移、通知机制及配置提供,实现集群故障恢复与服务持续可用,核心组件包... 目录一. 引言二. 核心功能三. 核心组件四. 故障转移流程五. 服务部署六. sentinel部署

从基础到进阶详解Python条件判断的实用指南

《从基础到进阶详解Python条件判断的实用指南》本文将通过15个实战案例,带你大家掌握条件判断的核心技巧,并从基础语法到高级应用一网打尽,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录​引言:条件判断为何如此重要一、基础语法:三行代码构建决策系统二、多条件分支:elif的魔法三、

Python WebSockets 库从基础到实战使用举例

《PythonWebSockets库从基础到实战使用举例》WebSocket是一种全双工、持久化的网络通信协议,适用于需要低延迟的应用,如实时聊天、股票行情推送、在线协作、多人游戏等,本文给大家介... 目录1. 引言2. 为什么使用 WebSocket?3. 安装 WebSockets 库4. 使用 We

Python利用PySpark和Kafka实现流处理引擎构建指南

《Python利用PySpark和Kafka实现流处理引擎构建指南》本文将深入解剖基于Python的实时处理黄金组合:Kafka(分布式消息队列)与PySpark(分布式计算引擎)的化学反应,并构建一... 目录引言:数据洪流时代的生存法则第一章 Kafka:数据世界的中央神经系统消息引擎核心设计哲学高吞吐

Springboot项目构建时各种依赖详细介绍与依赖关系说明详解

《Springboot项目构建时各种依赖详细介绍与依赖关系说明详解》SpringBoot通过spring-boot-dependencies统一依赖版本管理,spring-boot-starter-w... 目录一、spring-boot-dependencies1.简介2. 内容概览3.核心内容结构4.

从基础到高阶详解Python多态实战应用指南

《从基础到高阶详解Python多态实战应用指南》这篇文章主要从基础到高阶为大家详细介绍Python中多态的相关应用与技巧,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、多态的本质:python的“鸭子类型”哲学二、多态的三大实战场景场景1:数据处理管道——统一处理不同数据格式

Go语言使用net/http构建一个RESTful API的示例代码

《Go语言使用net/http构建一个RESTfulAPI的示例代码》Go的标准库net/http提供了构建Web服务所需的强大功能,虽然众多第三方框架(如Gin、Echo)已经封装了很多功能,但... 目录引言一、什么是 RESTful API?二、实战目标:用户信息管理 API三、代码实现1. 用户数据

MySQL数据类型与表操作全指南( 从基础到高级实践)

《MySQL数据类型与表操作全指南(从基础到高级实践)》本文详解MySQL数据类型分类(数值、日期/时间、字符串)及表操作(创建、修改、维护),涵盖优化技巧如数据类型选择、备份、分区,强调规范设计与... 目录mysql数据类型详解数值类型日期时间类型字符串类型表操作全解析创建表修改表结构添加列修改列删除列