Questions and Answers
What is the runtime of DFS?
What is the runtime of BFS?
What method do you use to check for a removable vertex?
DFS
What method do you use to check if a graph is bipartite?
Signup and view all the answers
What function checks if a path exists?
Signup and view all the answers
How do you find the shortest cycle in a graph?
Signup and view all the answers
What method do you use to count connected components?
Signup and view all the answers
What method do you use to find the longest connected component?
Signup and view all the answers
What method do you use to find the shortest path in an unweighted graph?
Signup and view all the answers
What is the Topological Sort method known as 'Magic'?
Signup and view all the answers
What is the runtime of Tarjan's Topo Algorithm?
Signup and view all the answers
What is Kahn's Algorithm used for in Topological Sort?
Signup and view all the answers
What is the runtime of Kahn's Topo Algorithm?
Signup and view all the answers
What is used to check for time consistency in a graph?
Signup and view all the answers
What is the method to find all Strongly Connected Components?
Signup and view all the answers
What is the runtime of Kosaraju's Algorithm?
Signup and view all the answers
How do you find a mother vertex using indegree 0?
Signup and view all the answers
What algorithm is used for finding the shortest path with weights?
Signup and view all the answers
What is the runtime of Dijkstra's Algorithm?
Signup and view all the answers
What is the runtime of Dijkstra's Algorithm if the graph is connected?
Signup and view all the answers
How can you prove Dijkstra's algorithm?
Signup and view all the answers
What is the runtime for extracting min once per vertex in Dijkstra's Runtime?
Signup and view all the answers
What is the runtime for building the heap in Dijkstra's algorithm?
Signup and view all the answers
What is the runtime for decreasing the key E times in Dijkstra's algorithm?
Signup and view all the answers
What method do you use to find the shortest path in a directed acyclic graph (DAG)?
Signup and view all the answers
What is the method for finding the longest path in a DAG?
Signup and view all the answers
What algorithm is similar to Dijkstra's for Minimum Spanning Tree?
Signup and view all the answers
What is the runtime of Prim's MST algorithm?
Signup and view all the answers
What method is used for Minimum Spanning Tree by adding edges with Union-Find?
Signup and view all the answers
What is the runtime of Kruskal's MST algorithm?
Signup and view all the answers
What method is used for Minimum Spanning Tree by removing edges?
Signup and view all the answers
What is the runtime of Reverse-Delete MSTs algorithm?
Signup and view all the answers
What principle is used to prove Kruskal's algorithm?
Signup and view all the answers
What principle is used to prove Prim's algorithm?
Signup and view all the answers
What principle is used to prove Reverse-Delete algorithm?
Signup and view all the answers
How many nodes does the root of rank k have?
Signup and view all the answers
How many nodes are there at most of rank k?
Signup and view all the answers
What is the runtime for Huffman's algorithm?
Signup and view all the answers
What is the runtime for Binary Heap Insert?
Signup and view all the answers
Study Notes
Graph Algorithms Runtime Complexity
- Depth-First Search (DFS) runtime is O(n + m), where n is the number of vertices and m is the number of edges.
- Breadth-First Search (BFS) runtime is also O(n + m).
Graph Characteristics and Checks
- Removal of a vertex can be checked using DFS.
- To determine if a graph is bipartite, BFS is utilized.
Path and Cycle Determination
- The existence of a path can be verified using the HasPath function.
- The shortest cycle can be found by performing BFS from every vertex and checking the last edge.
- BFS is also used to count connected components and identify the longest connected component.
- BFS is optimal for finding the shortest path in unweighted graphs.
Topological Sorting Methods
- Tarjan's Algorithm provides a topological sort using a reverse DFS method.
- Kahn's Algorithm for topological sorting operates on vertices with an indegree of zero.
Algorithm Runtimes
- Both Tarjan's and Kahn's topological sort algorithms run in O(n + m).
- Dijkstra's Algorithm, used for finding the shortest path in weighted graphs, runs in O((V + E) log V) if the graph is connected, with V as vertices and E as edges.
Dijkstra's Specifics
- Proving Dijkstra's efficiency involves induction on the size of the path.
- Extracting the minimum once per vertex in Dijkstra's results in a time complexity of O(log V).
- Building the heap during Dijkstra's Algorithm takes O(V).
- Decreasing a key value E times in Dijkstra's runs in O(log V).
Directed Acyclic Graphs (DAG)
- To find the shortest path in a DAG, a topological sort is performed.
- The longest path in a DAG is computed as the shortest path multiplied by -1.
Minimum Spanning Tree (MST) Algorithms
- Prim's Algorithm, similar to Dijkstra's, has a runtime of O(m log n).
- Kruskal's MST algorithm, focused on adding edges, also runs in O(m log n).
- Reverse-Delete MST, which removes edges, operates with a runtime of O(m²).
Proving MST Algorithms
- Kruskal's and Prim's algorithms are proven using the Cut Property.
- The Reverse-Delete algorithm is demonstrated through the Cycle Property.
Union-Find Structures
- A root of rank k has at least 2^k nodes.
- There are at most n / 2^k nodes of rank k in a union-find structure.
Other Key Algorithms
- Huffman's Algorithm has a runtime of O(n log n) for constructing optimal prefix codes.
- Inserting into a binary heap has a runtime of O(log n).
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
Test your knowledge with flashcards from CIS 1210 Midterm 2. This quiz covers various algorithms and their runtimes, such as DFS and BFS, as well as properties of graphs. Perfect for preparing for your midterm exam in computer science.
