c++无向图邻接矩阵

在C++中，无向图（Undirected Graph）可以通过邻接矩阵（Adjacency Matrix）来表示。邻接矩阵是一个二维数组，其中的每个元素表示两个顶点之间是否存在边。如果顶点i和顶点j之间有边，矩阵中的[i][j]或[j][i]（因为无向图是双向的）会有一个非零值，通常是1或其他非零标识；如果没有边，则对应位置的值为0。

邻接矩阵的主要优点是空间效率较高，适用于稠密图（边的数量接近于顶点数量的平方），查询任意两个顶点间是否有边的时间复杂度是O(1)。然而，对于稀疏图（边的数量远小于顶点数量的平方），邻接矩阵可能会浪费大量空间，因为大部分元素都是0。

邻接矩阵的实现步骤如下：

1. 定义一个二维数组，其大小为顶点数的平方，用于存储边的信息。
2. 初始化数组，例如使用整型数组并初始化为0，表示初始时没有边。
3. 当添加边时，更新对应位置的值。如果是无向图，需要同时更新[i][j]和[j][i]。
4. 查询边的存在时，只需检查[i][j]或[j][i]是否非零。

相关问题

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

c++设计算法将无向图邻接矩阵转换为邻接表，将邻接表转换为邻接矩阵

将无向图的邻接矩阵转换为邻接表，可以遍历整个矩阵，对于每个非零元素，将其所在的行和列分别对应到邻接表中的一个顶点，然后在这两个顶点的邻接表中分别添加对方作为相邻节点的边。具体实现代码如下：

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> matrixToAdjList(vector<vector<int>> matrix) {
    int n = matrix.size();
    vector<vector<int>> adjList(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (matrix[i][j] != 0) {
                adjList[i].push_back(j);
                adjList[j].push_back(i);
            }
        }
    }
    return adjList;
}

将邻接表转换为邻接矩阵，可以先遍历邻接表中的所有顶点，对于每个顶点，遍历其邻接表中的节点，将其对应的邻接矩阵位置设为1。具体实现代码如下：

vector<vector<int>> adjListToMatrix(vector<vector<int>> adjList) {
    int n = adjList.size();
    vector<vector<int>> matrix(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j : adjList[i]) {
            matrix[i][j] = 1;
            matrix[j][i] = 1;
        }
    }
    return matrix;
}

以上是将无向图的邻接矩阵转换为邻接表，以及将邻接表转换为邻接矩阵的具体实现代码，您可以根据实际情况进行调整。