Graph Algorithms
Back to ReadingRoom
Textbooks
- Cormen: secn 6 Graph Algorithms(ch 22, 23, 24 thru p588 and p595-601, 25 Floyd-Warshall)
- The Discrete Math textbook(Rosen) has some good computing applications in the back of the Graphs chapter; also has shortest-path algs in secn 7.6.
Online
- Some starting points:
Wikipedia: Graph theory - some basic terminology and trivial coverage of topics. Especially look at the route and network flow graph problems, as well as graph algorithms.
Wikipedia: Graph data structures - storing data in graphs
Wikipedia: Category Graph Theory - LOTS of related articles, topics, problems.
thefreedictionary: Greedy Algorithm - sparse and a bit obfuscated, but might be useful
Wikipedia: Greedy Algorithm - less weirded than thefreedictionary, but still short.
Graph Algorithms - from an online text/lecture notes for The Algorithm Design manual. Looks highly readable; more in-depth than Wikipedia. With examples.
- Some cool applications:
Mazes - uses graph theory to draw mazes.
Graph Mining as applied to Web Communities(PDF) - how Google uses graphs
Wikipedia: Minimum Spanning Tree - we constructed one of these in class.