Dwudzielność grafu

Z RNO-Wiki

Zapoznaj się z definicją grafu dwudzielnego na Wikipedii [1].

Sprawdzanie dwudzielności grafu można zrealizować w bardzo prosty sposób. Wystarczy go przejrzeć w głąb lub wszerz odpowiednio kolorując wierzchołki; zakładamy, że dysponujemy tylko dwoma kolorami. Jeśli podczas odwiedzania wierzchołka napotykamy konflikt, tj. jego sąsiad ma taki sam kolor, to przerywamy przeglądanie z odpowiedzią, że dany graf nie jest grafem dwudzielnym.

Implementacja

Implementacja w pseudo języku

int color[]; // tablica kolorów wierzchołków ;
 
// Na początku zakłada się, że wszystkie wierzchołki nie mają żadnego koloru
 
bool dfs(int u, int c) // odwiedź wierzchołek u ; pokoloruj go na kolor c
{
    // pokoloruj wierzchołek u na kolor c
    // dla wszystkich sąsiadów v wierzchołka u wykonaj:
    //     jeśli v ma kolor c to zwróć FALSE
    //     jeśli v nie ma żadnego koloru, to wykonaj
    //        dfs(v, d)  //  d - to kolor przeciwny do c
    //        jeśli dfs zwróciło FALSE, to zwróć FALSE
    // zwróć TRUE    
}

Implementacja w C/C++

 
Osobiste