LN10 Minimum Spanning Tree, Directed cycles and Topological Order Flashcards
What is the goal of graph traversal in algorithms?
Graph traversal techniques aim to visit all nodes in a graph efficiently, forming the basis for many graph algorithms.
What is the Breadth-First Search (BFS) algorithm?
BFS starts at a node, explores all its neighbors, and then moves to the neighbors of those neighbors, processing nodes layer by layer using a queue.
How does BFS determine shortest paths in graphs?
In graphs with unit edge lengths, BFS partitions nodes into layers where each layer represents nodes at increasing distances from the start node, naturally yielding the shortest paths.
What is a BFS tree?
A BFS tree is a tree formed by including edges only when a node is discovered for the first time. It provides a path from the root to all reachable nodes.
Describe Depth-First Search (DFS) and its key characteristic.
DFS starts at a node, explores as far as possible down each path before backtracking, typically implemented recursively or using a stack.
What is a DFS tree, and what are “tree edges”?
A DFS tree includes edges where each DFS function call leads to a recursive call. Tree edges are those that connect nodes along these paths, forming a tree structure.
What types of edges can exist in a DFS traversal of directed graphs?
In directed graphs, DFS edges include tree edges, forward edges (to descendants), back edges (to ancestors), and cross edges (to nodes on earlier paths).
How does BFS help in solving the connectivity problem in undirected graphs?
BFS can identify all nodes in the connected component containing the start node, efficiently testing connectivity in O(m) time by reaching all nodes if the graph is connected.
What is the difference between “connected” and “strongly connected” in graph theory?
An undirected graph is connected if a path exists between any two nodes. A directed graph is strongly connected if there is a directed path between every pair of nodes.
Explain the process for determining strong connectivity in directed graphs.
Run BFS twice from one node—once on the original graph and once on the reversed graph. If both traversals reach all nodes, the graph is strongly connected.
How is the 2-coloring problem related to BFS?
For bipartite graphs (2-colorable), BFS can be used to alternate colors across layers, ensuring adjacent nodes are colored differently, solvable in O(m) time.
Why is k-coloring NP-complete for k ≥ 3?
Unlike 2-coloring, k-coloring for k ≥ 3 does not have a straightforward traversal solution, and it is NP-complete, proven by reduction from 3SAT.
What is the Minimum Spanning Tree (MST) problem?
The MST problem seeks a subset of edges that connects all nodes with minimal total edge cost, important in network design for cost efficiency.
In which scenarios are BFS and DFS inefficient for graph traversal?
Using adjacency matrices for BFS and DFS is generally inefficient (O(n²) time) due to the need to examine all potential edges, especially in sparse graphs.
Give an example of where BFS and DFS might produce different results in traversal.
In the example graph with nodes {a, b, c, d} and edges {ab, ac, bc, bd}, BFS creates unique layers, while DFS results vary based on the order of edge exploration.
