表示加权图-java教程-PHP中文网

首页

Java

java教程

表示加权图

王林

Sep 06, 2024 am 06:07 AM

加权边可以存储在邻接列表中。

加权图有两种类型：顶点加权和边加权。在顶点加权图中，每个顶点都被分配一个权重。在边加权图中，每条边都被分配一个权重。在这两种类型中，边加权图有更多的应用。本章讨论边加权图。

加权图可以用与未加权图相同的方式表示，只不过您必须表示边上的权重。与未加权图一样，加权图中的顶点可以存储在数组中。本节介绍加权图中边的三种表示形式。

表示加权边：边数组

加权边可以使用二维数组来表示。例如，您可以使用下图(b)中的数组来存储下图(a)图中的所有边。

Representing Weighted Graphs

权重可以是任何类型：Integer、Double、BigDecimal等。您可以使用 Object 类型的二维数组来表示加权边，如下所示：

对象[][]边缘= {
{new Integer(0), new Integer(1), new SomeTypeForWeight(2)},
{new Integer(0), new Integer(3), new SomeTypeForWeight(8)},
...
};

加权邻接矩阵

假设图有 n 个顶点。您可以使用二维 n * n 矩阵，例如 weights 来表示边上的权重。 weights[i][j] 表示边上的权重 (i, j)。如果顶点 i 和 j 未连接，则 weights[i][j] 为 null。例如，上图(a)中的权重可以使用邻接矩阵表示如下：

Representing Weighted Graphs

邻接表

表示边缘的另一种方法是将边缘定义为对象。 AbstractGraph.Edge 类被定义为表示 AbstractGraph.java 中的未加权边。对于加权边，我们定义 WeightedEdge 类，如下面的代码所示。

Representing Weighted Graphs

AbstractGraph.Edge 是 AbstractGraph 类中定义的内部类。它表示从顶点 u 到 v 的边。 WeightedEdge 使用新属性 weight 扩展了 AbstractGraph.Edge。

要创建 WeightedEdge 对象，请使用 new WeightedEdge(i, j, w)，其中 w 是边上的权重 (i ，j）。通常您需要比较边的权重。因此，WeightedEdge 类实现了 Comparable 接口。

对于未加权图，我们使用邻接表来表示边。对于带权图，我们仍然使用邻接表，下图a中的图中顶点的邻接表可以表示为：

java.util.List[] list = new java.util.List[5];

Representing Weighted Graphs

list[i] 存储与顶点 i.

相邻的所有边

为了灵活性，我们将使用数组列表而不是固定大小的数组来表示 list，如下所示：

列表> list = new java.util.ArrayList();

以上是表示加权图的详细内容。更多信息请关注PHP中文网其他相关文章！

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

热工具

热门话题

PHP教程

1679

276

NYT连接提示和答案

331

836

显示更多

Related knowledge

如何在Java中创建文件 Sep 21, 2025 am 03:54 AM

UseFile.createNewFile()tocreateafileonlyifitdoesn’texist,avoidingoverwriting;2.PreferFiles.createFile()fromNIO.2formodern,safefilecreationthatfailsifthefileexists;3.UseFileWriterorPrintWriterwhencreatingandimmediatelywritingcontent,withFileWriterover

如何在Java中的类Path中添加JAR文件？ Sep 21, 2025 am 05:09 AM

使用-cp参数可将JAR加入类路径，使JVM能加载其内类与资源，如java-cplibrary.jarcom.example.Main，支持多JAR用分号或冒号分隔，也可通过CLASSPATH环境变量或MANIFEST.MF配置。

如何在Java中实现接口？ Sep 18, 2025 am 05:31 AM

使用implements关键字实现接口，类需提供接口中所有方法的具体实现，支持多接口时用逗号分隔，确保方法为public，Java8后默认和静态方法无需重写。

使用Java服务提供商界面（SPI）构建可扩展应用程序 Sep 21, 2025 am 03:50 AM

JavaSPI是JDK内置的服务发现机制，通过ServiceLoader实现面向接口的动态扩展。1.定义服务接口并在META-INF/services/下创建以接口全名为名的文件，写入实现类全限定名；2.使用ServiceLoader.load()加载实现类，JVM会自动读取配置并实例化；3.设计时应明确接口契约、支持优先级与条件加载、提供默认实现；4.应用场景包括多支付渠道接入和插件化校验器；5.注意性能、类路径、异常隔离、线程安全和版本兼容性；6.在Java9 可结合模块系统使用provid

深入理解HTTP持久连接：在同一Socket上发送多个请求的策略与实践 Sep 21, 2025 pm 01:51 PM

本文深入探讨了在同一TCP Socket上发送多个HTTP请求的机制，即HTTP持久连接（Keep-Alive）。文章澄清了HTTP/1.x与HTTP/2协议的区别，强调了服务器端对持久连接支持的重要性，以及如何正确处理Connection: close响应头。通过分析常见错误和提供最佳实践，旨在帮助开发者构建高效且健壮的HTTP客户端。

如何读取Java中的属性文件？ Sep 16, 2025 am 05:01 AM

使用Properties类可轻松读取Java配置文件。1.将config.properties放入资源目录，通过getClassLoader().getResourceAsStream()加载并调用load()方法读取数据库配置。2.若文件在外部路径，使用FileInputStream加载。3.使用getProperty(key,defaultValue)处理缺失键并提供默认值，确保异常处理和输入验证。

了解Java仿制药和通配符 Sep 20, 2025 am 01:58 AM

Javagenericsprovidecompile-timetypesafetyandeliminatecastingbyallowingtypeparametersonclasses,interfaces,andmethods;wildcards(?,?extendsType,?superType)handleunknowntypeswithflexibility.1.UseunboundedwildcardwhentypeisirrelevantandonlyreadingasObject