Graph

Nota:

• Whole, Acyclic subgraph. Includes all the nodes in the graph.

1. Minimum spanning tree
   1. Prim

      Nota:

      • 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}).
   2. Kruskal

      Nota:

      • 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.
      1. Union-Find
         1. find

            Nota:

            • find(x) find grandparent of x return
         2. union

            Nota:

            • Union(y,z) if(y.h y.p=z else if z.h>y.h else if EQUAL y.p=z z.h ++
         3. make-set

            Nota:

            • make-set(x) x.parent=x x.height = 0

1. Single-source
   1. Dijkstra

      Nota:

      • Optimized Relax calls. (Every Edge relaxed once)

      Adjunto:

      • Dijkstra
   2. Bellman-Ford

      Nota:

      • Not optimized Relax calls. Max V-1 times Relax calls per edge. V-1 times      for every Edge            relax(edge) 
2. All
   1. Floyd-Warshall

1. Path finding. path[]
   1. Breadth-first-search

      Nota:

      • 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
   2. Depth-first-search

      Nota:

      • Cycle detection. There is a cycle in a graph only if there is a backward edge in the algorithm.

Nota:

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