# 算法设计：计算无向图的欧拉路径和回路？

2021年3月25日12:01:50 发表评论 1,578 次浏览

## 本文概述

….a)所有非零度的顶点都已连接。我们不在乎零度的顶点, 因为它们不属于欧拉循环或路径(我们仅考虑所有边)。

….b)所有顶点都具有偶数度。

….a)与欧拉循环的条件(a)相同

….b)如果零个或两个顶点具有奇数度, 而所有其他顶点具有偶数度。请注意, 在无向图中, 只有一个具有奇数度的顶点是不可能的(在无向图中, 所有度的总和始终是偶数)

## C ++

``````// A C++ program to check if a given graph is Eulerian or not
#include<iostream>
#include <list>
using namespace std;

// A class that represents an undirected graph
class Graph
{
int V;    // No. of vertices
public :
// Constructor and destructor
Graph( int V)   { this ->V = V; adj = new list< int >[V]; }
~Graph() { delete [] adj; } // To avoid memory leak

// function to add an edge to graph
void addEdge( int v, int w);

// Method to check if this graph is Eulerian or not
int isEulerian();

// Method to check if all non-zero degree vertices are connected
bool isConnected();

// Function to do DFS starting from v. Used in isConnected();
void DFSUtil( int v, bool visited[]);
};

void Graph::addEdge( int v, int w)
{
adj[w].push_back(v);  // Note: the graph is undirected
}

void Graph::DFSUtil( int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true ;

// Recur for all the vertices adjacent to this vertex
list< int >::iterator i;
if (!visited[*i])
DFSUtil(*i, visited);
}

// Method to check if all non-zero degree vertices are connected.
// It mainly does DFS traversal starting from
bool Graph::isConnected()
{
// Mark all the vertices as not visited
bool visited[V];
int i;
for (i = 0; i < V; i++)
visited[i] = false ;

// Find a vertex with non-zero degree
for (i = 0; i < V; i++)
break ;

// If there are no edges in the graph, return true
if (i == V)
return true ;

// Start DFS traversal from a vertex with non-zero degree
DFSUtil(i, visited);

// Check if all non-zero degree vertices are visited
for (i = 0; i < V; i++)
if (visited[i] == false && adj[i].size() > 0)
return false ;

return true ;
}

/* The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian)  */
int Graph::isEulerian()
{
// Check if all non-zero degree vertices are connected
if (isConnected() == false )
return 0;

// Count vertices with odd degree
int odd = 0;
for ( int i = 0; i < V; i++)
odd++;

// If count is more than 2, then graph is not Eulerian
if (odd > 2)
return 0;

// If odd count is 2, then semi-eulerian.
// If odd count is 0, then eulerian
// Note that odd count can never be 1 for undirected graph
return (odd)? 1 : 2;
}

// Function to run test cases
void test(Graph &g)
{
int res = g.isEulerian();
if (res == 0)
cout << "graph is not Eulerian\n" ;
else if (res == 1)
cout << "graph has a Euler path\n" ;
else
cout << "graph has a Euler cycle\n" ;
}

// Driver program to test above function
int main()
{
// Let us create and test graphs shown in above figures
Graph g1(5);
test(g1);

Graph g2(5);
test(g2);

Graph g3(5);
test(g3);

// Let us create a graph with 3 vertices
// connected in the form of cycle
Graph g4(3);
test(g4);

// Let us create a graph with all veritces
// with zero degree
Graph g5(3);
test(g5);

return 0;
}``````

## Java

``````// A Java program to check if a given graph is Eulerian or not
import java.io.*;
import java.util.*;

