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

前言

本篇来谈一谈图的邻接表实现的两种方式,首先我们明确一点“学会图的邻接表实现的关键点在于“:你所建立的图的邻接表的对象是什么!

首先我们看一下《算法导论》中关于图的邻接表的定义:

图G=(V,E)的邻接表表示有一个包含 |V| 个列表的数组Adj所组成,其中每个列表对应于V中的一个顶点,对于每一个u∈V,邻接表Adj[u]包含所有满足条件(u,v)∈E的顶点v,亦即,Adj[u]包含图G中所有和顶点u相邻的顶点。(或者他也可能指向这些顶点的指针),每个邻接表中的顶点一般以任意的顺序存储。

图的邻接表表示如下图所示:

定义总是比较晦涩难懂的,下面我们从如何实现图的邻接表表示来谈一谈!

1、邻接表构建图是必须需要一个Graph对象,也就是图对象!该对象包含属性有:顶点数、边数以及图的顶点集合;

2、正如上面所说,邻接链表的对象首先我们需要确定邻接表的对象,可以用顶点作为邻接链表的对象,自然也可以用边作为邻接链表的对象!下面将分别对这两种方式进行讲解!

一、邻接链表使用顶点作为对象构建图

1、Graph对象类

/**
* 自定义图类
* @author King
*/
public class Graph1 {
Vertex1[] vertexArray=new Vertex1[100];
int verNum=0;
int edgeNum=0;
}

2、Vertex对象类

/**
* 图的顶点类
* @author King
*/
public class Vertex1 {
String verName;
Vertex1 nextNode;
}

3、图的实现类

import java.util.Scanner;
public class CreateGraph3 {
/**
* 根据用户输入的string类型的顶点返回该顶点
* @param graph 图
* @param str 输入数据
* @return返回一个顶点
*/
public Vertex1 getVertex(Graph1 graph,String str){
for(int i=0;i<graph.verNum;i++){
if(graph.vertexArray[i].verName.equals(str)){
return graph.vertexArray[i];
}
}
return null;
}
/**
* 根据用户输入的数据初始化一个图,以邻接表的形式构建!
* @param graph 生成的图
*/
public void initialGraph(Graph1 graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("请输入顶点数和边数:");
graph.verNum=scan.nextInt();
graph.edgeNum=scan.nextInt();
System.out.println("请依次输入定点名称:");
for(int i=0;i<graph.verNum;i++){
Vertex1 vertex=new Vertex1();
String name=scan.next();
vertex.verName=name;
vertex.nextNode=null;
graph.vertexArray[i]=vertex;
}
System.out.println("请依次输入图的便边:");
for(int i=0;i<graph.edgeNum;i++){
String preV=scan.next();
String folV=scan.next();
Vertex1 v1=getVertex(graph,preV);
if(v1==null)
System.out.println("输入边存在图中没有的顶点!");
//下面代码是图构建的核心:链表操作
Vertex1 v2=new Vertex1();
v2.verName=folV;
v2.nextNode=v1.nextNode;
v1.nextNode=v2;
//紧接着下面注释的代码加上便是构建无向图的,不加则是构建有向图的!
// Vertex1 reV2=getVertex(graph,folV);
// if(reV2==null)
// System.out.println("输入边存在图中没有的顶点!");
// Vertex1 reV1=new Vertex1();
// reV1.verName=preV;
// reV1.nextNode=reV2.nextNode;
// reV2.nextNode=reV1;
}
}
/**
* 输入图的邻接表
* @param graph 待输出的图
*/
public void outputGraph(Graph1 graph){
System.out.println("输出图的邻接链表为:");
for(int i=0;i<graph.verNum;i++){
Vertex1 vertex=graph.vertexArray[i];
System.out.print(vertex.verName);

Vertex1 current=vertex.nextNode;
while(current!=null){
System.out.print("-->"+current.verName);
current=current.nextNode;
}
System.out.println();
}
}
public static void main(String[] args) {
Graph1 graph=new Graph1();
CreateGraph3 createGraph=new CreateGraph3();
createGraph.initialGraph(graph);
createGraph.outputGraph(graph);
}
}

二、邻接链表使用边作为对象构建图

1、Graph对象类

import java.util.ArrayList;
public class Graph {
ArrayList<Vertex> vertexList=new ArrayList<Vertex>();
int vertexNum=0;
int edgeNum=0;
public Graph(){}
}

2、Edge对象类

/**
* 图的边对象类
* @author King
*/
public class Edge {
int edgeName;
Edge next;
public Edge(){
}
}

3、Vertex对象类<这里顶点对象只是辅助边构建图,不是作为邻接链表的对象>

