Graphentheorie
-
Hi,
kann mir jemand sagen, wie eine Breitensuche für einen bipartiten Graphen aussieht ? Also ich meine, wie genau geht die Suche (schematisch) vor sich ? Prinzipiell kenne ich den Unterschied zwischen Breiten- und Tiefensuche aber kann mir das für einen bipartiten Graphen irgendwie nicht vorstellen. Das hängt vermutlich (stark) damit zusammen, wie man einen Baum darin generiert, oder ?
Danke!
-
Breiten- und Tiefensuche funktionieren genau gleich wie fuer jeden anderen Graphen auch. Ich verstehe deshalb deine Frage nicht genau.
Nimm doch mal einen bipartiten Graphen und fuehre darauf von Hand Breiten- und Tiefensuche durch. Vielleicht wirds dann klarer.
-
da DFS und BFS auf allgemeinen Graphen definiert sind, stellt ein bitartiter Graph natürlich keinen Sonderfall dar. Es könnte höchstens sein, dass der Algorithmus sich für spezielle Klassen von Graphen noch weiter vereinfachen könnte - das kann dir aber egal sein.