Graph

Graph

1. Spanning tree

   • Whole, Acyclic subgraph. Includes all the nodes in the graph.
   • Minimum spanning tree
     • Prim
       • Greedy. We want to be adding nodes that are the closest to the Tree (T) being constructed.(NOT A NODE LIKE DJIKSTRA). So we want in every turn add minDist[] EDGE, to the tree. Means we want to know dist[] and parent! (to what node is the distance) Initialise all dist[]=inf, parent[]=nil.Start with random node.dist[rNode] = 0, Go through adj. list, update dist and parent. Here's the trick. Although the heap contains nodes (key value is their distance), tree T contains edges. So T= T u ({n,v}).
     • Kruskal
       • Every node is it's own island. We connect them one by one, cheapest first. In the end, only one island remains. Remember, it's a tree we are building, so edges. for every edge we check wheter it connects to islands then we do it if it does. We take em from a heap.
       • Union-Find
         • find
           • find(x) find grandparent of x return
         • union
           • Union(y,z) if(y.h y.p=z else if z.h>y.h else if EQUAL y.p=z z.h ++
         • make-set
           • make-set(x) x.parent=x x.height = 0

2. Shortest path

   • Single-source
     • Dijkstra
       • Optimized Relax calls. (Every Edge relaxed once)
       • Dijkstra
     • Bellman-Ford
       • Not optimized Relax calls. Max V-1 times Relax calls per edge. V-1 times      for every Edge            relax(edge) 
   • All
     • Floyd-Warshall

3. Unweighted graphs

   • Path finding. path[]
     • Breadth-first-search
       • Input: Graph and source Goal: all shortest paths known. Tools:  -queue, to store nodes in order -path array, path[u] tells the node leading to u. -distance array -visited boolean array,  or "added to que" array
     • Depth-first-search
       • Cycle detection. There is a cycle in a graph only if there is a backward edge in the algorithm.

4. Topological sort

   • for every directed edge   uv in the sorting, u comes before v. needs to be a directed acyclic graph