无向图的邻接矩阵和邻接表

邻接矩阵和邻接表是表示无向图的两种方式。邻接矩阵是一个二维数组，其中的行和列分别表示图中的节点，而数组中的元素表示这两个节点之间是否有边相连。如果有边相连，则该元素的值为1，否则为0。邻接表是一种链表的形式，表示图中每个节点的邻居节点。每个节点都有一个相关链表，链表中的节点表示该节点所连接的邻居节点。邻接表通常可以更有效地表示稀疏图。

相关问题

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;
}

无向图的邻接矩阵转化为邻接表

将无向图的邻接矩阵转化为邻接表，可以按照以下步骤进行：

1. 创建一个包含n个空链表的列表，其中n为图中的顶点数。

2. 对于邻接矩阵中每一个非零元素a[i][j]，将顶点i和j之间的边加入到i对应的链表中，并将边的另一个端点j也加入到i对应的链表中。

3. 因为是无向图，所以对于邻接矩阵中的每一个非零元素a[i][j]，还需要将顶点j和i之间的边加入到j对应的链表中，并将边的另一个端点i也加入到j对应的链表中。

4. 最终得到的列表就是该无向图的邻接表表示。

下面是一个Python示例代码：

def adj_matrix_to_adj_list(adj_matrix):
    n = len(adj_matrix)
    adj_list = [[] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if adj_matrix[i][j] != 0:
                adj_list[i].append(j)
                adj_list[i].append(adj_matrix[i][j])
                adj_list[j].append(i)
                adj_list[j].append(adj_matrix[i][j])
    return adj_list

其中，adj_matrix是一个n*n的邻接矩阵，adj_list是转化后的邻接表。