Найти цикл в неориентированном графе только с порядком поствизитов - PullRequest
Новая
       40

Найти цикл в неориентированном графе только с порядком поствизитов

0 голосов
/ 04 апреля 2020

Можно ли использовать порядок поствизитов в DFS, чтобы проверить, содержит ли ненаправленный граф цикл?

Проблема состоит в том, чтобы проверить, является ли граф G допустимым деревом. Действительное дерево может быть проверено с помощью DFS с двумя условиями:

  1. G не содержит циклов ИЛИ num_vertices - 1 = num_edges
  2. G полностью подключено, что означает количество подключенных компонентов == 1

Мне очень нравятся алгоритмы DFS в учебнике DPV (2006) из U C Беркли, потому что он позволяет вам находить циклы проверки, топологическую сортировку и находить связанные компоненты все в одном. Этот код работает с ориентированными графами и должен работать с неориентированными графами, но это isCycle (который проверяет обратные ребра) ломается на неориентированных графах.

Я не могу понять, почему hasCycle () основан на поствизит перерывы. Если postvisit находит циклы только в ориентированных графах, то я могу сосредоточиться на том, что если сосед посещен и сосед! = Parent [v], то цикл существует. 

edges = [[0,1],[0,2],[1,2]]
ans = Solution().validTree(edges)
>> True
>> pre = {0: 0, 1: 1, 2: 2}
>> post = {2: 3, 1: 4, 0: 5})


class Solution(object):
    def validTree(self, edges: List[List[int]]) -> bool:
        # Create adjacency list
        graph = collections.defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        pre, post, cc = self.dfs(graph) 
        # TODO: containsCycles per backEdge is broken
        return not self.containsCycle(edges, post) and cc == 1 # BREAKS
        #return cc == 1 and len(graph.keys()) - 1 == len(edges) # OK, works

    def containsCycle(self, edges, post):
        """Check (z->w), post[z] > post[w] if not Backedge"""
        for (z, w) in edges:
            if not post[z] > post[w]: return True   
        return False

    def containsCycleAncestor(self, edge, parent, visited):
        """If we visited neighbor and neighbor is not parent, then ancestor"""
        v, neighbor = edge # v->neighbor
        return neighbor in visited and neighbor != parent[v]

    def dfs(self, graph):
        """Run DFS to check if there is a cycle."""
        clock = [0] # global clock
        visited = set()
        pre = collections.defaultdict(int)
        post = collections.defaultdict(int)
        cc = 0
        for v in graph.keys():
            if v not in visited:
                cc += 1
                self.explore(graph, v, pre, post, clock, visited) 

        return pre, post, cc

    def explore(self, graph, v, pre, post, clock, visited):
        """Visit neighbors of vertex v."""
        visited.add(v)
        pre[v] = clock[0]
        clock[0] += 1
        for neighbor in graph[v]:
            if neighbor not in visited:
                self.explore(graph, neighbor, pre, post, clock, visited)
        post[v] = clock[0]
        clock[0] += 1
...