欧拉路径是一条路径,通过它我们可以一次访问每个边缘。我们可以多次使用相同的顶点。欧拉电路是欧拉路径的一种特殊类型。当欧拉路径的起始顶点也与该路径的终止顶点相连时,则称为欧拉电路。
要检测路径和电路,我们必须遵循以下条件-
该图必须已连接。
当恰好两个顶点具有奇数度时,它就是一条欧拉路径。
现在,当无向图的所有顶点都没有奇数度时,那就是欧拉回路。
Input: Adjacency matrix of a graph. 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 Output: 该图具有欧拉路径。
遍历(u,已访问)
输入: 起始节点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(图)
输入-图形。
输出-如果已连接图形,则为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
isEulerian(图)
输入-给定的图。
输出-如果不是欧拉则返回0,如果具有欧拉路径则返回1,如果找到欧拉回路则返回2
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 dooDegree done if oddDegree > 2, then return 0 if oddDegree = 0, then return 2 else return 1 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} }; /* 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 /* 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]; //对于所有顶点u作为起点,检查所有节点是否可见 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 isEulerian() { 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 > 2) //when vertices with odd degree greater than 2 return 0; return (oddDegree)?1:2; //when oddDegree is 0, it is Euler circuit, and when 2, it is Euler path } int main() { int check; check = isEulerian(); switch(check) { case 0: cout << "该图不是欧拉图。"; break; case 1: cout << "该图具有欧拉路径。"; break; case 2: cout << "该图具有欧拉回路。"; break; } }
输出结果
该图具有欧拉路径。