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。但是，通过使用一些优化算法，如剪枝等技巧，可以降低时间复杂度。

相关问题

c语言基于邻接矩阵判断图中是否有回路的函数

基于邻接矩阵判断图中是否有回路，可以使用深度优先搜索算法。下面是一个基于邻接矩阵的C语言函数实现：

#define MAX_VERTEX_NUM 100 // 图的最大顶点数
typedef int VertexType; // 顶点类型
typedef int EdgeType; // 边权类型
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组
    EdgeType edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int n, e; // 顶点数和边数
} MGraph;

int visited[MAX_VERTEX_NUM]; // 访问标记数组

// DFS遍历图
int DFS(MGraph *G, int v, int parent) {
    visited[v] = 1; // 标记当前节点为已访问
    int i;
    for (i = 0; i < G->n; i++) {
        if (G->edges[v][i] != 0) { // 如果当前节点与节点i之间有边
            if (!visited[i]) { // 如果节点i未被访问过
                if (DFS(G, i, v)) // 递归遍历节点i
                    return 1; // 如果返回真，则说明存在回路
            } else if (i != parent) { // 如果节点i已被访问过且不是当前节点的父节点
                return 1; // 说明存在回路
            }
        }
    }
    return 0; // 没有找到回路
}

// 判断无向图是否有回路
int HasCycle(MGraph *G) {
    int i;
    for (i = 0; i < G->n; i++)
        visited[i] = 0; // 初始化访问标记数组
    for (i = 0; i < G->n; i++) {
        if (!visited[i]) // 如果节点i未被访问过
            if (DFS(G, i, -1)) // 从节点i开始遍历
                return 1; // 如果返回真，则说明存在回路
    }
    return 0; // 不存在回路
}

其中，`DFS`函数用于深度优先遍历图，判断是否存在回路，`HasCycle`函数用于判断无向图是否有回路。函数中使用`visited`数组记录每个节点的访问状态，`parent`参数表示当前节点的父节点，用于判断是否存在回路。

c++ 求邻接矩阵的无向图

以下是C++代码，用于求邻接矩阵的无向图：

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "请输入顶点个数：";
    cin >> n;

    int graph[n][n]; // 定义邻接矩阵

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }

    // 输入无向边
    int u, v;
    cout << "请输入无向边（以-1 -1结束）：" << endl;
    while (true) {
        cin >> u >> v;
        if (u == -1 && v == -1) {
            break;
        }
        graph[u][v] = graph[v][u] = 1;
    }

    // 输出邻接矩阵
    cout << "邻接矩阵为：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << graph[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

该程序首先要求用户输入顶点个数，然后定义一个二维数组作为邻接矩阵，并初始化为0。接着，程序要求用户输入每条无向边，将邻接矩阵中对应的位置修改为1。最后，程序输出邻接矩阵。