`

图 邻接表 Java 实现

阅读更多

 

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

 

也许实现的时候,可以不区别头结点和表结点。

但是不区分的话,遍历麻烦些。

 

可以有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语言实现完整 邻接表无向图是一种常见的图数据结构,它通过邻接表表示无向图。在Java语言中,实现邻接表无向图需要定义相应的数据结构和算法。下面是关于邻接表无向图的Java语言实现的知识点: ...

    JAVA下基于邻接表的图的通用算法实现

    (1) 基于邻接表的图的构建功能 (2) 标准Dijkstra算法 (3) 有向图的强连通算法 Environment: Eclipse 3.4 + JDK 1.6 注:目前只实现了以上三个功能,但由于各功能都基于模块化分解的思想实现,所以加入新功能会比较...

    图的邻接表实现

    图的邻接表实现,用邻接矩阵实现了图,基本操作,主要算法

    数据结构 图 邻接表

    在编程实现时,可以使用各种编程语言,如C++、Java、Python等,利用它们提供的数据结构(如链表、数组)来构建邻接表。此外,理解邻接表的内部工作原理对于优化算法和提高程序性能至关重要。 总的来说,邻接表是一...

    数据结构 图的邻接表存储

    ### 数据结构:图的邻接表存储 #### 一、引言 在计算机科学中,图是一种非线性数据结构,由顶点集合V和边集合E组成,表示为G=(V,E)。图可以用来表示各种各样的关系,如社交网络中的朋友关系、互联网中的网页链接等...

    基于邻接边表实现图的顶点结构算法(java源码)

    * 基于邻接边表实现图的顶点结构 */ package dsa; public class Vertex_List implements Vertex { //变量 protected Object info;//当前顶点中存放的数据元素 protected Position vPosInV;//当前顶点在所属的...

    Java实现邻接表.html

    第一次制作的网页,关于基于Java实现图论算法的代码。内含一些html的基础操作语法,比如超链接等等。

    java使用邻接表对图进行深度和广度优先遍历

    在这个Java程序中,我们将探讨如何使用邻接表来实现图的深度优先遍历(DFS)和广度优先遍历(BFS)。邻接表是图数据结构的一种有效实现方式,尤其对于稀疏图(边的数量远小于节点数量的平方)来说,它比邻接矩阵更加...

    邻接矩阵和邻接表存储的图的遍历

    本主题将深入探讨两种常见的图存储方式——邻接矩阵和邻接表,以及如何在这两种存储方式下实现深度优先遍历(DFS)和广度优先遍历(BFS)。 首先,邻接矩阵是一种直观的图表示方法,它使用二维数组来存储图中每个...

    图的邻接矩阵实现及深度优先搜索(JAVA)

    这个应用程序演示了如何使用Java实现图的邻接矩阵和深度优先搜索的基本概念。 总结一下,这个话题涵盖了以下关键知识点: 1. 图的邻接矩阵表示法:使用二维数组存储图中节点的关系。 2. Java中实现邻接矩阵:创建一...

    邻接表实现图的广搜和深搜(java模板)

    本篇将详细介绍如何使用Java实现基于邻接表的图的广度优先搜索(BFS)和深度优先搜索(DFS),并提供相关代码模板。 **一、邻接表的概念** 邻接表是一种空间效率高的图数据结构,它为每个顶点维护一个列表,列表中...

    Java基于邻接边表实现图的边结构(算法源码)

    * 基于邻接边表实现图的边结构 */ package dsa; public class Edge_List implements Edge { //变量 protected Object info;//当前边中存放的数据元素 protected Position ePosInE;//当前边在所属的图的边表中...

    Java基于邻接边表实现图结构(算法源码)

    * 基于邻接边表实现图结构 */ package dsa; public class Graph_List implements Graph { //变量 protected List E;//容器:存放图中所有边 protected List V;//容器:存放图中所有顶点 //构造方法 public ...

    基于邻接边表实现图结构算法(java算法源码)

    * 基于邻接边表实现图结构 */ package dsa; public class Graph_List implements Graph { //变量 protected List E;//容器:存放图中所有边 protected List V;//容器:存放图中所有顶点 //构造方法 public ...

    java实现图的邻接表存储结构的两种方式及实例应用详解

    Java 实现图的邻接表存储结构的两种方式及实例应用详解 本文主要介绍了 Java 实现图的邻接表存储结构的两种方式及实例应用详解。图的邻接表是一种常用的图存储结构,它将图的顶点和边信息存储在一个数组中,使得图...

    有向图存储和遍历-java实现.zip

    综上所述,这个Java实现可能涉及了有向图的基本概念、存储结构、遍历算法以及实际的代码实现,是学习和理解有向图的好素材。开发者可以通过阅读和运行代码,进一步理解这些理论知识在实际编程中的应用。

    编写算法,由依次输入的顶点数目、弧的数目、各顶点信息和各条弧信息建立有向图的邻接表。

    邻接表是用于表示有向图的一种高效的数据结构,尤其适用于存储稀疏图(边的数量远小于顶点数量的平方)。在这个任务中,我们需要编写一个算法,根据输入的顶点数目、弧的数目以及各自的顶点和弧信息来构建有向图的...

    基于java数据结构实验基于邻接矩阵和邻接表的深度广度优先遍历图.pdf

    实验的结果表明,基于邻接表和邻接矩阵的深度广度优先遍历图实验可以成功实现图的建立和遍历。实验的总结部分也对实验的结果进行了总结和分析,指出实验的经验和收获,以及实验中遇到的问题和分析。 本实验报告的...

    JAVA实现的多段图动态规划算法

    由JAVA实现的多段图的动态规划算法,采用邻接表数据结构存储

Global site tag (gtag.js) - Google Analytics