java實(shí)現(xiàn)圖的鄰接表存儲(chǔ)結(jié)構(gòu)的兩種方式及實(shí)例應(yīng)用詳解

更新時(shí)間：2019年06月26日 10:06:03 作者：feilong_csdn

這篇文章主要介紹了java實(shí)現(xiàn)圖的鄰接表存儲(chǔ)結(jié)構(gòu)的兩種方式及實(shí)例應(yīng)用詳解,鄰接表構(gòu)建圖是必須需要一個(gè)Graph對(duì)象，也就是圖對(duì)象！該對(duì)象包含屬性有：頂點(diǎn)數(shù)、邊數(shù)以及圖的頂點(diǎn)集合,需要的朋友可以參考下

前言

本篇來談一談圖的鄰接表實(shí)現(xiàn)的兩種方式，首先我們明確一點(diǎn)“學(xué)會(huì)圖的鄰接表實(shí)現(xiàn)的關(guān)鍵點(diǎn)在于“：你所建立的圖的鄰接表的對(duì)象是什么！

首先我們看一下《算法導(dǎo)論》中關(guān)于圖的鄰接表的定義：

圖G=(V,E)的鄰接表表示有一個(gè)包含 |V| 個(gè)列表的數(shù)組Adj所組成，其中每個(gè)列表對(duì)應(yīng)于V中的一個(gè)頂點(diǎn)，對(duì)于每一個(gè)u∈V，鄰接表Adj[u]包含所有滿足條件（u，v）∈E的頂點(diǎn)v，亦即，Adj[u]包含圖G中所有和頂點(diǎn)u相鄰的頂點(diǎn)。（或者他也可能指向這些頂點(diǎn)的指針），每個(gè)鄰接表中的頂點(diǎn)一般以任意的順序存儲(chǔ)。

圖的鄰接表表示如下圖所示：

定義總是比較晦澀難懂的，下面我們從如何實(shí)現(xiàn)圖的鄰接表表示來談一談！

1、鄰接表構(gòu)建圖是必須需要一個(gè)Graph對(duì)象，也就是圖對(duì)象！該對(duì)象包含屬性有：頂點(diǎn)數(shù)、邊數(shù)以及圖的頂點(diǎn)集合；

2、正如上面所說，鄰接鏈表的對(duì)象首先我們需要確定鄰接表的對(duì)象，可以用頂點(diǎn)作為鄰接鏈表的對(duì)象，自然也可以用邊作為鄰接鏈表的對(duì)象！下面將分別對(duì)這兩種方式進(jìn)行講解！

一、鄰接鏈表使用頂點(diǎn)作為對(duì)象構(gòu)建圖

1、Graph對(duì)象類

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

2、Vertex對(duì)象類

/**
* 圖的頂點(diǎn)類
* @author King
*/
public class Vertex1 {
String verName;
Vertex1 nextNode;
}

3、圖的實(shí)現(xiàn)類

import java.util.Scanner;
public class CreateGraph3 {
/**
* 根據(jù)用戶輸入的string類型的頂點(diǎn)返回該頂點(diǎn)
* @param graph 圖
* @param str 輸入數(shù)據(jù)
* @return返回一個(gè)頂點(diǎn)
*/
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;
}
/**
* 根據(jù)用戶輸入的數(shù)據(jù)初始化一個(gè)圖，以鄰接表的形式構(gòu)建!
* @param graph 生成的圖
*/
public void initialGraph(Graph1 graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");
graph.verNum=scan.nextInt();
graph.edgeNum=scan.nextInt();
System.out.println("請(qǐng)依次輸入定點(diǎn)名稱：");
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("請(qǐng)依次輸入圖的便邊：");
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("輸入邊存在圖中沒有的頂點(diǎn)！");
//下面代碼是圖構(gòu)建的核心：鏈表操作
Vertex1 v2=new Vertex1();
v2.verName=folV;
v2.nextNode=v1.nextNode;
v1.nextNode=v2;
//緊接著下面注釋的代碼加上便是構(gòu)建無向圖的，不加則是構(gòu)建有向圖的！
// Vertex1 reV2=getVertex(graph,folV);
// if(reV2==null)
// System.out.println("輸入邊存在圖中沒有的頂點(diǎn)！");
// 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);
}
}

