Sie haben eine Grafik von n Knoten (nummeriert 1-n) und m Kanten. Sie entfernen alle Knoten nacheinander und überprüfen bei jedem Schritt, ob der Graph vollständig verbunden ist oder nicht (durch Drucken von "Verbunden" oder nicht). Die Reihenfolge der zu entfernenden Knoten ist angegeben.Graph-Theorie-Puzzle über Konnektivität?
Zum Beispiel
n = 4 und m= 3 Die Kanten gegeben sind: 1 - 2, 2 - 3, 3 - 4. Das Entfernen Reihenfolge ist: 3, 4, 1, 2
die Knoten sind 1-n nummeriert, so dass die Knoten in diesem Fall sind 1, 2, 3, 4.
Zunächst wird der graph verbunden ist, so dass Sie ausdrucken:
Verbunden
Zuerst entfernen Sie Knoten 3. Jetzt wird die Grafik getrennt, da Knoten 4 alleine ist.
Disconnected
Dann entfernen Sie Knoten 4. Nun ist die grafische Darstellung besteht aus nur Knoten 1 und 2, die miteinander verbunden sind.
Verbunden
Dann entfernen Sie Knoten 1. Der Graph nach wie vor verbunden ist, betrachtet; Es gibt nur einen Knoten.
Verbunden
Sie entfernen dann Knoten 2 nichts mehr übrig ist.
Beispielcode wäre hilfreich, vorzugsweise Java oder C++. Ich habe versucht, BFS und DFS zu verwenden, aber sie waren zu langsam. Was ist der effizienteste Weg, dies zu tun?
Wer all meine Fragen ablehnt: Warum? –
Hören Sie auf, die Probleme zu kopieren, die jemand von Ihnen zu lösen versucht hat, versuchen Sie, sie zu beantworten, und wenn Sie uns nicht zeigen können, wo Sie versagt haben. Es ist SO, nicht "Wir machen deine Arbeit". – FiReTiTi
Ich glaube, ich habe dir gezeigt, wo ich versagt habe. Ich sagte, ich benutze BFS und DFS, aber sie waren zu langsam. Ich möchte nur wissen, was der effizienteste Weg ist, dies zu tun. –