// This class represents an undirected graph using adjacency list
// representation
class Graph
{
private int V;   // No. of vertices

// Array  of lists for Adjacency List Representation

// Constructor
Graph( int v)
{
V = v;
for ( int i= 0 ; i<v; ++i)
}

//Function to add an edge into the graph
void addEdge( int v, int w)
{
}

// A function used by DFS
void DFSUtil( int v, boolean visited[])
{
// Mark the current node as visited
visited[v] = true ;

// Recur for all the vertices adjacent to this vertex
while (i.hasNext())
{
int n = i.next();
if (!visited[n])
DFSUtil(n, visited);
}
}

// Method to check if all non-zero degree vertices are
// connected. It mainly does DFS traversal starting from
boolean isConnected()
{
// Mark all the vertices as not visited
boolean visited[] = new boolean [V];
int i;
for (i = 0 ; i < V; i++)
visited[i] = false ;

// Find a vertex with non-zero degree
for (i = 0 ; i < V; i++)
break ;

// If there are no edges in the graph, return true
if (i == V)
return true ;

// Start DFS traversal from a vertex with non-zero degree
DFSUtil(i, visited);

// Check if all non-zero degree vertices are visited
for (i = 0 ; i < V; i++)
if (visited[i] == false && adj[i].size() > 0 )
return false ;

return true ;
}

/* The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian)  */
int isEulerian()
{
// Check if all non-zero degree vertices are connected
if (isConnected() == false )
return 0 ;

// Count vertices with odd degree
int odd = 0 ;
for ( int i = 0 ; i < V; i++)
if (adj[i].size()% 2 != 0 )
odd++;

// If count is more than 2, then graph is not Eulerian
if (odd > 2 )
return 0 ;

// If odd count is 2, then semi-eulerian.
// If odd count is 0, then eulerian
// Note that odd count can never be 1 for undirected graph
return (odd== 2 )? 1 : 2 ;
}

// Function to run test cases
void test()
{
int res = isEulerian();
if (res == 0 )
System.out.println( "graph is not Eulerian" );
else if (res == 1 )
System.out.println( "graph has a Euler path" );
else
System.out.println( "graph has a Euler cycle" );
}

// Driver method
public static void main(String args[])
{
// Let us create and test graphs shown in above figures
Graph g1 = new Graph( 5 );
g1.test();

Graph g2 = new Graph( 5 );
g2.test();

Graph g3 = new Graph( 5 );
g3.test();

// Let us create a graph with 3 vertices
// connected in the form of cycle
Graph g4 = new Graph( 3 );
g4.test();

// Let us create a graph with all veritces
// with zero degree
Graph g5 = new Graph( 3 );
g5.test();
}
}
// This code is contributed by Aakash Hasija``````

## python

``````# Python program to check if a given graph is Eulerian or not
#Complexity : O(V+E)

from collections import defaultdict

#This class represents a undirected graph using adjacency list representation
class Graph:

def __init__( self , vertices):
self .V = vertices #No. of vertices
self .graph = defaultdict( list ) # default dictionary to store graph

# function to add an edge to graph
def addEdge( self , u, v):
self .graph[u].append(v)
self .graph[v].append(u)

#A function used by isConnected
def DFSUtil( self , v, visited):
# Mark the current node as visited
visited[v] = True

#Recur for all the vertices adjacent to this vertex
for i in self .graph[v]:
if visited[i] = = False :
self .DFSUtil(i, visited)

'''Method to check if all non-zero degree vertices are
connected. It mainly does DFS traversal starting from
node with non-zero degree'''
def isConnected( self ):

# Mark all the vertices as not visited
visited = [ False ] * ( self .V)

#  Find a vertex with non-zero degree
for i in range ( self .V):
if len ( self .graph[i]) > 1 :
break

# If there are no edges in the graph, return true
if i = = self .V - 1 :
return True

# Start DFS traversal from a vertex with non-zero degree
self .DFSUtil(i, visited)

# Check if all non-zero degree vertices are visited
for i in range ( self .V):
if visited[i] = = False and len ( self .graph[i]) > 0 :
return False

return True

'''The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian)  '''
def isEulerian( self ):
# Check if all non-zero degree vertices are connected
if self .isConnected() = = False :
return 0
else :
#Count vertices with odd degree
odd = 0
for i in range ( self .V):
if len ( self .graph[i]) % 2 ! = 0 :
odd + = 1

