前言
本篇来谈一谈图的邻接表实现的两种方式，首先我们明确一点“学会图的邻接表实现的关键点在于“：你所建立的图的邻接表的对象是什么！
首先我们看一下《算法导论》中关于图的邻接表的定义：
图G=(V,E)的邻接表表示有一个包含 |V| 个列表的数组Adj所组成，其中每个列表对应于V中的一个顶点，对于每一个u∈V，邻接表Adj[u]包含所有满足条件（u，v）∈E的顶点v，亦即，Adj[u]包含图G中所有和顶点u相邻的顶点。（或者他也可能指向这些顶点的指针），每个邻接表中的顶点一般以任意的顺序存储。
图的邻接表表示如下图所示：
定义总是比较晦涩难懂的，下面我们从如何实现图的邻接表表示来谈一谈！
1、邻接表构建图是必须需要一个Graph对象，也就是图对象！该对象包含属性有：顶点数、边数以及图的顶点集合；
2、正如上面所说，邻接链表的对象首先我们需要确定邻接表的对象，可以用顶点作为邻接链表的对象，自然也可以用边作为邻接链表的对象！下面将分别对这两种方式进行讲解！
一、邻接链表使用顶点作为对象构建图
1、Graph对象类
public class Graph1 {
Vertex1[] vertexArray=new Vertex1[100];
int verNum=0;
int edgeNum=0;
}
2、Vertex对象类
public class Vertex1 {
String verName;
Vertex1 nextNode;
}
3、图的实现类
import java.util.Scanner;
public class CreateGraph3 {
public Vertex1 getVertex(Graph1 graph,String str){
for(int i=0;i"+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);
}
}
二、邻接链表使用边作为对象构建图
1、Graph对象类
import java.util.ArrayList;
public class Graph {
ArrayList vertexList=new ArrayList();
int vertexNum=0;
int edgeNum=0;
public Graph(){}
}
2、Edge对象类
public class Edge {
int edgeName;
Edge next;
public Edge(){
}
}
3、Vertex对象类<这里顶点对象只是辅助边构建图，不是作为邻接链表的对象>
public class Vertex {
String vertexName;
Edge firstEdge=new Edge();
public Vertex(){
}
}
4、图的实现类
import java.util.Scanner;
public class CreateGraph {
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、以上面给出的图片中图为例运行结果展示：
三、使用邻接表构建图的实例
问题：随机生成一个图（可以是有向图或是无向图），图的顶点大概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;
public class CreateGraph2 {
public VertexRandom getVertex(GraphRandom graph,int name){
for(int i=0;i"+current.verName);
current=current.nextNode;
}
System.out.println();
}
}
public void IORadius(GraphRandom graph){
for(int i=0;i
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。
