Consider a graph where you want to find if a path exists between two given nodes. Which traversal algorithm would be generally more efficient for this task?
Both DFS and BFS have the same efficiency for this task.
Breadth-First Search (BFS)
Neither DFS nor BFS can determine if a path exists between two nodes.
Depth-First Search (DFS)
What is a common way to keep track of visited nodes during graph traversal to avoid cycles and infinite loops?
Maintaining a separate list or set of visited nodes.
Assigning weights to edges based on whether they lead to visited nodes.
Using a special 'visited' flag or attribute within the node's data structure.
Both options 1 and 3 are common and effective approaches.
Removing a vertex from a graph also requires you to remove:
All edges connected to it.
All cycles in the graph.
All vertices connected to it.
The vertex with the highest degree.
Which of the following is an advantage of using an adjacency matrix representation for a graph?
Efficient for sparse graphs.
Less memory usage for large graphs.
Faster to find all neighbors of a vertex.
Constant time edge existence check.
A cycle in a graph that is not a simple cycle (visits a vertex more than once) is called a:
Trail
Path
Closed Walk
Circuit
If every vertex in a graph has an even degree, what can we conclude about the graph?
It must be bipartite.
It must have an Eulerian cycle.
It must be a tree.
It must be directed.
Which of the following graph algorithms is best suited for finding the shortest path in a weighted graph?
Depth-First Search
Dijkstra's Algorithm
Topological Sort
Breadth-First Search
Which of the following is the BEST representation of a graph when the number of edges is much smaller than the number of vertices?
Edge List
Incidence Matrix
Adjacency List
Adjacency Matrix
In the context of graph traversal, what does 'backtracking' refer to in Depth-First Search (DFS)?
Using a heuristic function to guide the search towards the goal node.
Revisiting already explored nodes to find alternative paths.
Returning to the parent node after exploring all descendants of a node.
Skipping certain branches of the graph to improve efficiency.
Adding an edge between two vertices in an undirected graph always:
May increase or decrease the number of connected components.
Decreases the number of connected components.
Increases the number of connected components.
Creates a cycle.