Which of the following is the BEST representation of a graph when the number of edges is much smaller than the number of vertices?
Adjacency Matrix
Incidence Matrix
Edge List
Adjacency List
What is the time complexity of performing a Breadth-First Search on a graph with 'V' vertices and 'E' edges?
O(V)
O(V * E)
O(V + E)
O(E)
What does a '1' represent in an adjacency matrix of an undirected graph?
The weight of the edge.
The presence of an edge between two vertices.
The direction of the edge.
The degree of the vertex.
A graph is said to be __________ if there is a path from any vertex to any other vertex.
Connected
Disconnected
Complete
Bipartite
Which traversal algorithm is best suited for detecting cycles in a graph?
Prim's Algorithm
Depth First Search (DFS)
Kruskal's Algorithm
Breadth First Search (BFS)
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?
Stack
Linked List
Queue
Heap
Which of the following statements accurately describes a key difference between Depth-First Search (DFS) and Breadth-First Search (BFS)?
DFS is typically used for finding shortest paths in unweighted graphs, while BFS is used for cycle detection.
DFS is always more efficient than BFS in terms of time complexity.
DFS uses a queue, while BFS uses a stack for traversal.
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.
If every vertex in a graph has an even degree, what can we conclude about the graph?
It must have an Eulerian cycle.
It must be bipartite.
It must be directed.
It must be a tree.
In the context of graph traversal, what does 'backtracking' refer to in Depth-First Search (DFS)?
Returning to the parent node after exploring all descendants of a node.
Skipping certain branches of the graph to improve efficiency.
Using a heuristic function to guide the search towards the goal node.
Revisiting already explored nodes to find alternative paths.
Adding an edge between two vertices in an undirected graph always:
Increases the number of connected components.
May increase or decrease the number of connected components.
Creates a cycle.
Decreases the number of connected components.