What is a common way to keep track of visited nodes during graph traversal to avoid cycles and infinite loops?
Both options 1 and 3 are common and effective approaches.
Using a special 'visited' flag or attribute within the node's data structure.
Maintaining a separate list or set of visited nodes.
Assigning weights to edges based on whether they lead to visited nodes.
Which of the following scenarios is particularly well-suited for applying a Depth-First Search (DFS) algorithm?
Finding the shortest path between two locations on a map.
Solving mazes or navigating through grid-based environments.
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.
Removing a vertex from a graph also requires you to remove:
All cycles in the graph.
All vertices connected to it.
All edges connected to it.
The vertex with the highest degree.
What data structure is typically used to implement the core of a Breadth-First Search (BFS) algorithm?
Queue
Linked List
Heap
Stack
What does a '1' represent in an adjacency matrix of an undirected graph?
The direction of the edge.
The degree of the vertex.
The weight of the edge.
The presence of an edge between two vertices.
You remove an edge from a connected graph. What is a possible consequence of this action?
The graph will always become disconnected.
The number of cycles in the graph will always decrease.
The number of edges and vertices in the graph will decrease.
The graph may become disconnected.
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 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.
Which type of graph is MOST suitable for representing a one-way system on a city map?
Undirected Graph
Directed Graph
Tree
Weighted Graph
A graph is said to be __________ if there is a path from any vertex to any other vertex.
Complete
Disconnected
Bipartite
Connected