c++根据无向图邻接矩阵生成邻接表

可以按照以下步骤在C++中生成邻接表：

1. 定义邻接表节点结构体

struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

2. 定义邻接表结构体

struct AdjList {
    struct AdjListNode* head;
};

3. 初始化邻接表

struct AdjList* adjListArray = new AdjList[V];
for (int i = 0; i < V; ++i) {
    adjListArray[i].head = NULL;
}

4. 循环遍历邻接矩阵，将非零元素添加到邻接表中

for (int i = 0; i < V; ++i) {
    for (int j = 0; j < V; ++j) {
        if (graph[i][j] != 0) {
            int dest = j;
            struct AdjListNode* newNode = new AdjListNode;
            newNode->dest = dest;
            newNode->next = adjListArray[i].head;
            adjListArray[i].head = newNode;
        }
    }
}

完整代码如下：

#include <iostream>
using namespace std;

struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

struct AdjList {
    struct AdjListNode* head;
};

class Graph {
    private:
        int V;
        struct AdjList* adjListArray;
    public:
        Graph(int V) {
            this->V = V;
            adjListArray = new AdjList[V];
            for (int i = 0; i < V; ++i) {
                adjListArray[i].head = NULL;
            }
        }

        void addEdge(int src, int dest) {
            struct AdjListNode* newNode = new AdjListNode;
            newNode->dest = dest;
            newNode->next = adjListArray[src].head;
            adjListArray[src].head = newNode;
        }

        void printGraph() {
            for (int i = 0; i < V; ++i) {
                struct AdjListNode* ptr = adjListArray[i].head;
                cout << "Adjacency list of vertex " << i << endl;
                while (ptr != NULL) {
                    cout << "-> " << ptr->dest;
                    ptr = ptr->next;
                }
                cout << endl;
            }
        }
};

int main() {
    int V = 5;
    int graph[5][5] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 1, 1},
        {0, 1, 0, 0, 1},
        {1, 1, 0, 0, 1},
        {0, 1, 1, 1, 0}
    };
    Graph g(V);
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (graph[i][j] != 0) {
                g.addEdge(i, j);
            }
        }
    }
    g.printGraph();
    return 0;
}