首页 > 编程语言 >C++的算法:欧拉道路与欧拉回路

C++的算法:欧拉道路与欧拉回路

时间:2024-06-09 14:04:14浏览次数:29  
标签:int C++ stk 回路 adj 节点 欧拉

        在图论中,欧拉道路和欧拉回路是两个重要的概念,它们分别描述了在图中找到一条经过所有边且每条边只经过一次的道路或回路的可能性。欧拉道路和欧拉回路在实际应用中有着广泛的用途,如路线规划、电路设计等。

        欧拉道路:通过图中每条边恰好一次且仅一次的行进路线,若存在,则称为欧拉道路。欧拉道路不必是回路,也就是说,起点和终点可以不同。

        欧拉回路:通过图中每条边恰好一次且仅一次的闭回路(或圈、环),若存在,则称为欧拉回路。欧拉回路是欧拉道路的一个特例,它要求起点和终点相同,形成闭环。

        欧拉道路的判定条件:一个连通图存在欧拉道路,当且仅当该图中有且仅有两个奇度顶点(度数为奇数的顶点)。

        欧拉回路的判定条件:一个连通图存在欧拉回路,当且仅当该图中所有顶点的度数均为偶数。

        以下是一个简单的C++程序,用于判断一个给定的图是否存在欧拉道路或欧拉回路,并输出对应的路径(如果存在的话),代码如下。

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

using namespace std;

class Graph {
    int V;    // 顶点数
    vector<int> *adj; // 邻接表

public:
    Graph(int V);  // 构造函数
    void addEdge(int v, int w); // 添加边
    bool hasEulerianPath(); // 是否存在欧拉道路
    bool hasEulerianCycle(); // 是否存在欧拉回路
    void printEulerianPath(); // 打印欧拉道路
    void printEulerianCycle(); // 打印欧拉回路
};

Graph::Graph(int V) {
    this->V = V;
    adj = new vector<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
    adj[w].push_back(v); // 无向图,添加双向边
}

bool Graph::hasEulerianPath() {
    int oddDegreeCount = 0;
    for (int i = 0; i < V; i++) {
        int degree = adj[i].size();
        if (degree % 2 != 0) {
            oddDegreeCount++;
        }
        if (oddDegreeCount > 2) {
            return false; // 超过两个奇度顶点,不存在欧拉道路
        }
    }
    return oddDegreeCount == 0 || oddDegreeCount == 2; // 要么没有奇度顶点(存在欧拉回路),要么有两个奇度顶点(存在欧拉道路)
}

bool Graph::hasEulerianCycle() {
    for (int i = 0; i < V; i++) {
        if (adj[i].size() % 2 != 0) {
            return false; // 存在奇度顶点,不存在欧拉回路
        }
    }
    return true; // 所有顶点度数均为偶数,存在欧拉回路
}

void Graph::printEulerianPath() {
    if (!hasEulerianPath()) {
        cout << "图形没有欧拉路径." << endl;
        return;
    }
    stack<int> stk;
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    // 找到任意一个奇度顶点(如果存在的话)作为起点
    for (int i = 0; i < V; i++) {
        if (adj[i].size() % 2 != 0 && !visited[i]) {
            stk.push(i);
            visited[i] = true;
            break;
        }
    }
    // 如果所有顶点都是偶度顶点,则任意选择一个未访问的顶点作为起点
    if (stk.empty()) {
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                stk.push(i);
                visited[i] = true;
                break;
            }
        }
    }
    // 深度优先搜索,打印欧拉道路
    while (!stk.empty()) {
        int current = stk.top();
        stk.pop();
        cout << current << " ";
        for (int i = adj[current].size() - 1; i >= 0; i--) {
            int next = adj[current][i];
            cout<<"next "<<next<<endl;
            if (!visited[next]) {
                stk.push(next);
                visited[next] = true;
                adj[current].erase(adj[current].begin() + i); // 删除已访问的边
               // adj[next].erase(remove(adj[next].begin(), adj[next].end(), current), adj[next].end()); // 从相邻顶点的邻接表中删除对应的反向边
            }
        }
    }
    delete[] visited;
    cout << endl;
}

