Python中图(Graph)的欧拉回路与哈密顿回路算法

在Python中，可以使用图(Graph)数据结构来表示和操作图。图是由一组节点和连接这些节点的边构成，并可以用于解决各种问题，如路径规划、网络分析等。图算法主要包括欧拉回路和哈密顿回路算法，用于找到图中的特定类型的路径。

1. 欧拉回路算法：

欧拉回路是指通过图中的每条边且只经过一次的闭合路径。欧拉回路算法可以用于判断一个图是否存在欧拉回路，以及找到其中的欧拉回路路径。

下面是一个使用Python实现欧拉回路算法的例子：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
    
    def add_edge(self, u, v):
        self.graph[u][v] = 1
        self.graph[v][u] = 1
    
    def dfs(self, v, visited):
        visited[v] = True
        for i in range(self.V):
            if self.graph[v][i] == 1 and not visited[i]:
                self.dfs(i, visited)
    
    def is_eulerian(self):
        visited = [False] * self.V
        
        # Find the first non-zero degree vertex
        for v in range(self.V):
            if sum(self.graph[v]) > 0:
                break
        
        # If no edges in the graph
        if v == self.V - 1:
            return True
        
        # Check if all non-zero degree vertices are connected
        self.dfs(v, visited)
        for i in range(self.V):
            if not visited[i] and sum(self.graph[i]) > 0:
                return False
        
        return True

使用例子：

# Create a graph
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.add_edge(3, 4)
g.add_edge(4, 0)

# Check if the graph has eulerian path
if g.is_eulerian():
    print("Graph has Eulerian cycle")
else:
    print("Graph doesn't have Eulerian cycle")

上面的例子中，创建了一个有5个节点的图，并添加了一些边。然后使用is_eulerian方法判断图中是否存在欧拉回路。如果存在，则打印"Graph has Eulerian cycle"，否则打印"Graph doesn't have Eulerian cycle"。

2. 哈密顿回路算法：

哈密顿回路是指通过图中的每个顶点且只经过一次的闭合路径。哈密顿回路算法可以用于判断一个图是否存在哈密顿回路，以及找到其中的哈密顿回路路径。

下面是一个使用Python实现哈密顿回路算法的例子：

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
    
    def add_edge(self, u, v):
        self.graph[u][v] = 1
        self.graph[v][u] = 1
    
    def hamiltonian_util(self, path, visited, pos):
        if pos == self.V:
            return True
        
        for v in range(self.V):
            if self.graph[path[pos-1]][v] == 1 and not visited[v]:
                path[pos] = v
                visited[v] = True
                
                if self.hamiltonian_util(path, visited, pos + 1):
                    return True
                
                path[pos] = -1
                visited[v] = False
        
        return False
    
    def hamiltonian_cycle(self):
        path = [-1] * self.V
        visited = [False] * self.V
        
        # Start from the first vertex
        path[0] = 0
        visited[0] = True
        
        if self.hamiltonian_util(path, visited, 1):
            print("Hamiltonian cycle exists")
            print("Path:", path)
        else:
            print("Hamiltonian cycle doesn't exist")

使用例子：

# Create a graph
g = Graph(5)
g.add_edge(0, 1)
g.add_edge(0, 3)
g.add_edge(1, 2)
g.add_edge(1, 4)
g.add_edge(2, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)

# Find Hamiltonian cycle in the graph
g.hamiltonian_cycle()

上面的例子中，创建了一个有5个节点的图，并添加了一些边。然后使用hamiltonian_cycle方法找到图中的哈密顿回路。如果存在哈密顿回路，则打印"Hamiltonian cycle exists"和找到的回路路径；否则打印"Hamiltonian cycle doesn't exist"。

以上是 Python 中图(Graph)的欧拉回路和哈密顿回路算法的实现和使用例子，可以根据实际需求进行相应的调整和扩展。