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.
Removing a vertex from a graph also requires you to remove:
The vertex with the highest degree.
All cycles in the graph.
All edges connected to it.
All vertices connected to it.
In a directed graph, if vertex A has an outgoing edge to vertex B, then:
Vertex A is adjacent to vertex B.
Vertex B is adjacent to vertex A.
Vertex A and B have the same degree.
There must be an edge from vertex B to vertex A.
You remove an edge from a connected graph. What is a possible consequence of this action?
The number of edges and vertices in the graph will decrease.
The graph will always become disconnected.
The number of cycles in the graph will always decrease.
The graph may become disconnected.
Which of the following is NOT a characteristic of a bipartite graph?
Edges can only connect vertices from different sets.
It can be used to model matching problems.
Vertices can be divided into two disjoint sets.
It can have an odd-length cycle.
How does the iterative implementation of Depth-First Search (DFS) typically differ from its recursive counterpart?
The iterative approach is generally less efficient in terms of space complexity than recursion.
The iterative approach is not suitable for traversing graphs with cycles.
The iterative approach uses a stack to mimic the function call stack used in recursion.
The iterative and recursive approaches produce fundamentally different traversal orders.
You are performing a Breadth-First Search on a graph. Which of the following best describes the order in which vertices are visited?
Vertices at the same distance from the source vertex are visited before moving to vertices further away
Increasing order of their degree (number of connections)
Random order
Alphabetical order
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
In an undirected graph with 5 vertices, what is the maximum number of edges you can add without creating a cycle?
4
10
5
6
In the context of graph traversal, what does 'backtracking' refer to in Depth-First Search (DFS)?
Skipping certain branches of the graph to improve efficiency.
Returning to the parent node after exploring all descendants of a node.
Using a heuristic function to guide the search towards the goal node.
Revisiting already explored nodes to find alternative paths.