Which of the following graph representations is most efficient for checking if two vertices are adjacent?
Adjacency Matrix
Incidence Matrix
Edge List
Adjacency List
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.
Depth-First Search (DFS)
Neither DFS nor BFS can determine if a path exists between two nodes.
Breadth-First Search (BFS)
Which graph traversal algorithm uses a queue to visit vertices?
Bellman-Ford Algorithm
Breadth First Search (BFS)
Dijkstra's Algorithm
Depth First Search (DFS)
How does the iterative implementation of Depth-First Search (DFS) typically differ from its recursive counterpart?
The iterative and recursive approaches produce fundamentally different traversal orders.
The iterative approach is not suitable for traversing graphs with cycles.
The iterative approach uses a stack to mimic the function call stack used in recursion.
The iterative approach is generally less efficient in terms of space complexity than recursion.
What is a cycle in a graph?
A path that starts and ends at the same vertex.
A vertex with a degree of 1.
A graph that is not connected.
The longest path between any two vertices.
Removing a vertex from a graph also requires you to remove:
All cycles in the graph.
All vertices connected to it.
The vertex with the highest degree.
All edges connected to it.
Which of the following is the BEST representation of a graph when the number of edges is much smaller than the number of vertices?
In a directed graph, if vertex A has an outgoing edge to vertex B, then:
There must be an edge from vertex B to vertex A.
Vertex A is adjacent to vertex B.
Vertex B is adjacent to vertex A.
Vertex A and B have the same degree.
What data structure is typically used to implement the core of a Breadth-First Search (BFS) algorithm?
Stack
Queue
Linked List
Heap
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?