Which data structure is most efficient for checking if an edge exists between two vertices in a sparse graph?
Adjacency Matrix
Linked List
Queue
Adjacency List
You remove an edge from a connected graph. What is a possible consequence of this action?
The number of cycles in the graph will always decrease.
The graph may become disconnected.
The number of edges and vertices in the graph will decrease.
The graph will always become disconnected.
In the context of Breadth-First Search (BFS), what does it mean for a node to be at 'level i' from the starting node?
The node is the i-th node discovered by the BFS algorithm.
The node is at a distance of 'i' edges away from the starting node.
The node has a priority value of 'i' in the BFS traversal order.
The node has 'i' neighbors in the graph.
In a directed graph, if vertex A has an outgoing edge to vertex B, then:
Vertex B is adjacent to vertex A.
There must be an edge from vertex B to vertex A.
Vertex A and B have the same degree.
Vertex A is adjacent to vertex B.
Which type of graph is MOST suitable for representing a one-way system on a city map?
Undirected Graph
Directed Graph
Tree
Weighted Graph
Which of the following is an advantage of using an adjacency matrix representation for a graph?
Less memory usage for large graphs.
Faster to find all neighbors of a vertex.
Efficient for sparse graphs.
Constant time edge existence check.
Removing a vertex from a graph also requires you to remove:
The vertex with the highest degree.
All vertices connected to it.
All cycles in the graph.
All edges connected to it.
What is the time complexity of performing a Breadth-First Search on a graph with 'V' vertices and 'E' edges?
O(V + E)
O(E)
O(V)
O(V * E)
What data structure is typically used to implement the core of a Breadth-First Search (BFS) algorithm?
Heap
Stack
Which of the following statements accurately describes a key difference between Depth-First Search (DFS) and Breadth-First Search (BFS)?
DFS explores a path as far as possible before backtracking, while BFS explores all neighbors at the current level before moving to the next level.
DFS is typically used for finding shortest paths in unweighted graphs, while BFS is used for cycle detection.
DFS uses a queue, while BFS uses a stack for traversal.
DFS is always more efficient than BFS in terms of time complexity.