c++给出邻接矩阵编写一个算法判断是否为无向图

可以使用如下的伪代码实现：

bool isUndirectedGraph(int** matrix, int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (matrix[i][j] != matrix[j][i]) {
                // 如果矩阵沿对角线对称位置的元素不相等，则不是无向图
                return false;
            }
        }
    }
    return true;
}

其中，`matrix` 是邻接矩阵，`n` 是矩阵的大小（假设矩阵是一个正方形），返回值为布尔类型。

如果矩阵沿对角线对称位置的元素相等，则是无向图，否则不是。

相关问题

用c++编写程序设计一个算法将无向图的邻接矩阵转为对应邻接表的算法

当然可以！以下是一个用C++编写的算法，可以将无向图的邻接矩阵转换为对应的邻接表：

#include <iostream>
#include <vector>

using namespace std;

// 定义无向图类
class Graph {
private:
    int numVertices; // 图中顶点的数量
    vector<vector<int>> adjMatrix; // 邻接矩阵

public:
    // 构造函数
    Graph(int n) {
        numVertices = n;
        // 初始化邻接矩阵
        adjMatrix.resize(numVertices, vector<int>(numVertices, 0));
    }

    // 添加边
    void addEdge(int src, int dest) {
        adjMatrix[src][dest] = 1;
        adjMatrix[dest][src] = 1;
    }

    // 将邻接矩阵转换为邻接表
    vector<vector<int>> convertToAdjList() {
        vector<vector<int>> adjList(numVertices);

        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                if (adjMatrix[i][j] == 1) {
                    adjList[i].push_back(j);
                }
            }
        }

        return adjList;
    }
};

int main() {
    int numVertices, numEdges;
    cout << "Enter the number of vertices: ";
    cin >> numVertices;
    cout << "Enter the number of edges: ";
    cin >> numEdges;

    Graph graph(numVertices);

    cout << "Enter the edges (source destination):\n";
    for (int i = 0; i < numEdges; i++) {
        int src, dest;
        cin >> src >> dest;
        graph.addEdge(src, dest);
    }

    vector<vector<int>> adjList = graph.convertToAdjList();

    cout << "Adjacency List:\n";
    for (int i = 0; i < adjList.size(); i++) {
        cout << i << " -> ";
        for (int j = 0; j < adjList[i].size(); j++) {
            cout << adjList[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

这个程序首先创建一个Graph类，它包含一个邻接矩阵和一些函数来添加边和转换为邻接表。在main函数中，我们首先输入图的顶点数量和边数量，然后输入每条边的起点和终点。最后，调用convertToAdjList函数将邻接矩阵转换为邻接表，并打印出来。

希望能帮到你！如有任何疑问，请随时提问。

c++用邻接矩阵判断有向图是否存在回路

使用邻接矩阵来判断有向图是否存在回路的方法如下：

1. 首先，创建一个大小为n×n的邻接矩阵，其中n表示图的顶点数量。初始时，所有矩阵元素值设为0。

2. 将有向图的边按照起始顶点和终止顶点的关系填入邻接矩阵中。如果存在从顶点i到顶点j的边，则将矩阵元素M[i][j]设为1。

3. 对于每个顶点v，从它的下一个顶点w开始进行深度优先搜索（DFS）。如果w已被访问过且不为v，则表示存在回路。若没有回路，则进行下一步。

4. 对于每个顶点v，如果DFS中搜索到它自身，则表示存在回路。若没有回路，则进行下一步。

5. 如果上述两步都没有找到回路，则判断无向图存在回路。若存在回路，则返回"有回路"，否则返回"无回路"。

通过邻接矩阵判断有向图是否存在回路的时间复杂度为O(n^2)，其中n表示图的顶点数量。因为需要遍历邻接矩阵的所有元素，并进行DFS。但是，通过使用一些优化算法，如剪枝等技巧，可以降低时间复杂度。