'''If odd count is 2, then semi-eulerian.
If odd count is 0, then eulerian
If count is more than 2, then graph is not Eulerian
Note that odd count can never be 1 for undirected graph'''
if odd = = 0 :
return 2
elif odd = = 2 :
return 1
elif odd > 2 :
return 0

# Function to run test cases
def test( self ):
res = self .isEulerian()
if res = = 0 :
print "graph is not Eulerian"
elif res = = 1 :
print "graph has a Euler path"
else :
print "graph has a Euler cycle"

#Let us create and test graphs shown in above figures
g1 = Graph( 5 );
g1.test()

g2 = Graph( 5 )
g2.test();

g3 = Graph( 5 )
g3.test()

#Let us create a graph with 3 vertices
# connected in the form of cycle
g4 = Graph( 3 )
g4.test()

# Let us create a graph with all veritces
# with zero degree
g5 = Graph( 3 )
g5.test()

#This code is contributed by Neelam Yadav``````

## C#

``````// A C# program to check if a given graph is Eulerian or not
using System;
using System.Collections.Generic;

// This class represents an undirected graph using adjacency list
// representation
public class Graph
{
private int V;   // No. of vertices

// Array  of lists for Adjacency List Representation

// Constructor
Graph( int v)
{
V = v;
adj = new List< int >[v];
for ( int i=0; i<v; ++i)
adj[i] = new List< int >();
}

//Function to add an edge into the graph
void addEdge( int v, int w)
{
}

// A function used by DFS
void DFSUtil( int v, bool []visited)
{
// Mark the current node as visited
visited[v] = true ;

// Recur for all the vertices adjacent to this vertex
foreach ( int i in adj[v]){
int n = i;
if (!visited[n])
DFSUtil(n, visited);
}
}

// Method to check if all non-zero degree vertices are
// connected. It mainly does DFS traversal starting from
bool isConnected()
{
// Mark all the vertices as not visited
bool []visited = new bool [V];
int i;
for (i = 0; i < V; i++)
visited[i] = false ;

// Find a vertex with non-zero degree
for (i = 0; i < V; i++)
break ;

// If there are no edges in the graph, return true
if (i == V)
return true ;

// Start DFS traversal from a vertex with non-zero degree
DFSUtil(i, visited);

// Check if all non-zero degree vertices are visited
for (i = 0; i < V; i++)
if (visited[i] == false && adj[i].Count > 0)
return false ;

return true ;
}

/* The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian)  */
int isEulerian()
{
// Check if all non-zero degree vertices are connected
if (isConnected() == false )
return 0;

// Count vertices with odd degree
int odd = 0;
for ( int i = 0; i < V; i++)
odd++;

// If count is more than 2, then graph is not Eulerian
if (odd > 2)
return 0;

// If odd count is 2, then semi-eulerian.
// If odd count is 0, then eulerian
// Note that odd count can never be 1 for undirected graph
return (odd==2)? 1 : 2;
}

// Function to run test cases
void test()
{
int res = isEulerian();
if (res == 0)
Console.WriteLine( "graph is not Eulerian" );
else if (res == 1)
Console.WriteLine( "graph has a Euler path" );
else
Console.WriteLine( "graph has a Euler cycle" );
}

// Driver method
public static void Main(String []args)
{
// Let us create and test graphs shown in above figures
Graph g1 = new Graph(5);
g1.test();

Graph g2 = new Graph(5);
g2.test();

Graph g3 = new Graph(5);
g3.test();

// Let us create a graph with 3 vertices
// connected in the form of cycle
Graph g4 = new Graph(3);
g4.test();

// Let us create a graph with all veritces
// with zero degree
Graph g5 = new Graph(3);
g5.test();
}
}

// This code contributed by PrinciRaj1992``````

``````graph has a Euler path
graph has a Euler cycle
graph is not Eulerian
graph has a Euler cycle
graph has a Euler cycle``````

Fleury的算法可以打印欧拉路径或电路？

http://en.wikipedia.org/wiki/Eulerian_path