In a social network represented as a graph, what does the degree of a vertex signify?
The user's privacy settings.
The number of friends or connections a user has.
The number of groups the user belongs to.
The user's influence score.
In an undirected graph with 5 vertices, what is the maximum number of edges you can add without creating a cycle?
10
4
6
5
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)
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 and recursive approaches produce fundamentally different traversal orders.
The iterative approach uses a stack to mimic the function call stack used in recursion.
The iterative approach is not suitable for traversing graphs with cycles.
Which of the following graph representations is most efficient for checking if two vertices are adjacent?
Edge List
Adjacency Matrix
Adjacency List
Incidence Matrix
Which of these scenarios is BEST represented using a weighted graph?
Modeling the flow of information in a computer network.
Finding the shortest path between two cities on a road network with distances.
Storing the friendship relations between people on a social media platform.
Representing the hierarchical structure of a company.
A cycle in a graph that is not a simple cycle (visits a vertex more than once) is called a:
Path
Closed Walk
Circuit
Trail
Consider a graph where you want to find if a path exists between two given nodes. Which traversal algorithm would be generally more efficient for this task?
Breadth-First Search (BFS)
Depth-First Search (DFS)
Both DFS and BFS have the same efficiency for this task.
Neither DFS nor BFS can determine if a path exists between two nodes.
Which of the following statements accurately describes a key difference between Depth-First Search (DFS) and Breadth-First Search (BFS)?
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 is typically used for finding shortest paths in unweighted graphs, while BFS is used for cycle detection.
DFS uses a queue, while BFS uses a stack for traversal.
DFS is always more efficient than BFS in terms of time complexity.
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.
Assigning weights to edges based on whether they lead to visited nodes.
Using a special 'visited' flag or attribute within the node's data structure.
Maintaining a separate list or set of visited nodes.