邻接表表示图

邻接表是一种表示图的数据结构，用于存储图中每个节点的邻居节点列表。它是一种链式存储结构，每个节点对应一个链表，链表中存储该节点的所有邻居节点。邻接表通常用于表示稀疏图，即节点数比较多，但是节点之间的边比较少的情况。

具体来说，设图 G=(V,E) 是有 n 个节点和 m 条边的无向图，邻接表的实现步骤如下：

1. 用一个数组 adj[1...n] 存储每个节点的邻居节点链表，其中 adj[i] 表示节点 i 的邻居节点链表。

2. 对于每个节点 i，将它的邻居节点列表存储在 adj[i] 的链表中，链表中的每个元素表示节点 i 的一个邻居节点。

举个例子，假设有如下无向图：

     1 -- 2
    / \   \
   3 - 4 - 5

则邻接表的实现如下：

adj[1]: 2 -> 3
adj[2]: 1 -> 4 -> 5
adj[3]: 1 -> 4
adj[4]: 3 -> 2 -> 5 -> 1
adj[5]: 2 -> 4

其中，adj[1] 对应的链表是 {2, 3}，表示节点 1 的邻居节点分别是 2 和 3；adj[2] 对应的链表是 {1, 4, 5}，表示节点 2 的邻居节点分别是 1、4 和 5。

相关问题

如何用邻接表表示图？

在C语言中，我们可以使用邻接表来表示图。邻接表是一种链式存储结构，它由一个数组和一个链表组成。数组中的每个元素表示一个顶点，链表中的每个节点表示该顶点所连向的其他顶点。

具体来说，我们可以定义一个结构体来表示邻接表中的节点，该结构体包含两个成员变量：一个表示该节点所连向的顶点的编号，另一个表示下一个节点的指针。然后，我们可以定义一个数组来存储所有的节点，数组的大小为图中顶点的个数。对于每个顶点，我们可以用一个指针指向以该顶点为起点的链表。

下面是一个简单的示例代码，用邻接表表示一个无向图：

#include <stdio.h>
#include <stdlib.h>

// 邻接表中的节点
typedef struct node {
    int vertex;           // 该节点所连向的顶点的编号
    struct node* next;    // 下一个节点的指针
} Node;

// 邻接表
typedef struct graph {
    int numVertices;      // 顶点的个数
    Node** adjLists;      // 指向链表的指针数组
} Graph;

// 创建一个节点
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;}

// 创建一个图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;

    // 创建指向链表的指针数组
    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));

    // 将每个指针初始化为 NULL
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

// 添加一条边
void addEdge(Graph* graph, int src, int dest) {
    // 将 dest 添加到 src 的链表中
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 将 src 添加到 dest 的链表中
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 打印邻接表
void printGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        printf("顶点 %d 的邻接表：\n", i);
        Node* temp = graph->adjLists[i];
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

在上面的代码中，我们首先定义了一个 `Node` 结构体来表示邻接表中的节点，然后定义了一个 `Graph` 结构体来表示整个邻接表。在 `createGraph` 函数中，我们首先创建了一个 `Graph` 结构体，并为其分配了一个指向链表的指针数组。在 `addEdge` 函数中，我们将 `dest` 添加到 `src` 的链表中，并将 `src` 添加到 `dest` 的链表中。最后，在 `printGraph` 函数中，我们遍历整个邻接表，并打印出每个顶点的邻接表。

如何使用邻接表表示图？

邻接表是一种常用的图的表示方法，它使用链表来表示每个顶点的邻接点集合。下面是使用邻接表表示图的步骤：

1. 定义一个结构体来表示每个顶点，结构体中包含该顶点的编号和指向该顶点的所有边的指针。

2. 定义一个数组来存储所有的顶点，数组的下标即为顶点的编号。

3. 对于每个顶点，使用一个链表来存储它的所有邻接点。

4. 对于每条边，将它的起点顶点的链表中添加一个指向终点顶点的指针。

5. 如果是有向图，只需要在起点顶点的链表中添加指向终点顶点的指针；如果是无向图，还需要在终点顶点的链表中添加指向起点顶点的指针。

使用邻接表表示图的优点是可以节省空间，特别是对于稀疏图来说，因为只需要存储每个顶点的邻接点，而不需要存储所有的边。但是对于稠密图来说，邻接矩阵的方式更为方便。