溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
前言
本篇來談一談圖的鄰接表實現的兩種方式，首先我們明確一點“學會圖的鄰接表實現的關鍵點在于“：你所建立的圖的鄰接表的對象是什么！
首先我們看一下《算法導論》中關于圖的鄰接表的定義：
圖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 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、以上面給出的圖片中圖為例運行結果展示：
三、使用鄰接表構建圖的實例
問題：隨機生成一個圖（可以是有向圖或是無向圖），圖的頂點大概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);
}
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
