Monday, November 10, 2014

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)

Post a Comment

Follow by Email