二、鄰接鏈表使用邊作為對(duì)象構(gòu)建圖

1、Graph對(duì)象類

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

2、Edge對(duì)象類

/**
* 圖的邊對(duì)象類
* @author King
*/
public class Edge {
int edgeName;
Edge next;
public Edge(){
}
}

3、Vertex對(duì)象類<這里頂點(diǎn)對(duì)象只是輔助邊構(gòu)建圖，不是作為鄰接鏈表的對(duì)象>

/**
* 圖的點(diǎn)對(duì)象類
* @author King
*/
public class Vertex {
String vertexName;
Edge firstEdge=new Edge();
public Vertex(){
}
}

4、圖的實(shí)現(xiàn)類

import java.util.Scanner;
/**
* 通過構(gòu)建邊和點(diǎn)的對(duì)象來創(chuàng)建圖
* @author King
*/
public class CreateGraph {
/**
* 根據(jù)頂點(diǎn)信息String，返回邊的對(duì)象
* @param graph 圖
* @param str 頂點(diǎn)名稱
* @return 返回的是邊對(duì)象的標(biāo)簽
*/
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;
}
/**
* 該函數(shù)用于圖的初始化的實(shí)現(xiàn)
* @param graph 圖
*/
public void initialGraph(Graph graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù)：");
graph.vertexNum=scan.nextInt();
graph.edgeNum=scan.nextInt();
System.out.println("請(qǐng)依次輸入定點(diǎn)名稱：");
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("請(qǐng)依次輸入每個(gè)邊：");
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("輸入頂點(diǎn)數(shù)據(jù)錯(cuò)誤！");
//下面代碼是圖構(gòu)建的核心：鏈表操作
Edge edge1=new Edge();
edge1.edgeName=v2;
edge1.next=graph.vertexList.get(v1).firstEdge;
graph.vertexList.get(v1).firstEdge=edge1;
// 下面代碼加上便是構(gòu)建無向圖，不加便是構(gòu)建有向圖
// 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、以上面給出的圖片中圖為例運(yùn)行結(jié)果展示：

三、使用鄰接表構(gòu)建圖的實(shí)例

問題：隨機(jī)生成一個(gè)圖（可以是有向圖或是無向圖），圖的頂點(diǎn)大概100個(gè)左右，若是有向圖則邊大概2000條左右，若是無向圖則邊大概1000條左右！并計(jì)算出邊的入度和出度

代碼：

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、隨機(jī)圖實(shí)現(xiàn)類

import java.util.Scanner;
/**
* 隨機(jī)生成一個(gè)圖，計(jì)算每個(gè)頂點(diǎn)的入度和出度
* @author King
*
*/
public class CreateGraph2 {
/**
* 由頂點(diǎn)名稱返回頂點(diǎn)集合中的該頂點(diǎn)
* @param graph 圖
* @param name 頂點(diǎn)名稱
* @return返回頂點(diǎn)對(duì)象
*/
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;
}
/**
* 該頂點(diǎn)通過頂點(diǎn)和邊構(gòu)建圖
* @param graph 圖
*/
public void randomSpanning(GraphRandom graph){
@SuppressWarnings("resource")
Scanner scan=new Scanner(System.in);
System.out.println("請(qǐng)輸入隨機(jī)圖的頂點(diǎn)個(gè)數(shù)：");
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("隨機(jī)生成的邊的數(shù)量為："+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("隨機(jī)圖中沒有該頂點(diǎn)！");
VertexRandom vertex2=new VertexRandom();
vertex2.verName=folV;
vertex2.nextNode=vertex1.nextNode;
vertex1.nextNode=vertex2;
// 下面用于計(jì)算頂點(diǎn)的出度和入度的
vertex1.outRadius++;
VertexRandom v2=getVertex(graph,folV);
if(v2==null)
System.out.println("隨機(jī)圖中沒有該頂點(diǎn)！");
v2.inRadius++;
// 加上下面代碼用于產(chǎn)生無向圖
// VertexRandom reVertex2=getVertex(graph,folV);
// if(reVertex2==null)
// System.out.println("隨機(jī)圖中沒有該頂點(diǎn)！");
// 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("頂點(diǎn)"+(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);
}
}

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: