自定义有向图，输出欧拉回路

Question

知识和技能
1欧拉图判定 2 fleury算法 3. 应用DFS判割边
任务描述
自定义有向图，输出欧拉回路
软件运行示例
有向图图以邻接矩阵形式存储于文件；判断是否为欧拉图；运用fleury算法求欧拉回路。

Answer 1

以下是一个使用C++实现的示例代码，可以读取邻接矩阵形式存储的有向图文件，并判断是否为欧拉图，然后使用Fleury算法求解欧拉回路：

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

bool isEulerianGraph(vector<vector<int>>& adjMatrix) {
    int n = adjMatrix.size();
    
    // 判断是否为连通图
    vector<bool> visited(n, false);
    dfs(adjMatrix, 0, visited);
    for (bool v : visited) {
        if (!v) {
            return false;
        }
    }
    
    // 判断每个顶点的入度等于出度
    for (int i = 0; i < n; i++) {
        int indegree = 0, outdegree = 0;
        for (int j = 0; j < n; j++) {
            indegree += adjMatrix[j][i];
            outdegree += adjMatrix[i][j];
        }
        if (indegree != outdegree) {
            return false;
        }
    }
    
    return true;
}

void dfs(vector<vector<int>>& adjMatrix, int vertex, vector<bool>& visited) {
    visited[vertex] = true;
    int n = adjMatrix.size();
    for (int i = 0; i < n; i++) {
        if (adjMatrix[vertex][i] == 1 && !visited[i]) {
            dfs(adjMatrix, i, visited);
        }
    }
}

void fleuryAlgorithm(vector<vector<int>>& adjMatrix, vector<int>& circuit) {
    if (!isEulerianGraph(adjMatrix)) {
        circuit.clear();
        return;
    }
    
    int n = adjMatrix.size();
    vector<int> stack;
    int currentVertex = 0;
    
    while (true) {
        circuit.push_back(currentVertex);
        
        // 寻找下一个可行的边
        for (int nextVertex = 0; nextVertex < n; nextVertex++) {
            if (adjMatrix[currentVertex][nextVertex] == 1) {
                stack.push_back(currentVertex);
                removeEdge(adjMatrix, currentVertex, nextVertex);
                currentVertex = nextVertex;
                break;
            }
        }
        
        if (stack.empty()) {
            break;
        }
        
        // 如果没有可行的边，则回溯
        if (currentVertex == stack.back()) {
            currentVertex = stack.back();
            stack.pop_back();
        }
    }
}

void removeEdge(vector<vector<int>>& adjMatrix, int vertex1, int vertex2) {
    adjMatrix[vertex1][vertex2] = 0;
}

int main() {
    // 读取邻接矩阵形式存储的有向图文件
    ifstream file("graph.txt");
    int n;
    file >> n;
    vector<vector<int>> adjMatrix(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            file >> adjMatrix[i][j];
        }
    }
    file.close();
    
    // 判断是否为欧拉图
    if (isEulerianGraph(adjMatrix)) {
        cout << "该图是欧拉图" << endl;
    } else {
        cout << "该图不是欧拉图" << endl;
    }
    
    // 使用Fleury算法求解欧拉回路
    vector<int> circuit;
    fleuryAlgorithm(adjMatrix, circuit);
    
    // 输出欧拉回路
    cout << "欧拉回路: ";
    for (int vertex : circuit) {
        cout << vertex << " ";
    }
    cout << endl;
    
    return 0;
}

请注意，上述代码假设邻接矩阵存储的有向图文件是一个文本文件，文件名为"graph.txt"。文件的第一行是图的顶点数，接下来的n行是邻接矩阵的内容。需要根据实际情况修改文件名和文件格式。