Whole, Acyclic subgraph.
Includes all the nodes in the graph.
1.1 Minimum spanning tree
1.1.1 Prim
Annotations:
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}).
1.1.2 Kruskal
Annotations:
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.1.2.1 Union-Find
1.1.2.1.1 find
Annotations:
find(x)
find grandparent of x
return
1.1.2.1.2 union
Annotations:
Union(y,z)
if(y.h
y.p=z
else if z.h>y.h
else if EQUAL
y.p=z
z.h ++
Not optimized Relax calls.
Max V-1 times Relax calls per edge.
V-1 times
for every Edge
relax(edge)
2.2 All
2.2.1 Floyd-Warshall
3 Unweighted graphs
3.1 Path finding.
path[]
3.1.1 Breadth-first-search
Annotations:
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
3.1.2 Depth-first-search
Annotations:
Cycle detection.
There is a cycle in a graph only if there is a backward edge in the algorithm.
4 Topological sort
Annotations:
for every directed edge uv
in the sorting, u comes before v.
needs to be a directed acyclic graph