Graph Algorithms Flashcards
What are the 2 sets of graphs
V, set of vertices/nodes
E, set of edges/links
What is the degree of a vertex
The number of edges connected to it
What are digraphs
Directed graphs, edges are pointed
What is a simple path
All nodes are distinct
What is the sum of weights of paths called
Path cost
What is a graph without cycles called
Directed Acyclic Graph (DAG)
What is a connected graph
every node has a way to get to every other node
what is a complete graph
every single node is connected
what is a graph that has lots of edges vs few edges called
dense vs sparse
What is the 2D array representing a graph called
Adjacency Matrix
Can topological sorts have multiple answers
yes
What kind of graph are topological sorts for
DAGs
What is the topological sort algorithm
List the in-degree for all nodes and softly delete each node with 0 in-degree while decrementing what it is pointing, repeat
What is the time complexity of topological sort using a list
O(V^2)
What is the time complexity of topological sorting using a queue
O(E+V)
What is the time complexity of Dijkstra’s algorithm
O(ElogV)
What kind of search is finding shortest path for unweighted graphs and what is the time complexity of
bread-first, O(E+V)
What makes a digraph strongly connected
there is a path from any node to any other node
What is the running time for unweighted shortest path using
O(v^2), O(E+V) if using level-order tree with queue and adjacency list
What is the running time for Dijkstra’s algorithm for shortest path of weighted graph
O(E+V^2), or if using priority queue with decreaseKey then O(ElogV)
What does does finding the minimal subset of edges result in
A tree (spanning tree problem)
what is running time of Prim’s minimum spanning tree
O(V^2), or O(ElogV) with binary heaps
when is Prim’s minimum spanning tree good to use
if the graph is dense
what is running time of Kruskal’s algorithm
O(ElogE) using union/find with heap
when is Kruskal’s algorithm good to use
if the graph is sparse
an undirected graph is connected only if …
a DFS from any node visits every node
what type of algorithm for graphs results in O(V^2), and what would make it better
greedy, using queues
