Hikmat Flashcards
What is a graph?
A set of vertices and a set of edges connecting the vertices
What’s usually associated with each edge?
A weight or cost
What makes a path simple?
If all vertices, except possibly the first and last, are distinct
What are the two ways to represent a graph?
- Adjacency matrix
- Adjacency list
What is the memory requirement of an adjacency list?
O(|E| + |V|)
What is the memory requirement of an adjacency matrix?
O(|V^2|)
What is Breadth First Search (BFS)?
An algorithm that systematically “discovers” all vertices that can be reached from S (source node)
What is the total cost of BFS?
O(|V| + |E|)
Why is BFS not Θ(|V| +|E|)?
Some vertices may not be reachable from s
What is Depth First Search (DFS)?
Edges are explored out of the most recently discovered node, going deeper whenever possible
How do BFS and DFS differ?
A single run of DFS is guaranteed to visit all nodes even if the graph has more than one connected component
What is the total cost of DFS?
Θ(|E| + |V|)
What is topological sorting?
A linear ordering of the nodes of directed graph such that every edge from node u to node v, u comes before v in the ordering
What is a connected component of an undirected graph?
A subgraph in which there is a path between every pair of vertices
What is Relaxation?
Relaxing an edge (u, v) means testing if we can improve the shortest path cost of v by using the edge (u, v)
What is the complexity of Kruskal’s Algorithm?
It is O(mlogn) with n = |V| and m = |E|
What is the difference between Kruskal’s algorithm and Prim’s algorithm?
Kruskal’s is edge based while Prim’s is vertex based
How does Prim’s algorithm work?
- Maintains a set S of vertices, initially containing a single vertex s which could be any vertex in V
- At each iteration we consider the sets S and V - S
- Find the edge (u, v) with minimum weight such that u ∈ S and v ∈ V - S
- Add v to S and (u, v) to T
What is the time complexity of Prim’s algorithm?
O(m log n)
What is a cut?
A cut (S, V - S) of the graph G is a partition of V
How does Bellman-Ford Algorithm work?
- Computes the shortest path from a given source to all other nodes in the graph
- IT works with negative weights and can detect negative cycles
- It uses the function RELAX to compute the shortest path
- RELAX is applied to all edges in the graph |V | - 1 times
What is the time complexity of Bellman-Ford?
O(|V| x |E|)
How does Dijkstra’s algorithm work?
- Works when all weights are positive
- Faster than Bellman-Ford
- Maintains a set S of nodes whose shortest paths have been determined
- All other nodes are kept in a min-priority queue to keep track of the next node to process
When does Dynamic Programming apply?
- Optimal substructure
- Overlapping subproblems
What are the two ways it can solved?
With memorization or bottom-up solutions