/**
* 图的点对象类
* @author King
*/
public class Vertex {
String vertexName;
Edge firstEdge=new Edge();
public Vertex(){
}
}

4、图的实现类

import java.util.Scanner;
/**
* 通过构建边和点的对象来创建图
* @author King
*/
public class CreateGraph {
/**
* 根据顶点信息String,返回边的对象
* @param graph 图
* @param str 顶点名称
* @return 返回的是边对象的标签
*/
public int vtoe(Graph graph,String str){
for(int i=0;i<graph.vertexNum;i++){
if(graph.vertexList.get(i).vertexName.equals(str)){
return i;
}
}
return -1;
}
/**
* 该函数用于图的初始化的实现
* @param graph 图
*/
public void initialGraph(Graph graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("请输入顶点数和边数:");
graph.vertexNum=scan.nextInt();
graph.edgeNum=scan.nextInt();
System.out.println("请依次输入定点名称:");
for(int i=0;i<graph.vertexNum;i++){
Vertex vertex=new Vertex();
String name=scan.next();
vertex.vertexName=name;
vertex.firstEdge=null;
graph.vertexList.add(vertex);
}
System.out.println("请依次输入每个边:");
for(int i=0;i<graph.edgeNum;i++){
String preV=scan.next();
String folV=scan.next();
int v1=vtoe(graph,preV);
int v2=vtoe(graph,folV);
if(v1==-1 || v2==-1)
System.out.println("输入顶点数据错误!");
//下面代码是图构建的核心:链表操作
Edge edge1=new Edge();
edge1.edgeName=v2;
edge1.next=graph.vertexList.get(v1).firstEdge;
graph.vertexList.get(v1).firstEdge=edge1;
// 下面代码加上便是构建无向图,不加便是构建有向图
// Edge edge2=new Edge();
// edge2.edgeName=v1;
// edge2.next=graph.vertexList.get(v2).firstEdge;
// graph.vertexList.get(v2).firstEdge=edge2;
}
}
/**
* 输出图的邻接链表表示
* @param graph 图
*/
public void outputGraph(Graph graph){
Edge edge=new Edge();
for(int i=0;i<graph.vertexNum;i++){
System.out.print(graph.vertexList.get(i).vertexName);
edge=graph.vertexList.get(i).firstEdge;
while(edge!=null){
System.out.print("-->"+graph.vertexList.get(edge.edgeName).vertexName);
edge=edge.next;
}
System.out.println();
}
}
public static void main(String[] args) {
CreateGraph createGraph=new CreateGraph();
Graph graph=new Graph();
createGraph.initialGraph(graph);
createGraph.outputGraph(graph);
}
}

5、以上面给出的图片中图为例运行结果展示:

三、使用邻接表构建图的实例

问题:随机生成一个图(可以是有向图或是无向图),图的顶点大概100个左右,若是有向图则边大概2000条左右,若是无向图则边大概1000条左右!并计算出边的入度和出度

代码:

1、Graph类

public class GraphRandom {
VertexRandom[] vertexArray=new VertexRandom[200];
int verNum=0;
int edgeNum=0;
}

2、Vertexl类

public class VertexRandom {
int verName;
int inRadius,outRadius;
VertexRandom nextNode;
}

3、随机图实现类