void Graph::printEulerianCycle() {
    if (!hasEulerianCycle()) {
        cout << "图没有欧拉循环." << endl;
        return;
    }
    stack<int> stk;
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    // 从任意顶点开始深度优先搜索
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            stk.push(i);
            visited[i] = true;
            break;
        }
    }
    // 深度优先搜索,打印欧拉回路
    while (!stk.empty()) {
        int current = stk.top();
        stk.pop();
        cout << current << " ";
        for (int i = adj[current].size() - 1; i >= 0; i--) {
            int next = adj[current][i];
            if (!visited[next]) {
                stk.push(next);
                visited[next] = true;
                adj[current].erase(adj[current].begin() + i); // 删除已访问的边
                
                //adj[next].erase(remove(adj[next].begin(), adj[next].end(), current), adj[next].end()); // 从相邻顶点的邻接表中删除对应的反向边
            }
        }
    }
    delete[] visited;
    cout << endl;
}

int main() {
    // 创建一个图并添加边
	Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 0);


    // 判断并打印欧拉道路或欧拉回路
    if (g.hasEulerianPath()) {
        cout << "该图具有欧拉路径:" << endl;
        g.printEulerianPath();
    } else if (g.hasEulerianCycle()) {
        cout << "该图具有欧拉循环" << endl;
        g.printEulerianCycle();
    } else {
        cout << "该图没有欧拉路径或循环." << endl;
    }

    return 0;
}

        在上面的代码中,我们定义了一个`Graph`类,该类包含了一个邻接表来表示图的结构。`addEdge`函数用于添加无向边。`hasEulerianPath`和`hasEulerianCycle`函数分别用于判断图中是否存在欧拉道路或欧拉回路。`printEulerianPath`和`printEulerianCycle`函数则用于打印对应的路径或回路。

        在`main`函数中,我们创建了一个图并添加了一些边,然后判断并打印了图中是否存在欧拉道路或欧拉回路。根据欧拉道路和欧拉回路的定义及判定条件,程序会输出相应的结果。

        请注意,上述代码仅为示例,实际应用中可能需要根据具体需求进行调整和优化。同时,为了保证程序的正确性和可读性,建议在实际开发中添加必要的错误检查和边界条件处理。

        欧拉图算法的应用通常涉及到深度优先搜索(DFS)来寻找欧拉路径或欧拉回路。力扣上的“重新安排行程”这道题就是一个很好的应用实例,它要求根据给定的航班信息(表示为起点和终点的对),重新安排一个可能的行程。

        这个算法的思路如下:

        1. 构造邻接表,其中每个节点的邻接节点按字典序排序,以确保DFS的确定性。
        2. 从任意一个非空邻接表的节点开始,使用深度优先搜索遍历整个图。
        3. 回溯时将访问的节点逆序添加到结果中,这样就可以得到一条欧拉路径。

        代码如下。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<string> findItinerary(vector<pair<string, string>>& tickets) {
        // 构建邻接表
        unordered_map<string, vector<string>> graph;
        for (const auto& ticket : tickets) {
            graph[ticket.first].push_back(ticket.second);
        }

        // 对每个节点的邻接表进行排序,保证DFS的确定性
        for (auto& entry : graph) {
            sort(entry.second.begin(), entry.second.end());
        }

        vector<string> result;
        stack<string> s;

        // 找到起始点,即邻接表不为空的第一个节点
        for (const auto& entry : graph) {
            if (!entry.second.empty()) {
                s.push(entry.first);
                break;
            }
        }

        // 深度优先搜索,回溯时添加节点到结果中
        while (!s.empty()) {
            string curr = s.top();
            s.pop();

            // 将当前节点添加到结果中
            result.push_back(curr);

            // 遍历当前节点的所有邻接节点
            vector<string>& neighbors = graph[curr];
            while (!neighbors.empty()) {
                string next = neighbors.back();
                neighbors.pop_back(); // 移除已访问的邻接节点
                s.push(next); // 添加到栈中以便后续搜索
            }
        }

        // 反转结果,因为我们是从后往前添加的
        reverse(result.begin(), result.end());
        return result;
    }
};

int main() {
    Solution solution;
    vector<pair<string, string>> tickets = {
        {"MUC", "LHR"},
        {"JFK", "MUC"},
        {"SFO", "JFK"},
        {"LHR", "SFO"}
    };
    
    vector<string> itinerary = solution.findItinerary(tickets);
    cout << "重建的行程:" << endl;
    for (const string& city : itinerary) {
        cout << city << " ";
    }
    cout << endl;

    return 0;
}

        在这个代码中,我们首先创建了一个`unordered_map<string, vector<string>>`类型的`graph`,用于存储每个机场(节点)及其对应的可达机场列表(邻接表)。我们遍历`tickets`数组,将每个起点和终点对添加到`graph`中。

        接下来,我们对每个节点的邻接表进行排序,这是为了保证在搜索过程中,每次选择的节点顺序是一致的,从而得到确定的欧拉路径。

        我们使用一个栈来进行深度优先搜索。我们从`graph`中找到第一个非空邻接表的节点作为起始点,并将其压入栈中。然后,我们进入一个循环,不断从栈顶取出节点,将其添加到结果数组中,并继续遍历其邻接节点,将它们压入栈中。当栈为空时,说明已经搜索完所有可达的节点。

        最后,我们返回反转后的结果数组,因为我们是逆序添加节点的,所以需要反转以得到正确的行程顺序。

        这段代码可以在满足题目要求的条件下,正确地重新安排行程,并输出结果。

