package abc.Dijkstra.pack3; import java.util.ArrayList; import java.util.List; public class AlGraph { List<HeadNode> headNodes = new ArrayList<HeadNode>(); void addVertex(HeadNode node) { headNodes.add(node); } void addArc(HeadNode head, HeadNode tail) { if(head.firstArcNode == null) head.firstArcNode = new ArcNode(tail); else { ArcNode arcNode = head.firstArcNode; while (arcNode.nextArcNode != null) { arcNode = arcNode.nextArcNode; } arcNode.nextArcNode = new ArcNode(tail); } } static AlGraph createAlGraph() { AlGraph alGraph = new AlGraph(); HeadNode A = new HeadNode("A"); HeadNode B = new HeadNode("B"); HeadNode C = new HeadNode("C"); HeadNode D = new HeadNode("D"); alGraph.addVertex(A); alGraph.addVertex(B); alGraph.addVertex(C); alGraph.addVertex(D); alGraph.addArc(A, B); alGraph.addArc(A, C); alGraph.addArc(A, D); alGraph.addArc(B, A); alGraph.addArc(B, D); alGraph.addArc(C, A); alGraph.addArc(D, A); alGraph.addArc(D, B); return alGraph; } void print() { for(HeadNode head : headNodes) { System.out.print(head.name); if(head.firstArcNode != null) { ArcNode arcNode = head.firstArcNode; System.out.print(" -> "); System.out.print(arcNode.headNode.name); while (arcNode.nextArcNode != null) { arcNode = arcNode.nextArcNode; System.out.print(" -> "); System.out.print(arcNode.headNode.name); } } System.out.println(); } } public static void main(String[] args) { AlGraph.createAlGraph().print(); } } class ArcNode { public ArcNode(HeadNode tail) { this.headNode = tail; } HeadNode headNode; ArcNode nextArcNode; } class HeadNode { String name; ArcNode firstArcNode; HeadNode(String name) { this.name = name; } }
输出 写道
A -> B -> C -> D
B -> A -> D
C -> A
D -> A -> B
B -> A -> D
C -> A
D -> A -> B
也许实现的时候,可以不区别头结点和表结点。
但是不区分的话,遍历麻烦些。
可以有List代替Link
public class AlGraph3 { List<Node> vertexes = new ArrayList<Node>(); void addVertex(Node vertex) { vertexes.add(vertex); } void addArc(Node head, Node tail) { head.addArc(tail); } static AlGraph3 createAlGraph() { AlGraph3 alGraph = new AlGraph3(); Node A = new Node("A"); Node B = new Node("B"); Node C = new Node("C"); Node D = new Node("D"); alGraph.addVertex(A); alGraph.addVertex(B); alGraph.addVertex(C); alGraph.addVertex(D); alGraph.addArc(A, B); alGraph.addArc(A, C); alGraph.addArc(A, D); alGraph.addArc(B, A); alGraph.addArc(B, D); alGraph.addArc(C, A); alGraph.addArc(D, A); alGraph.addArc(D, B); return alGraph; } void print() { for(Node head : vertexes) { System.out.print(head.name); for(Node arc : head.adjs) { System.out.print(" -> "); System.out.print(arc.name); } System.out.println(); } } public static void main(String[] args) { AlGraph3.createAlGraph().print(); } } class Node { String name; List<Node> adjs = new ArrayList<Node>(); Node(String name) { this.name = name; } void addArc(Node node) { adjs.add(node); } }
相关推荐
本文将深入探讨图的邻接表存储方式以及如何用Java进行遍历。 一、邻接表的概念 邻接表是图的一种常见存储方式,它为每个顶点维护一个列表,列表中包含了与该顶点相连的所有边。相比于邻接矩阵,邻接表在处理稀疏图...
邻接表无向图的Java语言实现完整 邻接表无向图是一种常见的图数据结构,它通过邻接表表示无向图。在Java语言中,实现邻接表无向图需要定义相应的数据结构和算法。下面是关于邻接表无向图的Java语言实现的知识点: ...
(1) 基于邻接表的图的构建功能 (2) 标准Dijkstra算法 (3) 有向图的强连通算法 Environment: Eclipse 3.4 + JDK 1.6 注:目前只实现了以上三个功能,但由于各功能都基于模块化分解的思想实现,所以加入新功能会比较...
图的邻接表实现,用邻接矩阵实现了图,基本操作,主要算法
在编程实现时,可以使用各种编程语言,如C++、Java、Python等,利用它们提供的数据结构(如链表、数组)来构建邻接表。此外,理解邻接表的内部工作原理对于优化算法和提高程序性能至关重要。 总的来说,邻接表是一...
### 数据结构:图的邻接表存储 #### 一、引言 在计算机科学中,图是一种非线性数据结构,由顶点集合V和边集合E组成,表示为G=(V,E)。图可以用来表示各种各样的关系,如社交网络中的朋友关系、互联网中的网页链接等...
* 基于邻接边表实现图的顶点结构 */ package dsa; public class Vertex_List implements Vertex { //变量 protected Object info;//当前顶点中存放的数据元素 protected Position vPosInV;//当前顶点在所属的...
第一次制作的网页,关于基于Java实现图论算法的代码。内含一些html的基础操作语法,比如超链接等等。
在这个Java程序中,我们将探讨如何使用邻接表来实现图的深度优先遍历(DFS)和广度优先遍历(BFS)。邻接表是图数据结构的一种有效实现方式,尤其对于稀疏图(边的数量远小于节点数量的平方)来说,它比邻接矩阵更加...
本主题将深入探讨两种常见的图存储方式——邻接矩阵和邻接表,以及如何在这两种存储方式下实现深度优先遍历(DFS)和广度优先遍历(BFS)。 首先,邻接矩阵是一种直观的图表示方法,它使用二维数组来存储图中每个...
这个应用程序演示了如何使用Java实现图的邻接矩阵和深度优先搜索的基本概念。 总结一下,这个话题涵盖了以下关键知识点: 1. 图的邻接矩阵表示法:使用二维数组存储图中节点的关系。 2. Java中实现邻接矩阵:创建一...
本篇将详细介绍如何使用Java实现基于邻接表的图的广度优先搜索(BFS)和深度优先搜索(DFS),并提供相关代码模板。 **一、邻接表的概念** 邻接表是一种空间效率高的图数据结构,它为每个顶点维护一个列表,列表中...
* 基于邻接边表实现图的边结构 */ package dsa; public class Edge_List implements Edge { //变量 protected Object info;//当前边中存放的数据元素 protected Position ePosInE;//当前边在所属的图的边表中...
* 基于邻接边表实现图结构 */ package dsa; public class Graph_List implements Graph { //变量 protected List E;//容器:存放图中所有边 protected List V;//容器:存放图中所有顶点 //构造方法 public ...
* 基于邻接边表实现图结构 */ package dsa; public class Graph_List implements Graph { //变量 protected List E;//容器:存放图中所有边 protected List V;//容器:存放图中所有顶点 //构造方法 public ...
Java 实现图的邻接表存储结构的两种方式及实例应用详解 本文主要介绍了 Java 实现图的邻接表存储结构的两种方式及实例应用详解。图的邻接表是一种常用的图存储结构,它将图的顶点和边信息存储在一个数组中,使得图...
综上所述,这个Java实现可能涉及了有向图的基本概念、存储结构、遍历算法以及实际的代码实现,是学习和理解有向图的好素材。开发者可以通过阅读和运行代码,进一步理解这些理论知识在实际编程中的应用。
邻接表是用于表示有向图的一种高效的数据结构,尤其适用于存储稀疏图(边的数量远小于顶点数量的平方)。在这个任务中,我们需要编写一个算法,根据输入的顶点数目、弧的数目以及各自的顶点和弧信息来构建有向图的...
实验的结果表明,基于邻接表和邻接矩阵的深度广度优先遍历图实验可以成功实现图的建立和遍历。实验的总结部分也对实验的结果进行了总结和分析,指出实验的经验和收获,以及实验中遇到的问题和分析。 本实验报告的...
由JAVA实现的多段图的动态规划算法,采用邻接表数据结构存储