【邻接表特点,邻接表的代码实现】

邻接表（Adjacency List） 是图的一种链式存储结构。

#include
using namespace std;

#define MVNum 100	//最大顶点数
#define OtherInfo int //权值
#define VerTexType int//顶点的指针域
#define Status int

typedef struct ArcNode {	//边结点
	int adjvex;//该边指向的顶点的位置
	struct ArcNode* nextarc;//指向下一条边的指针
	OtherInfo info;//和边相关的信息，如权值等
}ArcNode;

typedef struct VNode {//顶点信息
	VerTexType data;
	ArcNode* firstarc;//指向第一条依附于该顶点的边的指针
}VNode,AdjList[MVNum];//邻接表

typedef struct
{
	AdjList vertices;//图的边结点组成的数组
	int vexnum, arcnum;//图的边结点的所有顶点数和边数
}ALGraph;

int LocateVex(ALGraph G, VerTexType v);

//创建无向图
Status CreateALGraph(ALGraph& G) {
	ArcNode* p1,*p2;
	int i,j;
	cout<<"请输入邻接表的顶点数和边的数目： " << endl;
	cin >> G.vexnum >> G.arcnum;
	cout << "请输入邻接表的顶点：" << endl;
	for (i = 0; i < G.vexnum; i++) {
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;//初始化邻接点
	}
	for (i = 0; i < G.arcnum; i++) {
		VerTexType v1, v2;
		cin >> v1>> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);//确定v1，v2在G中的位置，即顶点在G.vertices中的序号
		p1 = new ArcNode;//生成一个新的边结点*p1
		p1->adjvex = j;//邻接点序号j
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;//将新结点*p1插入顶点vi的表边结点
		p2 = new ArcNode;//生成另一个对称的新的边结点*p2
		p2->adjvex = i;//邻接结点序号i
		p2->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
		//将新结点插入顶点vj的边表头部
	}
	return 1;
}

int LocateVex(ALGraph G, VerTexType v) {//返回顶点u在图中的位置
	int i;
	for (i = 0; i < G.vexnum && G.vertices[i].data != v; i++) {
		if (i == G.vexnum) {
			return -1;
		}
		else {
			return i;
		}
	}
}

void showAdj(ALGraph G) {
	int i;
	cout << "头结点	邻接点" << endl;
	for (i = 0; i < G.vexnum; i++) {
		cout << G.vertices[i].data << " ";
		ArcNode* ptr = G.vertices[i].firstarc;
		while (ptr != NULL) {
			cout << "-->" << G.vertices[ptr->adjvex].data << " ";
			ptr = ptr->nextarc;
		}
		cout << endl;
	}
}

int main() {
	ALGraph G;
	CreateALGraph(G);
	showAdj(G);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

邻接表特点

• 方便找任一顶点的所有“邻接点”。
• 节约稀疏图的空间
  • 需要N个头指针+2E个结点（每个结点2个域）。
• 方便计算任一顶点的“度”？
  • 对无向图：是的
  • 对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”
• 不方便检查任意一对顶点间是否存在边。

邻接矩阵和邻接表表示法的关系

区别：
1.对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
2.邻接矩阵的空间复杂度为O（n平方），而邻接表的空间复杂度为O（n+e）。
用途：
邻接矩阵多用于稠密图；而邻接表多用于稀疏图。