标签:int,C++,stk,回路,adj,节点,欧拉
From: https://blog.csdn.net/winterling/article/details/139561130

相关文章

  • 二维数组2(第2~5题是Goc语言,其余是C++语言)
    第1题    对角线    时限:1s空间:256m输入整数N,输出相应方阵。输入格式一个整数N。(0<n<10)输出格式一个方阵,每个数字的场宽为3。输入/输出例子1输入:5输出: 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 ......
  • C++的近邻算法详解及应用
            近邻算法,也被称为最近邻算法或k-近邻算法(k-NN),是一种基本的分类和回归方法。它基于实例进行学习,无需进行模型训练,而是直接通过计算待分类样本与已知类别样本之间的距离来确定其所属类别。在C++中,我们可以通过编写特定的函数或利用现有的库来实现近邻算法。  ......
  • C++三大特性之多态
    1.多态1.1多态的概念在面向对象方法中一般是这样表述多态性的:向不同的对象发送同一个消息,不同的对象在接收时会产生不同的行为(即方法)也就是说,每个对象可以用自己的方式去响应共同的消息。所谓消息,就是调用函数,不同的行为就是指不同的实现,即执行不同的函数。通俗来说,就是......
  • C++20 新特性: 三向比较运算符
    目录标题功能和用法示例代码如何重载三向比较运算符示例:重载三向比较运算符注意事项结语C++20引入了一种新的比较运算符,称为“三向比较运算符”或“太空船运算符”,其符号为<=>。这个运算符提供了一种简化方式来同时比较两个值的相等性、小于和大于状态。这一特......
  • C++入门7 类|构造函数|析构函数
    一,类型设计和实例化对象封装是面向对象程序设计最基本的特性, 把数据 (属性) 和函数 (操作) 合成一个整体,这在计算机世界中是用类与对象实现的。C++中类的设计1 class 类型名称2 {3 public:4 成员列表1;5 protected:6 成员列表2;7 private:8 成员列表3;......
  • 【机器学习】与【数据挖掘】技术下【C++】驱动的【嵌入式】智能系统优化
    目录一、嵌入式系统简介二、C++在嵌入式系统中的优势三、机器学习在嵌入式系统中的挑战四、C++实现机器学习模型的基本步骤五、实例分析:使用C++在嵌入式系统中实现手写数字识别1.数据准备2.模型训练与压缩3.模型部署六、优化与分析1.模型优化模型量化模型剪枝......
  • 【调整堆】(C++ 代码实现 & 注释详解)
     自定义结构体:#definesz105typedefstructnode{ intlength; intl[sz];}SqList; 调整堆的函数:HeapAdjust函数思路说明://目标:将以s为根的子树调整为大根堆//具体操作:将路径上比s大的都往上移动,s往下移动,直到遇到比s还小的,就“放下”svoidHeapAdjust(SqList......
  • 跨语言系统中的功能通信:Rust、Java、Go和C++的最佳实践
    在现代软件开发中,使用多种编程语言构建复杂系统已成为一种常见的做法。每种编程语言都有其独特的优势和适用场景,这使得在同一个系统中使用多种语言变得合理且高效。然而,这也带来了一个重要的挑战:如何在这些不同语言之间实现高效、可靠的功能通信。本文将探讨Rust、Java、Go和C+......
  • 程序的基本结构、cout语句(c++语言)
    一、如何下载Dev C++    登录网站:ht.51goc.com二、安装DevC++一、启动DevC++   双击桌面的图标 二、新建一个程序三、复制一个程序    请你复制以下代码到“程序编辑区”    #include<bits/stdc++.h>usingn......
  • 【C++】初识C++
    【C++】初识C++文章概括关键字(C++98)命名空间命名空间的定义命名空间的特性输入与输出C++中的输入输出输入输出的命名空间缺省参数函数重载引用引用的概念引用的特性引用地使用场景引用做参数引用做返回值常引用常引用的俩个例子引用与指针的区别内联函数文章概括......