有向图采用邻接矩阵存储，设计算法，判断其中是否存在回路用c++

在有向图中，使用邻接矩阵存储时，可以利用深度优先搜索（Depth First Search, DFS）或拓扑排序算法来判断是否存在回路。这里提供一种基于DFS的方法：

#include <iostream>
#include <vector>

// 邻接矩阵表示有向图
using namespace std;
vector<vector<int>> adjMatrix;

// 检查节点v是否已经被访问过
bool visited[vertices]; // vertices表示图中的顶点数

// 辅助函数，用于递归查找回路
void dfs(int v) {
    visited[v] = true;
    for (int i = 0; i < vertices; ++i) {
        if (adjMatrix[v][i] && !visited[i]) { // 如果相邻且未访问
            dfs(i); // 递归检查邻居
            if (visited[i]) { // 如果邻居已经访问过（意味着存在回路）
                return; // 回溯并结束当前路径
            }
        }
    }
}

// 主函数，检测图是否有环
bool hasCycle() {
    fill(visited, visited + vertices, false);
    for (int i = 0; i < vertices; ++i) {
        if (!visited[i])
            if (dfs(i)) // 如果找到回路，则返回true
                return true;
    }
    return false; // 没有发现回路，返回false
}

int main() {
    int numVertices, numEdges;
    cout << "请输入顶点数和边数：";
    cin >> numVertices >> numEdges;

    adjMatrix.resize(numVertices, vector<int>(numVertices, 0)); // 初始化邻接矩阵
    // 假设输入的边已转化为从u到v的形式，填充邻接矩阵
    for (int i = 0; i < numEdges; ++i) {
        int u, v;
        cin >> u >> v;
        adjMatrix[u][v] = 1; // 非零表示有边相连
    }

    if (hasCycle())
        cout << "有向图包含回路。\n";
    else
        cout << "有向图不含回路。\n";

    return 0;
}