effiziente Art und Weise Graphentheorie Algorithmen

Question

ich gerade gelesen über den breadth-first search Algorithmus in der Einführung in Algorithmen Buch zu üben und ich die Hand den Algorithmus auf Papier simuliert. Was ich jetzt tun möchte, ist, es in Code für zusätzliche Übung zu implementieren.

Ich dachte über die Implementierung aller Datenstrukturen von Grund auf neu (die adjacency list, die "Farbe", "Abstand" und "Eltern" -Arrays), aber dann erinnerte ich mich, dass es derzeit Grafikbibliotheken gibt wie die Boost Grafik Bibliothek und einige andere graph APIs in Python. Ich habe auch versucht, einige BFS-Probleme auf UVA und Sphere Judge Online suchen, aber ich kann nicht sagen, welche Probleme eine BFS-Lösung erfordern würde.

Meine Frage ist, was die meisten schmerzlos Weg wäre, diese Graphenalgorithmen (nicht nur beschränkt auf BFS, sondern wird auch kommen in praktisch, wenn ich DFS implementieren möchten, Dijkstra, Floyd-Warshall, usw.) zu üben. Sites mit Übungsproblemen sind willkommen.

Answer 1

Ich persönlich denke, dass der beste Weg, um diejenigen zu verstehen, würde die Diagrammdarstellung von sich selbst Grund auf neu implementieren.

Auf der einen Seite würde das zeigen Sie tatsächliche Umsetzung Vorbehalte, aus denen Sie lernen warum oder warum ein bestimmter Algorithmus könnte interessant/gut/effizient/was auch immer. Auf der anderen Seite denke ich, dass das Verständnis von Graphen und ihrer realen Verwendung, einschließlich ihrer Implikationen (Rekursion, Leistung/Skalierbarkeit, Anwendungen, Alternativen, ...), durch den Bottom-Up-Ansatz erleichtert wird.

Aber vielleicht ist das nur mir. Das oben genannte ist sehr persönlicher Geschmack.

Answer 2

ich Ihre Frage interessant fand, gegoogelt ich ein bisschen und ich fand JGraphEd.

Es werden nicht alle Graphenalgorithmen abdecken, aber es sieht aus wie ein gutes Werkzeug für Experimente.

Answer 3

Ich stimme mit balpha überein. Der beste Weg, um Algorithmen wirklich zu lernen und zu verstehen, ist die Implementierung. Wählen Sie einfach einen Algorithmus und implementieren Sie ihn. Wenn Sie einen Punkt erreichen, an dem Sie stecken bleiben oder unsicher sind, sehen Sie sich einige Beispiele an. Sie werden dann in der Lage sein, Ihr eigenes Denken mit dem der anderen zu vergleichen, anstatt zu akzeptieren, was angeboten wird.

Sobald Sie gelernt haben, was Sie wollen, ist der beste Weg, um Ihr Verständnis zu festigen ist es zu versuchen, zu lehren oder es jemand anders zu beschreiben. Vielleicht haben Sie einige Leute, die bereit sind, Ihnen zuzuhören, oder Sie könnten zumindest einen Blogeintrag für Personen schreiben, die neu in dem Algorithmus sind, den Sie gerade studiert haben.

Aber wenn Sie für „schmerzlos“ suchen, dann sollten Sie vielleicht ganz klar von Algorithmen bleiben ;-)

Answer 4

This site could help you

Hier finden Sie Beschreibung jedes Problem auf acm problemset haben. Sie können die Kategorie jedes Problems sehen und einen Hinweis darauf geben, um es zu lösen. Suchen Sie einfach nach graphbezogenen Problemen. Guter Rat ist es, diese Hinweise nur zu verwenden, wenn Sie versucht haben, das Problem selbst zu lösen und gescheitert sind.

Answer 5

Visualisierung einiger kürzesten Weg Algorithmen auf reale Daten, wo der erforschten Bereich in gelb angezeigt:

• (bidirectional) Dijkstra
• A*