Graph Theory notes

Graph Theory Pop Quiz

* What is the best implementation, an adjacency List or Adjacency Matrix type implementation for a BFS Algorithm when dealing with a sparse graph ?

Why ?
 
What is the time complexity of the following algorithms:

* Dijkstra's shortest Path algorithm
* Kruskal's algorithm
* BFS
* DFS
*A* ?
* Dual Source Implementation of Dijkstra's Algorithm ?

* describe what an bipartite graph is...
 
* What is he number of edges of a connected undirected graph containing 47 vertices ?

* in what situation will Dijkstra's algorithm not function correctly?

* what does DAG stand for ?


* can a connected graph have several components ?  
* Which algorithm would a Topological Sort make use of ?

* which algorithm is defined recursively out of either BFS or DFS ?

* What is a Digraph ?

* What is the difference between a connected graph and a 
disconnected graph ?

* How many types of connectedness can a Directed Graph have ?

* What is the meaning of weakly connected graph ?
 
* Describe the Shortest Path Compositionality Property ?

* How many bridges of Konigsberg were there back in the day when the problem was introduced to Edgar W. Dijkstra ?
:D you nerd

* Name 3 common applications of Graph theory
a)
b)
c)