图中从顶点u出发的极大简单路径必过奇偶值不同两顶点的验证算法

给定无向/有向图G、起始顶点u，以及数组VAL[]，数组中为每个顶点v存储一个自然数VAL[v]。
其中极大简单路径的定义为：该路径无法在保持简单路径（无重复顶点）属性的前提下向两端继续扩展。
本次需要解决两个核心问题：

• 设计算法验证：所有从顶点u出发的极大简单路径，必然包含两个VAL值奇偶性不同的顶点
• 判断是否存在图维度下线性时间复杂度（即O(V+E)，V为顶点数、E为边数）的解法

存在线性时间复杂度的解法，核心逻辑如下：
我们只需要验证是否存在从u出发、所有顶点VAL奇偶性都和u相同的极大简单路径：

• 如果存在这样的路径，说明原题的验证不成立
• 如果不存在这样的路径，说明原题的验证成立
  我们可以通过DFS或BFS遍历所有u可达的、和u奇偶性相同的顶点构成的子图，只要遍历过程中发现某个节点没有未访问的同奇偶邻接节点，就说明找到了符合条件的异常路径，整个验证直接返回不成立。整个遍历过程每个顶点和每条边最多访问一次，时间复杂度为线性。

原有提交的代码存在多处语法和逻辑错误，修正后可运行版本如下：

from enum import Enum

class Color(Enum):
    WHITE = "white"
    GREY = "grey"
    BLACK = "black"

class Node(object):
    def __init__(self, name, adjacency=None):
        self.name = name
        self.adjacency = adjacency if adjacency is not None else []
        self.visit_state = Color.WHITE
        self.predecessor = None

    def __repr__(self) -> str:
        return self.name

    def append(self, vertex):
        self.adjacency.append(vertex)


def verify_parity_rule(start: Node, VAL: dict) -> bool:
    start_parity = VAL[start.name] % 2
    start.visit_state = Color.GREY
    has_same_parity_neighbor = False

    for v in start.adjacency:
        v_parity = VAL[v.name] % 2
        if v_parity != start_parity:
            continue
        # 只遍历同奇偶的邻接节点
        has_same_parity_neighbor = True
        if v.visit_state == Color.WHITE:
            if not verify_parity_rule(v, VAL):
                return False
    
    start.visit_state = Color.BLACK
    # 如果当前同奇偶节点没有可访问的同奇偶邻接，说明找到全同奇偶的极大路径
    return has_same_parity_neighbor


if __name__ == "__main__":
    node1 = Node("A")
    node2 = Node("B")
    node3 = Node("C")
    node4 = Node("D")

    node1.append(node2)
    node1.append(node3)
    node2.append(node3)
    node2.append(node4)
    node3.append(node4)
    VAL = {"A": 1, "B": 3, "C": 4, "D": 5}
    # 返回True代表所有从A出发的极大路径都有奇偶不同的顶点，返回False则存在异常路径
    print(verify_parity_rule(node1, VAL))

• 遍历过程中仅访问和起点奇偶性相同的节点，避免无效计算
• 只要某一个同奇偶的节点没有可继续访问的同奇偶邻接节点，就说明找到了一条从起点出发的全同奇偶极大路径，验证不通过直接返回False
• 遍历结束没有找到这样的节点，说明所有极大路径必然会走到奇偶不同的节点，验证通过返回True

内容的提问来源于stack exchange，提问作者mario