Jaka jest złożoność czasowa algorytmu Best w celu ustalenia, czy nieukierunkowany wykres jest drzewem?Najlepszy algorytm do określenia, czy nieukierunkowany wykres jest drzewem
Czy możemy powiedzieć Big-oh (n), z n wierzchołkami ??
Tak, to O (n).
Wybierz początkowy węzeł i przeprowadź pierwszą głębokość przejścia. Jeśli odwiedzasz węzeł więcej niż raz, nie jest to drzewo.
Tak, to O (n). Przy pierwszym wyszukiwaniu na wykresie skierowanym do głębi ma 3 typy krawędzi niebrzydkich - krzyż, tył i przód.
W przypadku przekierowanego przypadku jedynym rodzajem krawędzi niewrębowych jest tylna krawędź. Musisz więc szukać tylnych krawędzi.
Krótko mówiąc, wybierz początkowy wierzchołek. Przechyl i sprawdzaj, czy napotkana krawędź jest tylną krawędzią. Jeśli znajdziesz krawędzie drzewa n-1 bez odnajdywania tylnych krawędzi, a potem skończysz z krawędzi, jesteś złota.
(Tylko w celu wyjaśnienia - back edge to taki, w którym wierzchołek na drugim końcu już został napotkany - i ze względu na właściwości nie przekierowanych grafów, wierzchołek na drugim końcu byłby przodkiem obecnego węzła w drzewo, które jest budowane.)
thnx .. czy możemy to zrobić również za pomocą BFS w czasie O (n) – rakesh
Można, ale BFS może być wolniejszy, ponieważ nie znajdzie tak szybko cykli. –
Thnx anthony ... możemy to zrobić również za pomocą BFS z czasem O (n) – rakesh
Tak, ale głębokość pierwsza jest lepsza, ponieważ szybciej znajdzie cykle. –
Sprawdź również, czy wszystkie węzły są odwiedzane, w przeciwnym razie może to być las. – dieram3