Graph Algorithm Basic

1. Graph Representation in Memory

1. Adjacency matrix:
2. Sorted Edge List (minor): every edge is stored as a tuple (vi;vj) in a sorted list.
3. Adjacency List: node array + edge list;
4. Objects and Pointers: (similar to (2), but not sorted)

1) The optimal representation depends on the type of the graph. For instance, a Matrix wastes a lot of memory if a sparse graph is given, but it has optimal access times for any type of graph.
2) Objects and Pointers: very easy to insert and delete.
3) In Matrix, only use 0 or 1; But in Adjacency List, has to use Integers.
4) In Matrix, has to scan all N nodes to get Adjacency nodes.

Graph Traversal:
DFS: Fast to find one solution, but may need to scan the whole search space;

1. explicitly stack-based method: more complex but use heap memory (more safe)
2. implicitly recursive functions: simply to code but careful the stack overflow

BFS: No need to search the whole search space; especially for questions like "find the shortest path to ..."

1. explicitly queue-based method: more complex but use heap memory (more safe)

Notice the similarities between this and a depth-first search, we only differ in the data structure used and we mark a vertex visited as we push it into the queue, not as we pop it. 

2. Shortest Path Problems

2.1 Single source shortest path problem 
Dijkstra’s algorithm

• A* Algorithm tends to be faster, but has the same big-O notation.
• Bellman-Ford algorithm can deal with negative weights.

2.2 All pairs shortest path problem

Floyd-Warshall Algorithm: