Graph Algorithms

This video explains these algorithms really well, but the machine voice is soooo annoying! :-/
It'll just have to do for now.

(I only watched the first one though. I'm only assuming that the rest will be useful too)

Floyd's Algorithm

Kruskal's Algorithm

Drijkstra Dijkstra's Algorithm

(hehe they made a spelling error / typo in the title)

Prim's Algorithm

DFS

BFS

Link to this channel






*if any of these don't coincide with what you were taught in class, please let me know so I can fix it

Radix Sort

Radix Sort from GowriKumar Chandramouli

Explanation with no animation here

DFS & BFS

Depth-First Search

procedure dfs(vertex v)
{
   mark v as visited
   for each w adjacent to v
      if w unvisited
         dfs(w)
}



Breadth-First Search

procedure BFS(vertex s)
{
   create a queue Q
   enqueue s onto Q
   mark s as visited
   while Q is not empty
   {
      dequeue a vertex from Q into v
      for each w adjacent to v
      {
         if w unvisited 
         {
            mark w as visited
            enqueue w onto Q
         }
      }
   }
}


DFS
BFS

WFIalgorithm

Warshall / Floyd / Ingerman Algorithm (for finding shortest paths)

The graph can include negative weights.
This algorithm also allows us to detect cycles if the diagonal is initialized to inf and not to zero. If any of the diagonal values are changed, then the graph contains a cycle. Basically, if the cost / distance from node A to node A is not inf, it contains a cycle.

http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

B-Trees

Play around with this to get the feel for b-trees:

http://slady.net/java/bt/view.php

(Blogger won't let me embed it :( )