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

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

相关文章

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

基于Python构建一个高效词汇表

《基于Python构建一个高效词汇表》在自然语言处理(NLP)领域,构建高效的词汇表是文本预处理的关键步骤,本文将解析一个使用Python实现的n-gram词频统计工具,感兴趣的可以了解下... 目录一、项目背景与目标1.1 技术需求1.2 核心技术栈二、核心代码解析2.1 数据处理函数2.2 数据处理流程

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》:本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas

Python FastMCP构建MCP服务端与客户端的详细步骤

《PythonFastMCP构建MCP服务端与客户端的详细步骤》MCP(Multi-ClientProtocol)是一种用于构建可扩展服务的通信协议框架,本文将使用FastMCP搭建一个支持St... 目录简介环境准备服务端实现(server.py)客户端实现(client.py)运行效果扩展方向常见问题结

详解如何使用Python构建从数据到文档的自动化工作流

《详解如何使用Python构建从数据到文档的自动化工作流》这篇文章将通过真实工作场景拆解,为大家展示如何用Python构建自动化工作流,让工具代替人力完成这些数字苦力活,感兴趣的小伙伴可以跟随小编一起... 目录一、Excel处理:从数据搬运工到智能分析师二、PDF处理:文档工厂的智能生产线三、邮件自动化:

详解如何使用Python从零开始构建文本统计模型

《详解如何使用Python从零开始构建文本统计模型》在自然语言处理领域,词汇表构建是文本预处理的关键环节,本文通过Python代码实践,演示如何从原始文本中提取多尺度特征,并通过动态调整机制构建更精确... 目录一、项目背景与核心思想二、核心代码解析1. 数据加载与预处理2. 多尺度字符统计3. 统计结果可

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对(Key-Value)存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re