采用邻接表创建无向图举例和解析

邻接表是一种常用的图的存储方式，它通过链表的方式存储每个顶点的邻接点，可以很方便地实现图的遍历和其他操作。下面是一个采用邻接表创建无向图的例子和解析：

假设我们要创建如下无向图：

1--2--3
|  |  |
4--5--6

我们可以使用邻接表来存储这个图。具体步骤如下：

1. 创建一个包含所有顶点的列表，每个顶点对应一个链表。
2. 对于每条边 (u, v)，在顶点 u 的链表中添加一个指向顶点 v 的节点，在顶点 v 的链表中添加一个指向顶点 u 的节点。

根据上述步骤，我们可以得到如下的邻接表：

1: -> 2 -> 4
2: -> 1 -> 3 -> 5
3: -> 2 -> 6
4: -> 1 -> 5
5: -> 2 -> 4 -> 6
6: -> 3 -> 5

其中，每个数字代表一个顶点，箭头表示链表中的指向关系。例如，1: -> 2 -> 4 表示顶点 1 的链表中有两个节点，分别指向顶点 2 和顶点 4。

邻接表的创建过程比较简单，而且可以很方便地实现图的遍历和其他操作。如果需要创建有向图，只需要在添加边的时候只在一个顶点的链表中添加节点即可。

相关问题

邻接表创建无向图

邻接表是一种常见的图的存储方式，可以用于存储有向图和无向图。下面是邻接表创建无向图的步骤：

1. 定义一个邻接表的数据结构，一般包含两个部分：节点数组和邻接表数组。

2. 定义节点结构体，包含节点的值和指向第一个邻接节点的指针。

3. 初始化邻接表数组，将每个元素的指针初始化为 NULL。

4. 读取无向图的边信息，对于每条边 (u, v)，在节点 u 和节点 v 的邻接表中分别添加一个指向对方节点的指针。

5. 如果无向图中存在自环边，即 (u, u)，则在节点 u 的邻接表中只添加一个指向自己的指针。

6. 最后输出邻接表即可。

下面是用 C++ 代码实现的邻接表创建无向图的过程：

#include <iostream>
#include <vector>

using namespace std;

// 节点结构体
struct Node {
    int val;                 // 节点的值
    Node* next;              // 指向下一个邻接节点的指针
};

// 邻接表数据结构
class AdjacencyList {
public:
    // 构造函数
    AdjacencyList(int n) {
        nodes.resize(n);
        for (int i = 0; i < n; i++) {
            nodes[i].val = i;   // 节点值初始化为下标
            nodes[i].next = NULL;
        }
    }

    // 添加无向图边
    void addEdge(int u, int v) {
        Node* node_u = &nodes[u];
        while (node_u->next != NULL) {
            node_u = node_u->next;
        }
        Node* new_node_u = new Node();
        new_node_u->val = v;
        new_node_u->next = NULL;
        node_u->next = new_node_u;

        Node* node_v = &nodes[v];
        while (node_v->next != NULL) {
            node_v = node_v->next;
        }
        Node* new_node_v = new Node();
        new_node_v->val = u;
        new_node_v->next = NULL;
        node_v->next = new_node_v;
    }

    // 输出邻接表
    void printList() {
        for (int i = 0; i < nodes.size(); i++) {
            Node* node = &nodes[i];
            cout << node->val << " -> ";
            while (node->next != NULL) {
                node = node->next;
                cout << node->val << " -> ";
            }
            cout << "NULL" << endl;
        }
    }

private:
    vector<Node> nodes;         // 节点数组
};

int main() {
    int n, m;                   // n 个节点，m 条边
    cin >> n >> m;

    AdjacencyList list(n);      // 创建邻接表

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        list.addEdge(u, v);     // 添加无向图边
    }

    list.printList();           // 输出邻接表

    return 0;
}

上述代码中，我们首先定义了一个节点结构体 `Node`，包括节点的值和指向下一个邻接节点的指针。然后定义了一个邻接表数据结构 `AdjacencyList`，包括节点数组和邻接表数组，其中节点数组中每个元素表示一个节点，邻接表数组中每个元素表示一个节点的邻接表。在 `AdjacencyList` 类中，我们实现了添加无向图边和输出邻接表的方法。在 `main` 函数中，我们读取节点数和边数，然后创建邻接表并添加边，最后输出邻接表。

采用邻接表存储无向图

采用邻接表存储无向图是一种常见的图数据结构方法。在邻接表中，图被表示为一系列的链表或数组，每个节点对应图中的一个顶点，而链表或数组中的元素则是与其相连的顶点列表。具体步骤如下：

1. **节点结构**：每个顶点通常包含一个数据域（存储顶点本身的值）和一个链表（邻接链表），链表中的元素是该顶点连接的其他顶点。

2. **邻接链表**：对于图中的每条边，如果它连接顶点A和顶点B，那么在顶点A的邻接链表中会有一个指向顶点B的指针，同样，在顶点B的邻接链表中也会有一个指针指向顶点A，以保持无向图的对称性。

3. **访问效率**：邻接表非常适合快速查找某个顶点的所有邻居，只需要遍历相应顶点的链表即可。插入和删除边的操作也比较方便，通常只需要修改两个链表的对应元素。

4. **缺点**：空间开销可能会较大，因为对于稠密图（边数接近于顶点数的平方），邻接矩阵可能更为节省空间。此外，查询两个顶点之间是否存在边可能需要查找两次链表，不如邻接矩阵直接。