C++中图的邻接表存储

邻接表是一种图的存储结构，它把图中每个顶点的出边存储在一个单链表中，邻接表存储方式的空间复杂度取决于图中边的数量，因此适用于表示稀疏图。

C++中实现邻接表通常使用指针和动态内存分配。每个顶点对应一个链表，链表中的每个节点存储该顶点的一个出边，包括该边所到达的顶点以及该边的权重（如果有的话）。

以下是一个简单的邻接表的实现示例：

#include <iostream>
#include <vector>

using namespace std;

// 邻接表节点结构体
struct AdjListNode {
    int dest;           // 目标顶点
    int weight;         // 边的权重（如果有的话）
    AdjListNode* next;  // 指向下一个邻接点的指针
};

// 邻接表结构体
struct AdjList {
    AdjListNode* head;  // 指向链表的头节点指针
};

// 图结构体
class Graph {
public:
    Graph(int V);                        // 构造函数
    void addEdge(int src, int dest);     // 添加一条边
    void printGraph();                   // 打印邻接表

private:
    int V;                              // 图的顶点数
    vector<AdjList> adjLists;           // 存储邻接表的向量
};

// 构造函数
Graph::Graph(int V) {
    this->V = V;
    adjLists.resize(V);     // 调整邻接表向量的大小为V
    for (int i = 0; i < V; i++) {
        adjLists[i].head = nullptr;   // 初始化每个链表头节点为空指针
    }
}

// 添加一条边
void Graph::addEdge(int src, int dest) {
    AdjListNode* newNode = new AdjListNode;
    newNode->dest = dest;
    newNode->next = adjLists[src].head;
    adjLists[src].head = newNode;
}

// 打印邻接表
void Graph::printGraph() {
    for (int i = 0; i < V; i++) {
        AdjListNode* pCrawl = adjLists[i].head;
        cout << i << " -> ";
        while (pCrawl) {
            cout << pCrawl->dest << " ";
            pCrawl = pCrawl->next;
        }
        cout << endl;
    }
}

// 测试
int main() {
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
    g.printGraph();
    return 0;
}

上述代码实现了一个无向图的邻接表存储，使用了结构体和动态内存分配。在这个实现中，邻接表是通过一个

使用邻接表来存储图，可以将每个顶点的所有邻居节点存储在一个链表中，而每个顶点作为头结点。这种方式比邻接矩阵存储方法节省存储空间，特别是在图稀疏的情况下。在邻接表中，每个节点包含两个信息：一个是顶点的信息，另一个是指向链表中下一个节点的指针。

在C++中，我们可以用结构体和指针来实现邻接表。下面是一个示例：

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

vector<Node*> adj_list;

void addEdge(int u, int v) {
    Node* new_node = new Node(v);
    new_node->next = adj_list[u];
    adj_list[u] = new_node;

    new_node = new Node(u);
    new_node->next = adj_list[v];
    adj_list[v] = new_node;
}

void printGraph(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Vertex " << i << ": ";
        Node* curr = adj_list[i];
        while (curr) {
            cout << curr->val << " ";
            curr = curr->next;
        }
        cout << endl;
    }
}

int main() {
    int n = 5;  // number of vertices
    adj_list.resize(n, nullptr);

    addEdge(0, 1);
    addEdge(0, 4);
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(1, 4);
    addEdge(2, 3);
    addEdge(3, 4);

    printGraph(n);

    return 0;
}

在上面的代码中，我们使用了一个vector<Node*>类型的变量adj_list来存储每个顶点的链表头节点，addEdge函数用于添加边，printGraph函数用于打印图的邻接表。在主函数中，我们首先将adj_list初始化为n个空指针，然后调用addEdge函数添加边，最后调用printGraph函数打印邻接表。