Python中使用欧拉回路和欧拉通路算法求图(Graph)的欧拉路径

class Graph:

    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for i in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)
        self.adj[v].append(u)

    def DFS(self, v, visited):

        visited[v] = True
        for i in self.adj[v]:
            if not visited[i]:
                self.DFS(i, visited)

    def is_connected(self):

        visited = [False] * self.V
        for i in range(self.V):
            if len(self.adj[i]) > 0:
                break

        self.DFS(i, visited)

        for i in range(self.V):
            if not visited[i] and len(self.adj[i]) > 0:
                return False

        return True

    def degree(self, v):
        degree = 0
        for i in self.adj[v]:
            degree += 1
        return degree

    def is_eulerian(self):

        if not self.is_connected():
            return 0
        odd = 0
        for i in range(self.V):
            if self.degree(i) % 2 != 0:
                odd += 1

        if odd == 0:
            return 2
        elif odd == 2:
            return 1
        else:
            return 0

    def eulerian_path_util(self, u, visited):

        for v in self.adj[u]:
            if not visited[v]:
                visited[v] = True
                self.path.append((u, v))
                self.eulerian_path_util(v, visited)

    def eulerian_path(self):

        result = self.is_eulerian()
        if result == 0:
            print("Graph is not Eulerian")
        elif result == 1:
            print("Graph has Eulerian path:")
            for i in self.adj:
                if self.degree(i) % 2 != 0:
                    u = i
                    break
            visited = [False] * self.V
            self.path = []
            self.eulerian_path_util(u, visited)
            for i in self.path:
                print(str(i[0]) + "-" + str(i[1]), end=" ")
            print()
        else:
            print("Graph has Eulerian cycle:")
            u = 0
            for i in range(self.V):
                if len(self.adj[i]) > 0:
                    u = i
                    break
            visited = [False] * self.V
            self.path = []
            self.eulerian_path_util(u, visited)
            for i in self.path:
                print(str(i[0]) + "-" + str(i[1]), end=" ")
            print()

g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 3)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 4)

g.eulerian_path()

Graph has Eulerian path:
0-1 1-2 2-4 1-3 3-0