编写c++程序，判断一个用邻接表存储的有向图是否存在回路，并写出算法思想。

我建议使用深度优先搜索（DFS）来解决这个问题。算法思想是，从一个节点出发，沿着邻接表搜索它的邻居，如果发现搜索到了之前访问过的点，则表明存在回路；如果搜索完所有邻居，都没有发现回路，则说明图中不存在回路。

相关问题

假设一个有向图采用邻接表G存储。设计一个算法采用拓扑排序判断其中是否有回路。写出c++代码

在邻接表表示的有向图中，我们可以使用拓扑排序算法（如Kahn's Algorithm）来检测是否存在环。如果存在环，则不可能对所有顶点进行排序，因为环阻止了从某个顶点到其他顶点的唯一路径。

以下是使用C++实现的基本步骤：

1. 首先，我们需要创建一个邻接表表示图，同时维护每个顶点的入度（表示指向它的边的数量）。
2. 创建一个队列，并将入度为0的所有顶点加入队列。
3. 然后，我们开始遍历队列。对于每个顶点，如果发现有出度大于0的未访问顶点，则说明存在环。
4. 没有顶点可添加到队列意味着图是可达的，可以尝试进行拓扑排序。如果在这个过程中能够成功地对所有顶点排序，那么图中不存在环。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 用于表示图结构
struct Edge {
    int src, dest;
};

vector<vector<int>> adjList; // 邻接表

bool hasCycleUtil(int node, vector<bool>& visited, vector<int>& inDegree) {
    // Mark the current node as visited and increment its in-degree count
    visited[node] = true;
    inDegree[node]++;

    // For all the vertices adjacent to this vertex
    for (int i : adjList[node]) {
        // If vertex is not visited, recursively check if it has a cycle
        if (!visited[i])
            if (hasCycleUtil(i, visited, inDegree))
                return true;

        // If vertex is already visited and has an incoming edge, there must be a cycle
        else if (inDegree[i] > 0)
            return true;
    }

    // Decrement the in-degree count after visiting a node, if no cycle found
    inDegree[node]--;
    return false;
}

// 主函数，检查是否存在环并返回结果
bool hasCycle() {
    int numVertices = adjList.size();
    vector<bool> visited(numVertices, false);
    vector<int> inDegree(numVertices, 0);

    // Try to visit all nodes with zero in-degree first
    queue<int> q;
    for (int i = 0; i < numVertices; ++i) {
        if (!visited[i] && inDegree[i] == 0)
            q.push(i);
    }

    while (!q.empty()) {
        int node = q.front(); q.pop();
        if (hasCycleUtil(node, visited, inDegree))
            return true;
    }

    return false; // No cycle detected
}

int main() {
    // 初始化邻接列表...
    // ...

    bool hasLoop = hasCycle();
    if (hasLoop)
        cout << "Graph contains a cycle.\n";
    else
        cout << "Graph does not contain a cycle.\n";

    return 0;
}

假设一个无向图采用邻接表G作为存储结构，设计一个算法在存在经过顶点v的回路时输出所有这样的简单回路。写出c++代码

为了找到所有包含指定顶点v的简单回路，你可以使用深度优先搜索（DFS）算法，并记录下路径上已经访问过的节点。当发现回路时，停止搜索并反向回溯找出所有的简单路径。以下是C++代码实现：

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>

using namespace std;

// 辅助函数用于检查是否在路径上
bool inPath(vector<int>& path, int u) {
    return find(path.begin(), path.end(), u) != path.end();
}

void dfs(int u, int v, vector<int>& path, vector<vector<int>>& G, unordered_set<int>& visited, vector<vector<int>>& result) {
    path.push_back(u);
    visited.insert(u);

    if (u == v && !inPath(result.back(), u)) { // 如果找到简单回路
        result.push_back(path);
        return;
    }

    for (int neighbor : G[u]) {
        if (!visited.count(neighbor)) {
            dfs(neighbor, v, path, G, visited, result);
        } else if (neighbor != v && inPath(path, neighbor)) { // 如果邻居已经在路径上并且不是目标v，说明有交叉回路，跳过
            continue;
        }
    }

    path.pop_back(); // 出栈当前节点，继续探索下一个未访问的节点
}

// 主函数
void findAllSimplePathsThroughV(const vector<vector<int>>& G, int v, vector<vector<int>>& result) {
    unordered_set<int> visited;
    dfs(v, v, {}, G, visited, result); // 首先从v开始搜索
}

int main() {
    vector<vector<int>> G = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1}}; // 示例无向图
    int v = 2; // 指定顶点

    vector<vector<int>> paths;
    findAllSimplePathsThroughV(G, v, paths);

    if (paths.empty()) {
        cout << "No simple cycles found through vertex " << v << endl;
    } else {
        cout << "Simple cycles through vertex " << v << ": " << endl;
        for (const auto& path : paths) {
            cout << "[ ";
            for (int node : path) {
                cout << node << " ";
            }
            cout << "]" << endl;
        }
    }

    return 0;
}

这个代码会输出所有通过顶点v的简单回路，如果没有，则会告知没有简单回路。注意，这个解决方案只适用于寻找简单回路，如果允许复杂的环形结构，结果将包含更长的回路。