如何使用邻接表表示图？

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

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

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

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

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` 函数中，我们遍历整个邻接表，并打印出每个顶点的邻接表。

无向图邻接表怎么写？

无向图的邻接表是一种常用的数据结构，用于表示无向图中各个顶点之间的关系。邻接表由一个数组和一组链表组成，数组的每个元素表示一个顶点，链表则表示与该顶点相邻的其他顶点。

下面是一个示例代码，演示了如何使用邻接表表示无向图：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Graph:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        self.adj_list = [None] * num_vertices

    def add_edge(self, src, dest):
        # 添加边，将顶点dest添加到顶点src的链表中
        node = Node(dest)
        node.next = self.adj_list[src]
        self.adj_list[src] = node

        # 由于是无向图，所以还需要将顶点src添加到顶点dest的链表中
        node = Node(src)
        node.next = self.adj_list[dest]
        self.adj_list[dest] = node

    def print_adj_list(self):
        # 输出邻接表
        for i in range(self.num_vertices):
            print("顶点", i, "的邻接表：")
            node = self.adj_list[i]
            while node:
                print(" ->", node.value, end="")
                node = node.next
            print()

# 创建一个无向图
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 4)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(3, 4)

# 输出邻接表
g.print_adj_list()

运行以上代码，将会输出如下结果：

顶点 0 的邻接表：
 -> 4 -> 1
顶点 1 的邻接表：
 -> 4 -> 3 -> 2 -> 0
顶点 2 的邻接表：
 -> 3 -> 1
顶点 3 的邻接表：
 -> 4 -> 2 -> 1
顶点 4 的邻接表：
 -> 3 -> 1 -> 0