Which of the following scenarios is particularly well-suited for applying a Depth-First Search (DFS) algorithm?
Solving mazes or navigating through grid-based environments.
Finding the shortest path between two locations on a map.
Crawling and indexing web pages starting from a seed URL.
Simulating the spread of information or a virus in a social network.
What is the degree of a vertex in a graph?
The total number of vertices in the graph.
The length of the longest path starting from that vertex.
The number of edges connected to that vertex.
The number of self-loops on that vertex.
What is a common way to keep track of visited nodes during graph traversal to avoid cycles and infinite loops?
Using a special 'visited' flag or attribute within the node's data structure.
Assigning weights to edges based on whether they lead to visited nodes.
Maintaining a separate list or set of visited nodes.
Both options 1 and 3 are common and effective approaches.
Which of the following is NOT a characteristic of a bipartite graph?
It can be used to model matching problems.
It can have an odd-length cycle.
Edges can only connect vertices from different sets.
Vertices can be divided into two disjoint sets.
Which of the following statements accurately describes a key difference between Depth-First Search (DFS) and Breadth-First Search (BFS)?
DFS is always more efficient than BFS in terms of time complexity.
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 uses a queue, while BFS uses a stack for traversal.
DFS is typically used for finding shortest paths in unweighted graphs, while BFS is used for cycle detection.
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?
Heap
Queue
Stack
Linked List
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 has a priority value of 'i' in the BFS traversal order.
The node has 'i' neighbors in the graph.
The node is at a distance of 'i' edges away from the starting node.
The node is the i-th node discovered by the BFS algorithm.
Removing a vertex from a graph also requires you to remove:
The vertex with the highest degree.
All edges connected to it.
All vertices connected to it.
All cycles in the graph.
In a social network represented as a graph, what does the degree of a vertex signify?
The number of groups the user belongs to.
The number of friends or connections a user has.
The user's privacy settings.
The user's influence score.
Which of the following graph representations is most efficient for checking if two vertices are adjacent?
Adjacency Matrix
Adjacency List
Edge List
Incidence Matrix