import java.util.Scanner;
/**
* 随机生成一个图,计算每个顶点的入度和出度
* @author King
*
*/
public class CreateGraph2 {
/**
* 由顶点名称返回顶点集合中的该顶点
* @param graph 图
* @param name 顶点名称
* @return返回顶点对象
*/
public VertexRandom getVertex(GraphRandom graph,int name){
for(int i=0;i<graph.verNum;i++){
if(graph.vertexArray[i].verName==name){
return graph.vertexArray[i];
}
}
return null;
}
/**
* 该顶点通过顶点和边构建图
* @param graph 图
*/
public void randomSpanning(GraphRandom graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("请输入随机图的顶点个数:");
graph.verNum=scan.nextInt();
for(int i=1;i<=graph.verNum;i++){
VertexRandom vertex=new VertexRandom();
vertex.verName=i;
vertex.nextNode=null;
graph.vertexArray[i-1]=vertex;
}
int number=(int)(Math.random()*200+1000);
System.out.println("随机生成的边的数量为:"+number);
graph.edgeNum=number;
for(int i=0;i<graph.edgeNum;i++){
int preV=(int)(Math.random()*100+1);
int folV=(int)(Math.random()*100+1);
while(folV==preV){
folV=(int)(Math.random()*100+1);
}
VertexRandom vertex1=getVertex(graph,preV);
if(vertex1==null)
System.out.println("随机图中没有该顶点!");
VertexRandom vertex2=new VertexRandom();
vertex2.verName=folV;
vertex2.nextNode=vertex1.nextNode;
vertex1.nextNode=vertex2;
// 下面用于计算顶点的出度和入度的
vertex1.outRadius++;
VertexRandom v2=getVertex(graph,folV);
if(v2==null)
System.out.println("随机图中没有该顶点!");
v2.inRadius++;
// 加上下面代码用于产生无向图
// VertexRandom reVertex2=getVertex(graph,folV);
// if(reVertex2==null)
// System.out.println("随机图中没有该顶点!");
// VertexRandom reVertex1=new VertexRandom();
// reVertex1.verName=preV;
// reVertex1.nextNode=reVertex2.nextNode;
// reVertex2.nextNode=reVertex1;
}
}
/**
* 输出图的邻接链表
* @param graph 图
*/
public void outputGraph(GraphRandom graph){
System.out.println("输出图的邻接链表为:");
for(int i=0;i<graph.verNum;i++){
VertexRandom vertex=graph.vertexArray[i];
System.out.print(vertex.verName);

VertexRandom current=vertex.nextNode;
while(current!=null){
System.out.print("-->"+current.verName);
current=current.nextNode;
}
System.out.println();
}
}
/**
* 输出图的入度和出度
* @param graph 图
*/
public void IORadius(GraphRandom graph){
for(int i=0;i<graph.verNum;i++){
System.out.print("顶点"+(i+1)+"的出度为:"+graph.vertexArray[i].outRadius);
System.out.println(",入度为:"+graph.vertexArray[i].inRadius);
}
}
public static void main(String[] args) {
GraphRandom graph=new GraphRandom();
CreateGraph2 createGraph2=new CreateGraph2();
createGraph2.randomSpanning(graph);
createGraph2.outputGraph(graph);
createGraph2.IORadius(graph);
}
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • java中创建两表之间的触发器详解

    创建一个触发器实现借书自增数量/还书自减 在 books 被借阅属性 islend 更新时在 lender 表中同时更新借书数量 amount,其中islend 属性更新后保存的是借阅人 lender 的 id,lender 中 id 是主键,books 表中 islend 是外键,连接这两张表. 两个数据库表结构在下方给出,目前写的触发器如下: CREATE TRIGGER `lendBook` AFTER UPDATE ON `books` FOR EACH ROW BEGIN UPDATE

  • 邻接表无向图的Java语言实现完整源码

    邻接表无向图的介绍 邻接表无向图是指通过邻接表表示的无向图. 上面的图G1包含了"A,B,C,D,E,F,G"共7个顶点,而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7条边. 上图右边的矩阵是G1在内存中的邻接表示意图.每一个顶点都包含一条链表,该链表记录了"该顶点的邻接点的序号".例如,第2个顶点(顶点C)包含的链表所包含的节点的数据分别是"0,1,3":而这"

  • 深入浅解正则表达式在Java中的使用

