Learning Graph Algorithms

In algorith开发者_StackOverflowms, I've mostly been self-taught and that's largely been fine. However, I'm having trouble grasping graph algorithns. I'm looking for some kind of reference that has concepts and actual code so I can not only learn the theory (which I usually do ok with) but also get a feel for how graphs are represented and manipulated in practice (what I usually have a harder time grasping). Can SO deliver? Anything from books, to links, to existing projects would be great as long as they have both concept and implementation.

This is language agnostic, but I'm most familiar with python and don't have much experience with FP.

---

Both of these are very good:

• The Algorithm Design Manual

• Algorithms in C++ Part 5: Graph Algorithms (Don't worry about the C++ bit, has pseudocode as well)

Free Stuff:

• Chapter 5. Graphs and graph algorithms

---

Steve Yegge says this is a terrific book on algorithms that uses graphs extensively.

---

I would suggest that when you study any algorithms then don't think of coding it. Algorithms are totally mathematical and you must have the same attitude towards them. When you study something like Graph Spanner algorithm then don't think how to code it how to represent them. First appreciate why the algorithm is important and non-trivial. Then try some very trivial solutions and compare their complexity. Next see how optimal solutions look like and try to derive their properties. Use a paper and pen and not IDE, try to derive and prove lemmas and so on. Then finally see how you can write a pseudocode to solve the problem. If you do these things then you will develop an intimate relation with the algorithms and then you will find it is much easier to solve them since then you don't think while coding that why I am doing this.

Unfortunately due to tremendous demands for programmer the programmer of now days are not mathematician and they face problems in solving new problems. Programmer of earlier days such as Don Knuth, Mcarthy were mathematicians and good researchers. Hence programmer is now a days relatively cheap word compared to computer scientists.

---

I learned a lot about graphs from the book linked below... it's one of my favorite books:

A Course in Combinatorics
by J. H. van Lint, R. M. Wilson
Cambridge University Press
ISBN 0 521 00601 5

---

Bellman–Ford algorithm: Shortest path from Source to all other nodes in weighted directed graph even with -eve edge weight (not cycle). slower but versatile than Dijsktra. Complexity: O(|V|.|E|)

BFS: Find path from one given vertex to other nodes in un-weighted un-directed graph. Complexity: O(|V|+|E|). it is faster when you know vertices ahead and use appropriate data structure i.e FIFO Que for figuring out which vertex already processed than complexity can be reduced to O(|V|)

DFS: Find Shortest path from source to other nodes. in Tree and also in Graph. Graph may contain cycle which means a node could be visited again and again. so we can use boolean array to keep track of visited nodes. otherwise algorithm won't stop. more over it look deeper and deeper and go as far to the end of branch in tree. Complexity: O(|V|+|E|). and Complexity: O(|V|) space to store vertices.

Floyed Warshal Algorithm: Find All pair shortest path in Directed unweighted graph with +eve, -eve (not cycle) edge weight. but it doesn't return details of the paths themselves. it can be used to detect -eve weight cycle in graph. when it find one it terminates. it compare all possible path through graph between each pair of vertices . so it uses Dynamic approach not greedy approach. Complexity: O(|V^3|)

Johnson's Algorithm: find all pair shortest path in directed weighted sparse graph when edge weight is +eve, -eve but not -eve cycle. it first uses belman-ford algorithm to compute transformed graph from original graph. it removes -eve weight edges. then Dijkstra is applied to find paths. Complexity: O(V^2 Log V + VE)

Dijkstra Algorithm: the original version of this algorithm not uses Priority Que so Complexity is O(|V^2|) but a newer version uses this data structure so complexity becomes O(E+ V log V). and it is faster single source shortest path algorithm. it works by assigning a tentative weight to visited node and infinity to un-visited nodes for visited node look for its all not visited edges and select with minimum weight. and add it to path set.

Krushkal's Algorithm: to find MST where it finds an edge of least possible weight that connects any two tree in forest on un-directed, weighted graph. this is greedy algorithm. it also find Minimum Spanning Forest. Complexity: O(E log V)

Prim's Algorithm: it finds subset of edges that form a tree on un-directed, weighted graph. but can't find MS Forest like Krushkal's Algorithm does.

Brouvka's Algorithm: Problem with this algorithm is that weights should be unique in graph. it find MST by examining each vertex then putting with smaller weight. this algorithm is parallel in nature but not faster than Prim's Algorithm.

Same Complexity as Krushkal's Algorithm.