JAVA第33天——图（二）——进阶知识

是图的一种链式储存结构。在邻接表中，对图中的每个顶点建立一个单链表。每一个顶点的数据结构——结点，分3个域。为了随机访问任一顶点，每一个表结点前，设置了表头结点。因为表头结点可以以顺序结构的形式存储。无向图，n个顶点，e条边，需要n个头结点，2e个表结点。

表结点：

邻接点域：vi，adjvex链域：下一条弧的结点,nextarc数据域：储存弧相关的信息，如权值,info

表头结点：

数据域:data链域:firstarc

邻接表的数据结构：

#define MAX_VEX 20
typedef enum
{
	DG, // 有向图
	UDG // 无向图
}GraphKind; 
typedef struct ArcNode
{
	int adjvex; // 顶点的位置下标
	struct ArcNode * nextarc; // 指向下一条弧的指针
	int * info;
}ArcNode;
typedef struct VNode
{
	char data;
	ArcNode * firstarc;
}VNode, AdjList[MAX_VEX];
typedef struct
{
	AdjList vertices; // 挂接了链表的顶点数组
	int vexnum;
	int arcnum;
	GraphKind kind; 
}ALGraph;

图例：

Java语言实现：