Écrire un programme pour vérifier si un graphe est bipartite

Question

Je dois écrire un programme qui vérifie si un graphe est bipartite. J'ai lu des articles de wikipedia sur graph coloring et bipartite graph. Ces deux articles suggèrent des méthodes pour tester la bipartitude comme la recherche BFS, mais je ne peux pas écrire un programme implémentant ces méthodes.

Answer 1

Pourquoi pas vous? Votre question rend difficile pour quelqu'un d'écrire même le programme pour vous puisque vous ne mentionnez même pas une langue spécifique ...

L'idée est de commencer par placer un nœud aléatoire dans une file d'attente FIFO (également here). Colorie-le en bleu. Puis répétez ceci alors qu'il y a encore des nœuds dans la file d'attente: dequeue un élément. Colorez ses voisins avec une couleur différente de celle de l'élément extrait et insérez (enqueue) chaque voisin dans la file d'attente FIFO. Par exemple, si vous supprimez (extrayez) un élément (noeud) coloré en rouge, colorez ses voisins en bleu. Si vous extrayez un nœud bleu, colorez ses voisins en rouge. S'il n'y a pas de conflit de coloration, le graphique est bipartite. Si vous finissez par colorier un nœud avec deux couleurs différentes, ce n'est pas bipartite. Comme @Moron a dit, ce que j'ai décrit ne fonctionnera que pour les graphes connectés. Cependant, vous pouvez appliquer le même algorithme sur chaque composant connecté pour le faire fonctionner pour n'importe quel graphique.

Answer 2

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/breadthSearch.htm

S'il vous plaît lire cette page web, en utilisant la largeur première recherche pour vérifier si vous trouvez un noeud a été visité, vérifiez le cycle en cours est pair ou impair.

Un graphe est bipartite si et seulement s'il ne contient pas de cycle impair.

Answer 3

La mise en œuvre est détaillée comme suit (version C++):

struct NODE 
{ 
    int color; 
    vector<int> neigh_list; 
}; 

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index); 

bool checkBigraph(NODE * graph, int numNodes) 
{ 
    int start = 0; 

    do 
    { 
     queue<int> Myqueue; 
     Myqueue.push(start); 
     graph[start].color = 0; 

     while(!Myqueue.empty()) 
     { 
      int gid = Myqueue.front(); 
      for(int i=0; i<graph[gid].neigh_list.size(); i++) 
      { 
       int neighid = graph[gid].neigh_list[i]; 
       if(graph[neighid].color == -1) 
       { 
        graph[neighid].color = (graph[gid].color+1)%2; // assign to another group 
        Myqueue.push(neighid); 
       } 
       else 
       { 
        if(graph[neighid].color == graph[gid].color) // touble pair in the same group 
         return false; 
       } 
      } 
      Myqueue.pop(); 
     } 
    } while (!checkAllNodesVisited(graph, numNodes, start)); // make sure all nodes visited 
              // to be able to handle several separated graphs, IMPORTANT!!! 

    return true; 
} 

bool checkAllNodesVisited(NODE *graph, int numNodes, int & index) 
{ 
    for (int i=0; i<numNodes; i++) 
    { 
     if (graph[i].color == -1) 
     { 
      index = i; 
      return false; 
     } 
    } 

    return true; 
}