图的邻接表表示法

图是离散数学中一个重要的概念，有着广泛的应用。在计算机科学中，图在很多领域都有着重要的作用，如路由算法、数据挖掘、图像处理等等。为了进行图的计算，在计算机中需要用数据结构来表示图。其中一种比较常用的数据结构是邻接表。

邻接表是一种基于链表的数据结构，用于表示无向图和有向图中的边。邻接表表示法将图中每个顶点和和其相邻顶点构成一个链表，从而构成了整个图的邻接表。简单来说，邻接表就是用链表来存储每个顶点相邻的顶点。

邻接表的数据结构如下图所示：

![邻接表的数据结构][1]

从图中可以看出，这是一个有着6个顶点和8条边的简单图。每个顶点对应了一个链表，其中存储了与该顶点相邻的顶点。比如顶点1有与之相邻的顶点2、3和4，因此在邻接表中，节点1对应的链表中就存储了2、3和4这三个顶点。

邻接表的实现方法比较简单。首先需要定义一个数据结构来表示图中每个顶点及其相邻的顶点，如下所示：

```

// 顶点结构体

struct Vertex {

int val; // 顶点的值

struct Vertex *next; // 与该顶点相邻的下一个顶点

};

```

然后再定义一个数据结构来表示整个图，如下所示：

```

// 图结构体

struct Graph {

int vertex_num; // 顶点数目

struct Vertex **adj_list; // 邻接表

};

```

最后需要对每个顶点创建一个链表来存储与其相邻的顶点。具体实现方法如下：

```

// 创建邻接表

void create_adj_list(struct Graph *graph) {

for (int i = 0; i < graph->vertex_num; i++) {

graph->adj_list[i] = (struct Vertex*)malloc(sizeof(struct Vertex));

graph->adj_list[i]->next = NULL;

}

}

```

邻接表的优缺点

邻接表作为一种图的表示方法，具有以下优点：

1. 用邻接表表示稀疏图时，空间效率较高，因为只需要存储每个顶点的度数和边数。

2. 在邻接表中查询与一个顶点相邻的所有顶点时，时间复杂度为O(1)+O(k)，其中k为该顶点的度数，因此时间复杂度较低。

3. 邻接表可以表示有向图和无向图。

4. 可以方便地添加或删除图中的顶点或边。

邻接表也存在一些不足之处：

1. 在邻接表中查找两个顶点之间是否有边时，时间复杂度为O(k)，其中k为两个顶点的度数之和，因此当图比较密集时，时间复杂度会比较高。

2. 对于要求图中边权值的问题，用邻接表来存储边权值较为不便，因为每一个顶点只存储了与之相邻的点，而没有存储边的权值。

使用场景

邻接表在很多场景中都有着广泛的应用，以下是几个常见的使用场景：

1. 最小生成树问题

邻接表可以方便地在图中搜索最小生成树，因为只需要找到每个顶点相邻的所有顶点，并记录它们之间的边权值，就可以通过Kruskal算法或Prim算法等方法构造最小生成树。

2. 网络路由

在网络中，路由算法是一种用于计算数据包最合适路径的算法，而邻接表就是用来表示网络中所有节点和边的常用数据结构之一，因此很多网络路由算法都用到邻接表。

3. 数据挖掘

在数据挖掘领域，图常用来表示数据之间的复杂关系，而邻接表就是很常见的一种图的表示方法，因此在很多数据挖掘算法中都用到了邻接表。