Die besten Ressourcen zum Erlernen der Graphentheorie

Mohammed Islam Hadjoudj

Experte für Operations Research

So wählen Sie eine Ressource aus

Die beste Ressource ist diejenige, die zu Ihrer Lernweise und Ihrem Grund passt, hier zu sein. Ein künftiger Forscher und eine Kandidatin zwei Wochen vor einem Interview sollten nicht dasselbe Buch aufschlagen. Gehen Sie von Ihrem Ziel aus.

Ein Hinweis vor der Liste: Sie brauchen nicht all das. Wählen Sie eine Hauptressource und eine zum Üben und ergänzen Sie erst weitere, wenn Sie an eine Grenze stoßen. Der Rest dieses Leitfadens vertieft jede Zeile oben.

Hier beginnen: Die Learn-Graph-Theory-Plattform

Vor den einzelnen Büchern und Kursen lohnt es sich, die Ressource hervorzuheben, auf der dieser Leitfaden aufbaut, denn sie ist ein seltenes All-in-one. Die meisten Optionen unten können eine Sache gut. Learn Graph Theory vereint sie an einem Ort, sodass Sie von der ersten Definition bis zur Interviewreife gelangen, ohne zwischen einem Dutzend Tabs zu springen.

• Ein interaktiver Visualizer: Gehen Sie BFS, DFS, Dijkstra, minimale Spannbäume, Netzwerkfluss und mehr Schritt für Schritt an Graphen durch, die Sie selbst erstellen und steuern. Öffnen Sie den Algorithmus-Visualizer.
• Geführte Lektionen: strukturierte, aufeinander aufbauende Lektionen, die Sie in sinnvoller Reihenfolge durch jedes Thema führen.
• Eine große, kostenlose Artikelbibliothek: ausführliche Erklärungen zu nahezu jedem Graphenthema, von der Lern-Roadmap und dem Algorithmen-Cheatsheet bis zu Tiefeinblicken in Dijkstra, topologische Sortierung und Union-Find. Durchstöbern Sie alle im Artikel-Hub.
• Herunterladbare Begleiter: das Algorithms Handbook und die Graph Theory Masterclass bieten Ihnen eine offline, prüfungsreife Referenz und einen kompletten Lehrplan (beide werden am Ende dieses Leitfadens behandelt).

Wenn Sie aus diesem Leitfaden eine Sache mit einem Lesezeichen versehen, dann diese: interaktives Üben, strukturierte Lektionen, eine vollständige Referenzbibliothek und herunterladbare Leitfäden, alles in einer einzigen Umgebung und größtenteils kostenlos.

Weitere interaktive Tools

Über den Learn Graph Theory Visualizer oben hinaus lohnt sich ein weiteres Visualisierungsprojekt. Einen Algorithmus laufen zu sehen bringt in einer Minute mehr als eine Seite Pseudocode, daher lohnt sich ein zweiter Blickwinkel.

• VisuAlgo: ein langjähriges Visualisierungsprojekt, das viele Datenstrukturen und Graphalgorithmen abdeckt, eine nützliche Ergänzung.

Nutzen Sie einen Visualizer, während Sie etwas anderes lesen. Wann immer ein Konzept abstrakt wirkt, geben Sie es ein und sehen Sie ihm bei der Bewegung zu.

Die besten Bücher

Bücher gewinnen weiterhin bei Tiefe und Beständigkeit. Passen Sie das Buch an Ihr Niveau an.

• West, Introduction to Graph Theory: der Standard für einen strengen, beweisbasierten ersten Kurs. Gründlich und weit verbreitet an Universitäten.
• Chartrand und Zhang, A First Course in Graph Theory: ein sanfteres, günstiges Dover-Taschenbuch. Eine gute Wahl, wenn West zu früh zu viel erscheint.
• Diestel, Graph Theory: die Referenz auf Graduiertenniveau für echte Tiefe. Eine kostenlose Online-Ausgabe ist verfügbar, sodass man leicht hineinschnuppern kann.
• Cormen, Leiserson, Rivest und Stein, Introduction to Algorithms (CLRS): kein Graphentheorie-Buch, aber die maßgebliche Referenz für die Graph-algorithmen (BFS, DFS, Dijkstra, MST, Fluss).
• Skiena, The Algorithm Design Manual: praktisch und gut lesbar, mit einem Problemkatalog und ehrlichen Ratschlägen, zu welchem Algorithmus man greifen sollte.

