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

embedded/2024/9/24 2:21:41/

构建无向图

前提

JAVA实验环境

理论

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

实验数据

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

实验数据下载地址: https://algs4.cs.princeton.edu/code/algs4-data.zip
实验中用到的通用库:https://algs4.cs.princeton.edu/code/algs4.jar
实验数据使用方法:https://algs4.cs.princeton.edu/code/

在这里插入图片描述

完整代码

文件名称 myGraph.java

java">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)数据结构的实现。下面是对这段代码的逐行解读,可以帮助你向其他人详细介绍这个程序:

类定义

java">public class myGraph

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

成员变量

java">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 是系统相关的换行符,用于输出。

构造方法

java">public myGraph(int V

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

java">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 对象。

从输入流构造图

java">public myGraph(In in)

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

java">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); // 添加边
}

方法定义

java">public int V() { return V; }
public int E() { return E; }

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

java">public void addEdge(int v, int w)

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

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

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

toString 方法

java">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 方法

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

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

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

实验

编译

java">javac myGraph.java

导入实验数据

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.ppmy.cn/embedded/19305.html

相关文章

观察者模式

观察者设计模式 模式定义 观察者模式,定义对象间的一种一对多的依赖关系,当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并被自动更新。 顾名思义,此模式需要有观察者(Observer)和被观察者(Observable)两类角色,当Observable状态变化时会通知Observer,…

有什么因素会影响IP稳定性?

IP稳定性指的是IP地址在一段时间内保持不变的能力&#xff0c;对于网络连接的安全性和可靠性至关重要。以下是一些可能影响IP稳定性的主要因素&#xff1a; 网络服务提供商&#xff08;ISP&#xff09;的政策&#xff1a;不同的ISP对于IP地址的管理和使用有不同的政策。一些IS…

R可视化:分组频率分布直方图和密度图

介绍 ggplot2绘制分组频率分布直方图和密度图 加载R包 knitr::opts_chunk$set(message FALSE, warning FALSE) library(tidyverse) library(patchwork) library(ggpubr) library(rstatix)# rm(list ls()) options(stringsAsFactors F) options(future.globals.maxSize …

汇编期末复习知识点

参考文献1 第一章 概述 组成 计算机系统由硬件子系统和软件子系统组成。硬件子系统&#xff1a;组成计算机系统的所有电子的&#xff0c;机械的&#xff0c;光学的和磁性的元部件。 计算机中常用进制数表示 十进制(Decimal):数据尾部加一后缀D&#xff0c;如2355D二进制&a…

phpstudy-Ubuntu面板(小皮面板)

Ubuntu安装脚本 :(无docker版本) wget -O install.sh https://notdocker.xp.cn/install.sh && sudo bash install.sh Ubuntu安装脚本 :(有docker版本) wget -O install.sh https://download.xp.cn/install.sh && sudo bash install.sh 参考&#xff1a;linux 完…

【每日算法】理论:深度学习基础 刷题:KMP算法思想

上期文章 【每日算法】理论&#xff1a;常见网络架构 刷题&#xff1a;力扣字符串回顾 文章目录 上期文章一、上期问题二、本期理论问题1、注意力机制2、BatchNorm 和 LayerNorm 的区别3、Bert 的参数量是怎么决定的。4、为什么现在的大语言模型都采用Decoder only架构&#x…

Python小游戏 贪吃蛇(完整版) Pygame sys time

需要安装pip pygame 不会私 import randomimport pygame, sys,time # pygame.init()# 全局变量 SCREEN_WIDTH 640 # 屏幕宽度 SCREEN_HEIGHT 480 # 屏幕高度BLOCK_SIZE 20 # 方格的宽、高长度COLOR_GRAY (150, 150, 150) # 灰色 COLOR_GREEN (0, 150, 0) # 绿色 CO…

Wireshark安装教程

一、下载 地址&#xff1a;https://www.wireshark.org/download.html打开网址后&#xff0c;点击相应的版本下载&#xff1a; 二、安装 下载完成后双击文件开始安装 点击Next 点击Noted 点击Next 点击Next 点击Next 可以点击Browse更改安装路径&#xff0c;默认…