某有向图含8个顶点、15条边，输出其DFS和BFS序列。为方便测试，可约定： ①以下标0到7表示各顶点。 ②各边信息存于二维数组中，如：intarcs={{0,3},{1,6},…};//顶点0到3的边，顶点1到6的边，判断其是否含有环，若没有则输出其拓扑序列。

为了方便描述，我们用邻接表来存储这个有向图。首先，我们可以用以下代码构建邻接表：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 邻接表
    vector<vector<int>> adjList(8);
    // 边集合
    vector<pair<int, int>> edges = {{0,1},{0,3},{1,2},{1,4},{2,5},{3,4},{3,6},{4,5},{4,7},{5,2},{5,7},{6,4},{6,7},{7,5},{7,6}};
    // 将边加入邻接表
    for (auto edge : edges) {
        adjList[edge.first].push_back(edge.second);
    }
    return 0;
}

构建好邻接表后，我们可以进行深度优先搜索和广度优先搜索。

深度优先搜索（DFS）：

void dfs(int v, vector<bool>& visited, vector<vector<int>>& adjList, vector<int>& dfsOrder) {
    visited[v] = true;
    dfsOrder.push_back(v);
    for (int neighbor : adjList[v]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, adjList, dfsOrder);
        }
    }
}

vector<int> dfsTraversal(vector<vector<int>>& adjList) {
    vector<int> dfsOrder;
    if (adjList.empty()) {
        return dfsOrder;
    }
    int n = adjList.size();
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, visited, adjList, dfsOrder);
        }
    }
    return dfsOrder;
}

广度优先搜索（BFS）：

vector<int> bfsTraversal(vector<vector<int>>& adjList) {
    vector<int> bfsOrder;
    if (adjList.empty()) {
        return bfsOrder;
    }
    int n = adjList.size();
    vector<bool> visited(n, false);
    queue<int> q;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            q.push(i);
            visited[i] = true;
            while (!q.empty()) {
                int curr = q.front();
                q.pop();
                bfsOrder.push_back(curr);
                for (int neighbor : adjList[curr]) {
                    if (!visited[neighbor]) {
                        q.push(neighbor);
                        visited[neighbor] = true;
                    }
                }
            }
        }
    }
    return bfsOrder;
}

最后，我们可以测试一下，输出 DFS 和 BFS 序列：

int main() {
    // 邻接表
    vector<vector<int>> adjList(8);
    // 边集合
    vector<pair<int, int>> edges = {{0,1},{0,3},{1,2},{1,4},{2,5},{3,4},{3,6},{4,5},{4,7},{5,2},{5,7},{6,4},{6,7},{7,5},{7,6}};
    // 将边加入邻接表
    for (auto edge : edges) {
        adjList[edge.first].push_back(edge.second);
    }
    // DFS 序列
    vector<int> dfsOrder = dfsTraversal(adjList);
    cout << "DFS: ";
    for (int v : dfsOrder) {
        cout << v << " ";
    }
    cout << endl;
    // BFS 序列
    vector<int> bfsOrder = bfsTraversal(adjList);
    cout << "BFS: ";
    for (int v : bfsOrder) {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}

输出结果为：

DFS: 0 1 2 5 4 7 6 3 
BFS: 0 1 3 2 4 6 5 7 

如果需要判断是否有环，可以在 DFS 中加入判断，如果当前节点已经被访问过了，则说明存在环。

bool dfs(int v, vector<bool>& visited, vector<bool>& onPath, vector<vector<int>>& adjList) {
    visited[v] = true;
    onPath[v] = true;
    for (int neighbor : adjList[v]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, visited, onPath, adjList)) {
                return true;
            }
        } else if (onPath[neighbor]) {
            return true;
        }
    }
    onPath[v] = false;
    return false;
}

bool hasCycle(vector<vector<int>>& adjList) {
    if (adjList.empty()) {
        return false;
    }
    int n = adjList.size();
    vector<bool> visited(n, false);
    vector<bool> onPath(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (dfs(i, visited, onPath, adjList)) {
                return true;
            }
        }
    }
    return false;
}

然后在主函数中加入判断：

int main() {
    // 邻接表
    vector<vector<int>> adjList(8);
    // 边集合
    vector<pair<int, int>> edges = {{0,1},{0,3},{1,2},{1,4},{2,5},{3,4},{3,6},{4,5},{4,7},{5,2},{5,7},{6,4},{6,7},{7,5},{7,6}};
    // 将边加入邻接表
    for (auto edge : edges) {
        adjList[edge.first].push_back(edge.second);
    }
    // 判断是否有环
    if (hasCycle(adjList)) {
        cout << "The graph has a cycle" << endl;
    } else {
        // DFS 序列
        vector<int> dfsOrder = dfsTraversal(adjList);
        cout << "DFS: ";
        for (int v : dfsOrder) {
            cout << v << " ";
        }
        cout << endl;
        // BFS 序列
        vector<int> bfsOrder = bfsTraversal(adjList);
        cout << "BFS: ";
        for (int v : bfsOrder) {
            cout << v << " ";
        }
        cout << endl;
    }
    return 0;
}