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.Écrire un programme pour vérifier si un graphe est bipartite
Répondre
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.
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.
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;
}
- 1. Partitionner des correspondances parfaites dans un graphe bipartite
- 2. Comment vérifier si un graphe orienté est acyclique?
- 3. Comment vérifier si un programme se termine?
- 4. Programme pour vérifier un Palindrome
- 5. Pour vérifier si Office est installé sur un serveur
- 6. Comment vérifier si un pointeur est valide?
- 7. besoin d'aide pour écrire un programme
- 8. Comment vérifier si FileObject est un dossier?
- 9. Aide! Vérifier si un champ est vide
- 10. Comment vérifier si un fichier est ouvert
- 11. ssh: vérifier si un tunnel est vivant
- 12. Écrire un programme pour gratter des forums
- 13. Ecrivez un programme pour vérifier si un caractère forme un caractère d'échappement en C
- 14. vérifier si un tableau est multidimensionnel
- 15. Comment vérifier si un objet est nul
- 16. Comment vérifier si un objet est nul
- 17. Comment vérifier si un menu est affiché
- 18. AS3: Vérifier si un dictionnaire est vide
- 19. Comment vérifier si un objet est défini?
- 20. vérifier si une chaîne est un double
- 21. Comment vérifier si un bouton est cliqué?
- 22. Comment vérifier si un BOOL est nul?
- 23. Java vérifier si BufferedImage est un GIF
- 24. Écrire un programme comme netstat
- 25. écrire un simple programme ofx4j
- 26. algorithme pour vérifier si un espace est convexe
- 27. Way pour vérifier si le type est un ENUM
- 28. Un liner pour vérifier si l'élément est dans la liste
- 29. Regex pour vérifier si un nombre est pair
- 30. Pour vérifier si un objet est vide ou non
On dirait que cela ne fonctionne que pour les graphiques connectés. –
Bien! Qui ne comprend pas pourquoi le conflit de coloration signifie qu'il n'est pas bipartite alors je recommande de lire la réponse de @Haoran Wang. – Narek