亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

java實現圖的鄰接表存儲結構的兩種方式及實例應用詳解

發布時間:2020-09-14 06:13:36 來源:腳本之家 閱讀:538 作者:feilong_csdn 欄目:編程語言

前言

本篇來談一談圖的鄰接表實現的兩種方式,首先我們明確一點“學會圖的鄰接表實現的關鍵點在于“:你所建立的圖的鄰接表的對象是什么!

首先我們看一下《算法導論》中關于圖的鄰接表的定義:

圖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<graph.verNum;i++){
if(graph.vertexArray[i].verName.equals(str)){
return graph.vertexArray[i];
}
}
return null;
}
/**
* 根據用戶輸入的數據初始化一個圖,以鄰接表的形式構建!
* @param graph 生成的圖
*/
public void initialGraph(Graph2 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(Graph2 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) {
Graph2 graph=new Graph2();
CreateGraph4 createGraph=new CreateGraph4();
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、以上面給出的圖片中圖為例運行結果展示:

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<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();
CreateGraph3 createGraph3=new CreateGraph3();
createGraph3.randomSpanning(graph);
createGraph3.outputGraph(graph);
createGraph3.IORadius(graph);
}
}

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持億速云。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

漯河市| 堆龙德庆县| 庆元县| 乐平市| 阳泉市| 房山区| 景东| 马山县| 驻马店市| 浦江县| 龙里县| 天水市| 平江县| 衡水市| 和林格尔县| 开阳县| 崇礼县| 灯塔市| 古丈县| 青川县| 吴忠市| 晋州市| 太谷县| 神池县| 武强县| 新竹县| 宣武区| 淳化县| 息烽县| 余江县| 长治县| 吉木乃县| 杭锦后旗| 镇巴县| 湖北省| 合肥市| 阿克苏市| 博白县| 惠安县| 化德县| 卫辉市|