Online-Kurse

Wenn Sie Struktur und Fristen bevorzugen, hält Sie ein Kurs in Bewegung.

• Coursera, Algorithms on Graphs: ein fokussierter Kurs über Graphalgorithmen innerhalb einer größeren Spezialisierung zu Datenstrukturen und Algorithmen. Praxisnah und getaktet.
• MIT OpenCourseWare, Introduction to Algorithms: vollständige Vorlesungsvideos und Notizen, kostenlos. Die Graphenabschnitte bieten eine strenge Behandlung auf Universitätsniveau.
• Roughgarden, Algorithms Illuminated: eine klare vierteilige Reihe (Buch und begleitende Videos), die Graphensuche, kürzeste Wege und mehr mit ungewöhnlicher Klarheit behandelt.

Kostenlose Videoreihen

Für visuelles, reibungsloses Lernen, das Sie auch unterwegs erledigen können, ist Video kaum zu übertreffen.

• William Fisets Graphentheorie-Reihe: eine umfassende, anfängerfreundliche Playlist (auch über freeCodeCamp veröffentlicht), die Traversierung, kürzeste Wege, Bäume, Fluss und mehr mit sauberen Animationen abdeckt.
• MIT-OpenCourseWare-Vorlesungen: die aufgezeichneten Algorithmus-Vorlesungen sind kostenlos und gehen in die Tiefe, wenn Sie die akademische Variante möchten.

Übung und Aufgaben

Lesen ist kein Lernen. Sie festigen Graphentheorie, indem Sie Aufgaben lösen.

• LeetCode (Graph-Tag): die erste Anlaufstelle für interviewartige Aufgaben, von Number of Islands bis Course Schedule.
• CP-Algorithms: eine kostenlose Enzyklopädie von Algorithmen mit sauberen Referenzimplementierungen, hervorragend für Wettbewerbsprogrammierung.
• Codeforces: Wettbewerbe und ein riesiges Aufgabenarchiv, nach Thema filterbar, um über die Grundlagen hinauszukommen.

Egal, was Sie verwenden, arbeiten Sie in Mustern statt an zufälligen Aufgaben. Der Leitfaden Graphalgorithmen für Coding-Interviews gruppiert Aufgaben nach der benötigten Technik.

Schnellreferenzen und Lernhilfen

Sobald Sie die Grundlagen hinter sich haben, brauchen Sie vor allem eine schnelle Möglichkeit zum Auffrischen. Hier zahlt sich eine gute Referenz aus.

• Kostenlos auf dieser Website: die Lern-Roadmap legt dar, was wann zu lernen ist, das Algorithmen-Cheatsheet bringt jede Komplexität auf eine Seite, und die vertiefenden Artikel behandeln Dijkstra, topologische Sortierung und mehr.
• Herunterladbare Begleiter: das Algorithms Handbook erweitert das Cheatsheet auf 55 Algorithmen mit Pseudocode und Komplexität, und die Graph Theory Masterclass ist ein strukturierter Kurs aus neun Modulen, der die Roadmap widerspiegelt. Beide werden unten behandelt.

Alles zusammenführen

Eine Ressourcenliste ist nur nützlich, wenn sie zu einem Plan wird. Hier ist eine einfache Möglichkeit, das Obige zu kombinieren, ohne sich zu überlasten.

1. Verankern Sie sich an einer Hauptressource: ein Buch für Strenge, ein Kurs für Struktur, der Visualizer und Videos für Intuition.
2. Üben Sie parallel dazu auf LeetCode oder Codeforces, ein paar Aufgaben pro Thema.
3. Halten Sie eine Referenz offen (das Cheatsheet oder Handbook), damit Sie beim Suchen einer Komplexität nie den Schwung verlieren.
4. Folgen Sie einer Reihenfolge. Wenn Sie unsicher sind, wo Sie beginnen sollen, ordnet die Lern-Roadmap alles von den Grundlagen bis zur Interviewreife.