    介绍 •正则表达式一般用于字符串匹配, 字符串查找和字符串替换. 别小看它的作用, 在工作学习中灵活运用正则表达式处理字符串能够大幅度提高效率, 编程的快乐来得就是这么简单. •一下子给出一堆匹配的规则可能会让人恐惧, 下面将由浅入深讲解正则表达式的使用. 从简单例子认识正则表达式匹配 •先上代码 public class Demo1 { public static void main(String[] args) { //字符串abc匹配正则表达式"...", 其中".&q

  • Java通过CMD方式读取注册表任意键值对代码实践

    需要读取如图所示注册表[HKEY_LOCAL_MACHINE\SOFTWARE\EasyDrv7]节点下的[DateTime]的值 直接上代码: package com.beibei.common.util.cmd; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map;

  • 详解Java中的scala正则表达式

    Scala 通过 scala.util.matching 包中的 Regex 类来支持正则表达式. eg:使用正则表达式查找单词 Scala 实例中使用 String 类的 r() 方法构造了一个Regex对象.(也可直接new一个Regex对象实例)然后使用 findFirstIn 方法找到首个匹配项.如果需要查看所有的匹配项可以使用 findAllIn 方法. 可以使用 mkString( ) 方法来连接正则表达式匹配结果的字符串,并可以使用管道(|)来设置不同的模式: 如果需要将匹配的文本

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

    前言 本篇来谈一谈图的邻接表实现的两种方式,首先我们明确一点"学会图的邻接表实现的关键点在于":你所建立的图的邻接表的对象是什么! 首先我们看一下<算法导论>中关于图的邻接表的定义: 图G=(V,E)的邻接表表示有一个包含 |V| 个列表的数组Adj所组成,其中每个列表对应于V中的一个顶点,对于每一个u∈V,邻接表Adj[u]包含所有满足条件(u,v)∈E的顶点v,亦即,Adj[u]包含图G中所有和顶点u相邻的顶点.(或者他也可能指向这些顶点的指针),每个邻接表中的顶点一般

  • 图的邻接表存储表示示例讲解

    复制代码 代码如下: //---------图的邻接表存储表示------- #include<stdio.h>#include<stdlib.h> #define MAX_VERTEXT_NUM 20 typedef int InfoType;typedef char VertextType; typedef struct ArcNode{    int adjvex;    struct ArcNode *nextArc;    InfoType *info;}ArcNode;

  • C++实现图的邻接表存储和广度优先遍历实例分析

    本文实例讲述了C++实现图的邻接表存储和广度优先遍历方法.分享给大家供大家参考.具体如下: 示例:建立如图所示的无向图 由上图知,该图有5个顶点,分别为a,b,c,d,e,有6条边. 示例输入(按照这个格式输入): 5 6 abcde 0 1 0 2 0 3 2 3 2 4 1 4 输入结束(此行不必输入) 注:0 1表示该图的第0个顶点和第1个定点有边相连,如上图中的a->b所示       0 2表示该图的第0个顶点和第2个定点有边相连,如上图中的a->c所示       2 3表示该图的

  • 详解Java递归实现树形结构的两种方式

    目录 0.引言 1.数据准备 2.类型转化 3.递归实现方法 3.1.Java7及以下纯Java递归实现 3.2.Java8及以上借助lamda表达式实现 0.引言 在开发的过程中,很多业务场景需要一个树形结构的结果集进行前端展示,也可以理解为是一个无限父子结构,常见的有报表指标结构.菜单结构等.Java中递归实现树形结构的两种常见方式如下: Java7及以下纯Java递归实现 Java8及以上借助lamda表达式实现 1.数据准备 Java实体类NodePO对应数据库表 package com

  • Angualrjs 表单验证的两种方式(失去焦点验证和点击提交验证)

    AngularJS提供了表单验证,但是验证的过程交互体验很不好,比如重设密码,重复密码的时候一键入就会提示密码不正确,现整理了两种方法,仅供借鉴. 一,点击提交验证 <form action="" class="form-horizontal col-md-9" name="reset_pwd" ng-submit="resetPwd()"> <div class="form-group"

  • Java 两种延时thread和timer详解及实例代码

    Java 两种延时thread和timer详解及实例代码 在Java中有时候需要使程序暂停一点时间,称为延时.普通延时用Thread.sleep(int)方法,这很简单.它将当前线程挂起指定的毫秒数.如 try { Thread.currentThread().sleep(1000);//毫秒 } catch(Exception e){} 在这里需要解释一下线程沉睡的时间.sleep()方法并不能够让程序"严格"的沉睡指定的时间.例如当使用5000作为sleep()方法的参数时,线 程

  • jquery ajax提交表单数据的两种方式

    之前实现AJAX使用Javascript脚本一个一个敲出来的,很繁琐.学习Jquery之后就感觉实现AJAX并不是那么的困难了,当然除了Jquery框架外还有其它的优秀框架这里我就着重说下比较流行的Jquery.Jquery AJAX提交表单有两种方式,一是url参数提交数据,二是form提交(和平常一样在后台可以获取到Form表单的值).在所要提交的表单中,如果元素很多的话建议用第二种方式进行提交,当然你要是想练练"打字水平"的话用第一种方式提交也未尝不可,相信开发者都不想费白劲吧!

  • Java web开发中加载图片路径的两种方式

    (1)   src="/image/1_it.jpg" (2)   src="http://localhost:8080/image/1_it.jpg" 其中localhost可以换位你的电脑IP,端口号也要相应改变. 以上均在基于编译器idea以及tomcat服务器开发的web中测试可行!都是要先定位到项目的位置! 以上所述是小编给大家介绍的Java web开发加载图片路径的两种方式,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!

  • java自带命令行工具jmap、jhat与jinfo的使用实例代码详解

    java自带命令行工具(jmap,jhat,jinfo) (1)JMAP 1.作用 打印进程,core文件,和远程进程的共享对象存储map或堆存储器的详细信息. 2.使用 jmap[options]pid jmap[options]executablecore jmap[options][pid]server-id@]remote-hostname-or-IP 如果指定的进程是在64位Java虚拟机(JVM)上运行,那么你可能需要指定-J-d64选项,例如:jmap -J-d64 -heap p

  • js清空表单数据的两种方式(遍历+reset)

    方法1:遍历页面元素 /* 清空FORM表单内容 id:表单ID*/ function ClearForm(id) { var objId = document.getElementById(id); if (objId == undefined) { return; } for (var i = 0; i < objId.elements.length; i++) { if (objId.elements[i].type == "text") { objId.elements[

随机推荐