What is the time complexity of performing a Breadth-First Search on a graph with 'V' vertices and 'E' edges?
O(V + E)
O(V)
O(E)
O(V * E)
In the context of graph traversal, what does 'backtracking' refer to in Depth-First Search (DFS)?
Revisiting already explored nodes to find alternative paths.
Skipping certain branches of the graph to improve efficiency.
Using a heuristic function to guide the search towards the goal node.
Returning to the parent node after exploring all descendants of a node.
In a connected graph, a path that visits every edge exactly once is known as:
Critical Path
Hamiltonian Path
Eulerian Path
Shortest Path
Which of the following is NOT a characteristic of a bipartite graph?
Vertices can be divided into two disjoint sets.
Edges can only connect vertices from different sets.
It can be used to model matching problems.
It can have an odd-length cycle.
Which of the following graph traversal algorithms is generally more suitable for finding the shortest path in an unweighted graph?
Both DFS and BFS are equally suitable.
Breadth-First Search (BFS)
Neither DFS nor BFS can find shortest paths in unweighted graphs.
Depth-First Search (DFS)
A graph is said to be __________ if there is a path from any vertex to any other vertex.
Complete
Bipartite
Disconnected
Connected
Adding an edge between two vertices in an undirected graph always:
Decreases the number of connected components.
May increase or decrease the number of connected components.
Increases the number of connected components.
Creates a cycle.
Which of the following graph algorithms is best suited for finding the shortest path in a weighted graph?
Breadth-First Search
Dijkstra's Algorithm
Depth-First Search
Topological Sort
Which of these scenarios is BEST represented using a weighted graph?
Storing the friendship relations between people on a social media platform.
Finding the shortest path between two cities on a road network with distances.
Representing the hierarchical structure of a company.
Modeling the flow of information in a computer network.
Removing a vertex from a graph also requires you to remove:
All edges connected to it.
All vertices connected to it.
The vertex with the highest degree.
All cycles in the graph.