数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序检查无向图是否包含欧拉回路
要了解欧拉回路，我们需要了解欧拉路径。欧拉路径是一条路径，通过它我们可以精确地访问每个节点一次。我们可以多次使用相同的边。欧拉回路是一种特殊的欧拉路径。当欧拉路径的起始顶点也与该路径的结束顶点相连时。
为了检测回路，我们必须遵循以下条件
- 图必须是连通的。
- 现在，当无向图的任何顶点都没有奇数度时，它就是一个欧拉回路。
输入
输出
该图具有欧拉回路。
算法
traverse(u, visited)
输入 起始节点u和已访问节点，以标记已访问的节点。
输出 遍历所有连接的顶点。
Begin mark u as visited for all vertex v, if it is adjacent with u, do if v is not visited, then traverse(v, visited) done End
isConnected(graph)
输入：图。
输出：如果图是连通的，则返回True。
Begin define visited array for all vertices u in the graph, do make all nodes unvisited traverse(u, visited) if any unvisited node is still remaining, then return false done return true End
hasEulerianCircuit(Graph)
输入 给定的图。
输出 当没有欧拉回路时返回0，当存在欧拉回路时返回1。
Begin if isConnected() is false, then return false define list of degree for each node oddDegree := 0 for all vertex i in the graph, do for all vertex j which are connected with i, do increase degree done if degree of vertex i is odd, then increase oddDegree done if oddDegree is 0, then return 1 else return 0 End
示例代码
#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
/*int graph[NODE][NODE] = {{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}};*/ //No Euler circuit, but euler path is present
int graph[NODE][NODE] = {{0, 1, 1, 1, 1},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{1, 0, 0, 1, 0}}; //uncomment to check Euler Circuit as well as path
/*int graph[NODE][NODE] = {{0, 1, 1, 1, 0},
{1, 0, 1, 1, 0},
{1, 1, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 0, 0, 1, 0}};*/ //Uncomment to check Non Eulerian Graph
void traverse(int u, bool visited[]) {
visited[u] = true; //mark v as visited
for(int v = 0; v<NODE; v++) {
if(graph[u][v]) {
if(!visited[v]) traverse(v, visited);
}
}
}
bool isConnected() {
bool *vis = new bool[NODE];
//for all vertex u as start point, check whether all nodes are visible or not
for(int u; u < NODE; u++) {
for(int i = 0; i<NODE; i++)
vis[i] = false; //initialize as no node is visited
traverse(u, vis);
for(int i = 0; i<NODE; i++) {
if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected
return false;
}
}
return true;
}
int hasEulerianCircuit() {
if(isConnected() == false) //when graph is not connected
return 0;
vector<int> degree(NODE, 0);
int oddDegree = 0;
for(int i = 0; i<NODE; i++) {
for(int j = 0; j<NODE; j++) {
if(graph[i][j])
degree[i]++; //increase degree, when connected edge found
}
if(degree[i] % 2 != 0) //when degree of vertices are odd
oddDegree++; //count odd degree vertices
}
if(oddDegree == 0) { //when oddDegree is 0, it is Euler circuit
return 1;
}
return 0;
}
int main() {
if(hasEulerianCircuit()) {
cout << "The graph has Eulerian Circuit." << endl;
} else {
cout << "The graph has No Eulerian Circuit." << endl;
}
}输出
The graph has Eulerian Circuit.
更新于： 2019年7月30日
370 次查看
广告