邻接表的构建步骤

在图数据结构中，邻接表是一种常见的表示方法。它通过将每个顶点链接到其相邻顶点来存储图的信息。邻接表适用于稀疏图（边的数量远小于顶点数量平方），且能以较优的时间复杂度完成各种图操作。本文介绍如何构建一个邻接表。

1. 确定图的类型

首先，根据实际情况确定要使用的无向图还是有向图。无向图表示双向关系，而有向图则表示单向关系。

• 无向图：对于每个边$(u, v)$，在邻接表中需要分别在顶点$u$和$v$处添加指向另一个的指针。
• 有向图：仅需在一个方向上建立从一个节点到另一个节点的连接，例如从顶点$u$到顶点$v$。

2. 初始化顶点列表

对于每个顶点设置相应的数据结构来存储其所有相邻顶点的信息。常见的做法是为每个顶点维护一个链表（或数组）用来保存它直接相连的所有其他顶点的索引或者节点信息。

示例：初始化无向图

struct Node {
    int vertex;
    Node* next;

    Node(int v) : vertex(v), next(nullptr) {}
};

class Graph {
private:
    vector<Node*> adjLists;  // 存储邻接表

public:
    Graph(int V) { adjLists.resize(V); }  // 指定顶点数目
};

示例：初始化有向图

struct Node {
    int vertex;
    Node* next;

    Node(int v) : vertex(v), next(nullptr) {}
};

class Graph {
private:
    vector<Node*> adjLists;  // 存储邻接表

public:
    Graph(int V) { adjLists.resize(V); }  // 指定顶点数目
};

3. 添加边到邻接表中

根据图的类型，按照下面所述的方法添加边：

对于无向图

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = new Node(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 由于是无向图，所以还要添加一条从dest指向src的边。
    newNode = new Node(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

对于有向图

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = new Node(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

4. 验证构建的邻接表

为了确保邻接表正确无误，可以遍历整个图中的每个节点，并打印出它的邻居列表。

示例：验证构建的邻接表

void printGraph(Graph* graph, int V) {
    for (int v = 0; v < V; ++v) {
        cout << "Vertex " << v << " -> ";
        Node* temp = graph->adjLists[v];
        while (temp != nullptr) {
            cout << temp->vertex << " -> ";
            temp = temp->next;
        }
        cout << "\n";
    }
}

通过上述步骤，可以构建出一个邻接表来表示图结构。这不仅适用于理论研究，而且在实际应用中也具有很高的价值。例如在网络分析、路径规划等领域都有广泛的应用场景。