189 8069 5689

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

前言

成都创新互联坚持“要么做到,要么别承诺”的工作理念,服务领域包括:成都做网站、成都网站制作、成都外贸网站建设、企业官网、英文网站、手机端网站、网站推广等服务,满足客户于互联网时代的雁塔网站设计、移动媒体设计的需求,帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴!

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

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

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

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

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

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

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

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

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

1、Graph对象类

/**
* 自定义图类
* @author King
*/
public class Graph2 {
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 CreateGraph4 {
/**
* 根据用户输入的string类型的顶点返回该顶点
* @param graph 图
* @param str 输入数据
* @return返回一个顶点
*/
public Vertex1 getVertex(Graph2 graph,String str){
for(int i=0;i"+current.verName);
current=current.nextNode;
}
System.out.println();
}
}
public static void main(String[] args) {
Graph2 graph=new Graph2();
CreateGraph4 createGraph=new CreateGraph4();
createGraph.initialGraph(graph);
createGraph.outputGraph(graph);
}
}

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

1、Graph对象类

import java.util.ArrayList;
public class Graph {
ArrayList vertexList=new ArrayList();
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.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、以上面给出的图片中图为例运行结果展示:

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

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

问题:随机生成一个图(可以是有向图或是无向图),图的顶点大概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 CreateGraph3 {
/**
* 由顶点名称返回顶点集合中的该顶点
* @param graph 图
* @param name 顶点名称
* @return返回顶点对象
*/
public VertexRandom getVertex(GraphRandom graph,int name){
for(int i=0;i"+current.verName);
current=current.nextNode;
}
System.out.println();
}
}
/**
* 输出图的入度和出度
* @param graph 图
*/
public void IORadius(GraphRandom graph){
for(int i=0;i

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


文章名称:java实现图的邻接表存储结构的两种方式及实例应用详解
链接URL:http://cdxtjz.com/article/pdgcss.html

其他资讯