Est biparti
Leçon 14 sur 14 du cours Graphes - Série Structures de données n°9 de Coddy.
Un graphe est bipartite si vous pouvez diviser ses sommets en deux groupes de sorte que chaque arête relie un sommet d'un groupe à un sommet de l'autre. Pensez au rouge et au bleu : chaque arête a une extrémité rouge et une extrémité bleue.
Le parcours BFS (parcours en largeur) offre un test simple. Commencez par n'importe quel sommet, coloriez-le en rouge et progressez vers l'extérieur. Chaque nouveau voisin reçoit la couleur opposée du sommet dont nous venons. Si nous voyons une arête qui relie deux sommets ayant la même couleur, le graphe n'est pas bipartite. Le coupable classique est un cycle de longueur impaire : un triangle 0-1-2-0 force le sommet 0 à être à la fois rouge et bleu.
Une chose à retenir : si le graphe possède plusieurs composantes connexes, vous devez recommencer un nouveau coloriage à deux couleurs sur chacune d'elles. Le modèle le plus simple est une boucle unique sur tous les sommets qui lance un BFS chaque fois qu'elle trouve un sommet non coloré.
Défi
FacileÉcrivez une fonction isBipartite qui reçoit un tableau d'entiers 2D adjacency et un tableau d'entiers vertices, et renvoie true si le graphe est biparti, false sinon.
Construisez le graphe (addVertex pour chaque sommet, puis addEdge pour chaque arête). Ensuite, effectuez un coloriage avec 2 couleurs via un parcours BFS sur chaque composante connexe : attribuez la couleur de départ 0, et donnez à chaque voisin la couleur 1 - color[u]. Si vous trouvez une arête où les deux extrémités ont déjà la même couleur, renvoyez false. Sinon, renvoyez true.
Vous devez utiliser la classe Graph (fournie dans graph) - n'utilisez pas les structures intégrées du langage (maps, sets) pour modéliser l'adjacence. Les données auxiliaires pour l'algorithme (color map, file d'attente) peuvent utiliser les types de la bibliothèque standard (stdlib).
Essayez vous-même
#include <stdio.h>
#include "solution.h"
int main() {
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
int vertices[MAX_VERTICES];
for (int i = 0; i < n; i++) scanf("%d", &vertices[i]);
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
printf("%s\n", isBipartite(adjacency, m, vertices, n) ? "true" : "false");
return 0;
}