前言
成都創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的雁塔網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！
本篇來談一談圖的鄰接表實現(xiàn)的兩種方式，首先我們明確一點“學(xué)會圖的鄰接表實現(xiàn)的關(guān)鍵點在于“：你所建立的圖的鄰接表的對象是什么！
首先我們看一下《算法導(dǎo)論》中關(guān)于圖的鄰接表的定義：
圖G=(V,E)的鄰接表表示有一個包含 |V| 個列表的數(shù)組Adj所組成，其中每個列表對應(yīng)于V中的一個頂點，對于每一個u∈V，鄰接表Adj[u]包含所有滿足條件（u，v）∈E的頂點v，亦即，Adj[u]包含圖G中所有和頂點u相鄰的頂點。（或者他也可能指向這些頂點的指針），每個鄰接表中的頂點一般以任意的順序存儲。
圖的鄰接表表示如下圖所示：
定義總是比較晦澀難懂的，下面我們從如何實現(xiàn)圖的鄰接表表示來談一談！
1、鄰接表構(gòu)建圖是必須需要一個Graph對象，也就是圖對象！該對象包含屬性有：頂點數(shù)、邊數(shù)以及圖的頂點集合；
2、正如上面所說，鄰接鏈表的對象首先我們需要確定鄰接表的對象，可以用頂點作為鄰接鏈表的對象，自然也可以用邊作為鄰接鏈表的對象！下面將分別對這兩種方式進行講解！
一、鄰接鏈表使用頂點作為對象構(gòu)建圖
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、圖的實現(xiàn)類
import java.util.Scanner;
public class CreateGraph4 {
/**
* 根據(jù)用戶輸入的string類型的頂點返回該頂點
* @param graph 圖
* @param str 輸入數(shù)據(jù)
* @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);
}
} 二、鄰接鏈表使用邊作為對象構(gòu)建圖
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對象類<這里頂點對象只是輔助邊構(gòu)建圖，不是作為鄰接鏈表的對象>
/**
* 圖的點對象類
* @author King
*/
public class Vertex {
String vertexName;
Edge firstEdge=new Edge();
public Vertex(){
}
}4、圖的實現(xiàn)類
import java.util.Scanner;
/**
* 通過構(gòu)建邊和點的對象來創(chuàng)建圖
* @author King
*/
public class CreateGraph {
/**
* 根據(jù)頂點信息String，返回邊的對象
* @param graph 圖
* @param str 頂點名稱
* @return 返回的是邊對象的標(biāo)簽
*/
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、以上面給出的圖片中圖為例運行結(jié)果展示：
三、使用鄰接表構(gòu)建圖的實例
問題：隨機生成一個圖（可以是有向圖或是無向圖），圖的頂點大概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、隨機圖實現(xiàn)類
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 以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
