一、图的邻接表结构Java语言代码实现：
- 图的四种类型枚举类：
package bigjun.iplab.adjacencyList; /** * 图的四种主要类型的枚举类 */ public enum GraphKind { UDG, // 无向图 DG, // 有向图 UDN, // 无向网 DN, // 有向网 }
- 图的邻接表存储结构的顶点结点类：
package bigjun.iplab.adjacencyList; /** * 图的邻接表存储结构中的顶点结点类 */ public class VexNode { public Object data; // 顶点的信息 public ArcNode firstArc; // 指向第一条依附于该顶点的弧 public VexNode() { this(null, null); } public VexNode(Object data) { this(data, null); } public VexNode(Object data, ArcNode firstArc) { this.data = data; this.firstArc = firstArc; } public Object getData() { return data; } public ArcNode getFirstArc() { return firstArc; } }
- 图的邻接表存储结构的边（或弧）结点类：
package bigjun.iplab.adjacencyList; /** * 图的邻接表存储结构中的边(或弧)结点类 */ public class ArcNode { public int adjVex; // 该弧所指向的顶点在顶点数组中的下标 public int weight; // 边或弧的权值 public ArcNode nextArc; // 指向下一条表示边或弧的结点类 public ArcNode() { this(-1, 0, null); } public ArcNode(int adjVex) { this(adjVex, 0, null); } public ArcNode(int adjVex, int weight) { this(adjVex, weight, null); } public ArcNode(int adjVex, int weight, ArcNode nextArc) { this.adjVex = adjVex; this.weight = weight; this.nextArc = nextArc; } }
- 图的邻接表存储结构接口类：
package bigjun.iplab.adjacencyList; /** * 图的邻接矩阵存储结构接口类 */ public interface AdjacencyListGraphINF { // 创建一个图 public void createGraph(); // 返回图中的顶点数 public int getVexNum(); // 返回图中的边数 public int getArcNum(); // 给定顶点的位置v，返回其对应的顶点值 public Object getVex(int x) throws Exception; // 给定顶点的值vex，返回其在图中的位置 public int locateVex(Object vex); // 返回顶点v的第一个邻接点 public int firstAdjvex(int v) throws Exception; // 返回v相对于w的下一个邻接点 public int nextAdjvex(int v, int w) throws Exception; // 在图中插入有权重的边或弧结点 public void addArc(int v, int u, int weight); // 在图中插入没有权值的边或弧结点 public void addArc(int v, int u); }
- 图的邻接表存储结构实现类：
package bigjun.iplab.adjacencyList; import java.util.Scanner; public class AdjListGraph implements AdjacencyListGraphINF{ private GraphKind kind; // 图的种类标志 private int vexNum, arcNum; // 顶点数，边数 private VexNode[] vexs; // 顶点结点组成的顶点数组 public GraphKind getKind() { return kind; } public Object[] getVexs() { return vexs; } // 构造方法1: 构造一个空图 public AdjListGraph() { this(null, 0, 0, null); } // 构造方法2: 构造一个非空图 public AdjListGraph(GraphKind kind, int vexNum, int arcNum, VexNode[] vexs) { this.kind = kind; this.vexNum = vexNum; this.arcNum = arcNum; this.vexs = vexs; } // 创建图的四种类型中的一种 public void createGraph() { @SuppressWarnings("resource") Scanner scanner = new Scanner(System.in); System.out.println("请输入图的类型代号(UDG(无向图)、DG(有向图)、UDN(无向网)、DN(有向网)):"); GraphKind kind = GraphKind.valueOf(scanner.next()); switch (kind) { case UDG: createUnDirecedGraph(); return; case DG: createDirectedGraph(); return; case UDN: createUnDirectedNet(); return; case DN: createDirectedNet(); return; } System.out.println("图已创建完成！"); } // 创建无向图 private void createUnDirecedGraph() { @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); System.out.println("请分别输入图的顶点数，图的边数: "); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new VexNode[vexNum]; // 创建顶点结点数组 System.out.println("请分别输入图的各个顶点: "); for (int i = 0; i < vexNum; i++) { // 初始化顶点一维数组 vexs[i] = new VexNode(sc.next()); } System.out.println("请输入各个边的两个顶点(第一个输入是弧尾，第二个输入是弧头): "); for (int k = 0; k < arcNum; k++) { // 填入对应的权值 int v = locateVex(sc.next()); int u = locateVex(sc.next()); addArc(v, u); addArc(u, v); // 无向图是双向的弧 } } // 创建有向图 private void createDirectedGraph() { @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); System.out.println("请分别输入图的顶点数，图的边数: "); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new VexNode[vexNum]; // 创建顶点结点数组 System.out.println("请分别输入图的各个顶点: "); for (int i = 0; i < vexNum; i++) { // 初始化顶点一维数组 vexs[i] = new VexNode(sc.next()); } System.out.println("请输入各个边的两个顶点(第一个输入是弧尾，第二个输入是弧头): "); for (int k = 0; k < arcNum; k++) { // 填入对应的权值 int v = locateVex(sc.next()); int u = locateVex(sc.next()); addArc(v, u); } } // 创建无向网 private void createUnDirectedNet() { @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); System.out.println("请分别输入图的顶点数，图的边数: "); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new VexNode[vexNum]; // 创建顶点结点数组 System.out.println("请分别输入图的各个顶点: "); for (int i = 0; i < vexNum; i++) { // 初始化顶点一维数组 vexs[i] = new VexNode(sc.next()); } System.out.println("请输入各个边的两个顶点及其权值(第一个输入是弧尾，第二个输入是弧头): "); for (int k = 0; k < arcNum; k++) { // 填入对应的权值 int v = locateVex(sc.next()); int u = locateVex(sc.next()); int weight = sc.nextInt(); addArc(v, u, weight); addArc(u, v, weight); // 无向网是双向的弧 } } // 创建有向网 private void createDirectedNet() { @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); System.out.println("请分别输入图的顶点数，图的边数: "); vexNum = sc.nextInt(); arcNum = sc.nextInt(); vexs = new VexNode[vexNum]; // 创建顶点结点数组 System.out.println("请分别输入图的各个顶点: "); for (int i = 0; i < vexNum; i++) { // 初始化顶点一维数组 vexs[i] = new VexNode(sc.next()); } System.out.println("请输入各个边的两个顶点及其权值(第一个输入是弧尾，第二个输入是弧头): "); for (int k = 0; k < arcNum; k++) { // 填入对应的权值 int v = locateVex(sc.next()); int u = locateVex(sc.next()); int weight = sc.nextInt(); addArc(v, u, weight); } } // 返回顶点数 public int getVexNum() { return vexNum; } // 返回边数 public int getArcNum() { return arcNum; } // 返回v表示结点的值 public Object getVex(int x) throws Exception{ if (x < 0 && x >= vexNum ) throw new Exception("给定的顶点不存在"); return vexs[x].data; } // 返回顶点的值为vex的顶点在顶点数组的位置下标，如果图中不包含值为vex的顶点，则返回-1，例如，顶点名称为V0 public int locateVex(Object vex) { for (int v = 0; v < vexNum; v++) { if (vexs[v].data.equals(vex)) { return v; } } return -1; } // 返回下标为v的顶点的第一个邻接点，即遍历邻接矩阵的第v行,找到之后，返回第v行对应的下标 public int firstAdjvex(int v) throws Exception { if (v < 0 && v >= vexNum ) throw new Exception("给定的顶点不存在"); VexNode vex = vexs[v]; if (vex.firstArc != null) { return vex.firstArc.adjVex; } else { return -1; } } // 返回下标为v的顶点相对于下标为w的顶点的下一个邻接点，若w是v的最后一个邻接点，则返回-1 public int nextAdjvex(int v, int w) throws Exception { if (v < 0 && v >= vexNum ) throw new Exception("给定的顶点不存在"); VexNode vex = vexs[v]; ArcNode arcvTOw = null; for (ArcNode arc = vex.firstArc; arc != null; arc = arc.nextArc) { if (arc.adjVex == w) { arcvTOw = arc; break; } } if (arcvTOw != null && arcvTOw.nextArc != null) { return arcvTOw.nextArc.adjVex; } else { return -1; } } // 在位置为v、u的顶点之间，添加一条弧，权值为weight public void addArc(int v, int u, int weight) { ArcNode arc = new ArcNode(u, weight); arc.nextArc = vexs[v].firstArc; vexs[v].firstArc = arc; } // 在位置为v、u的顶点之间，添加一条没有权重的弧 public void addArc(int v, int u) { ArcNode arc = new ArcNode(u); arc.nextArc = vexs[v].firstArc; vexs[v].firstArc = arc; } public static void main(String[] args) throws Exception { AdjListGraph aListGraph = new AdjListGraph(); aListGraph.createGraph(); System.out.println("该类型的图已经创建完成！"); System.out.println("顶点数组下标为2的第一个邻接点的数组下标是: " + aListGraph.firstAdjvex(2)); int numOfV2 = aListGraph.firstAdjvex(2); System.out.println("顶点V2的第一个邻接点是: " + aListGraph.getVex(numOfV2)); System.out.println("顶点数组下标为2的相对于顶点数组下标为0的下一个邻接点的数组下标是: " + aListGraph.nextAdjvex(2, 0)); int numOfV2toV0next = aListGraph.nextAdjvex(2, 0); System.out.println("顶点V2相对于V0的邻接点是: " + aListGraph.getVex(numOfV2toV0next)); } }
- 以下面的例子为例：
- 输出：
请输入图的类型代号(UDG(无向图)、DG(有向图)、UDN(无向网)、DN(有向网)): DN 请分别输入图的顶点数，图的边数: 5 6 请分别输入图的各个顶点: V0 V1 V2 V3 V4 请输入各个边的两个顶点及其权值(第一个输入是弧尾，第二个输入是弧头): V0 V4 6 V1 V2 3 V1 V0 9 V2 V3 5 V2 V0 2 V3 V4 1 该类型的图已经创建完成！ 顶点数组下标为2的第一个邻接点的数组下标是: 0 顶点V2的第一个邻接点是: V0 顶点数组下标为2的相对于顶点数组下标为0的下一个邻接点的数组下标是: 3 顶点V2相对于V0的邻接点是: V3
二、图的邻接表结构C语言代码实现：
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXVEX 100 /* 最大顶点数,应由用户定义 */ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef char VertexType; /* 顶点类型应由用户定义 */ typedef int EdgeType; /* 边上的权值类型应由用户定义 */ typedef struct EdgeNode /* 边表结点 */ { int adjvex; /* 邻接点域,存储该顶点对应的下标 */ EdgeType info; /* 用于存储权值,对于非网图可以不需要 */ struct EdgeNode *next; /* 链域,指向下一个邻接点 */ }EdgeNode; typedef struct VertexNode /* 顶点表结点 */ { VertexType data; /* 顶点域,存储顶点信息 */ EdgeNode *firstedge;/* 边表头指针 */ }VertexNode, AdjList[MAXVEX]; typedef struct { AdjList adjList; int numNodes,numEdges; /* 图中当前顶点数和边数 */ }GraphAdjList; /* 建立图的邻接表结构 */ void CreateALGraph(GraphAdjList *G) { int i,j,k; EdgeNode *e; printf("输入顶点数和边数: "); scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */ for(i = 0;i < G->numNodes;i++) /* 读入顶点信息,建立顶点表 */ { scanf(&G->adjList[i].data); /* 输入顶点信息 */ G->adjList[i].firstedge=NULL; /* 将边表置为空表 */ } for(k = 0;k < G->numEdges;k++)/* 建立边表 */ { printf("输入边(vi,vj)上的顶点序号: "); scanf("%d,%d",&i,&j); /* 输入边(vi,vj)上的顶点序号 */ e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */ e->adjvex=j; /* 邻接序号为j */ e->next=G->adjList[i].firstedge; /* 将e的指针指向当前顶点上指向的结点 */ G->adjList[i].firstedge=e; /* 将当前顶点的指针指向e */ e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */ e->adjvex=i; /* 邻接序号为i */ e->next=G->adjList[j].firstedge; /* 将e的指针指向当前顶点上指向的结点 */ G->adjList[j].firstedge=e; /* 将当前顶点的指针指向e */ } } int main(void) { GraphAdjList G; CreateALGraph(&G); return 0; }