A graph where edges have a direction associated with them is called a:
Directed Graph
Undirected Graph
Cyclic Graph
Weighted Graph
What data structure is typically used to implement the core of a Breadth-First Search (BFS) algorithm?
Queue
Stack
Heap
Linked List
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?
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 uses a queue, while BFS uses a stack for traversal.
DFS is always more efficient than BFS in terms of time complexity.
DFS is typically used for finding shortest paths in unweighted graphs, while BFS is used for cycle detection.
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 number of cycles in the graph will always decrease.
The graph may become disconnected.
The graph will always become disconnected.
In an undirected graph, if the sum of the degrees of all vertices is 30, how many edges are there in the graph?
Cannot be determined.
15
60
30
Which graph traversal algorithm uses a queue to visit vertices?
Dijkstra's Algorithm
Breadth First Search (BFS)
Depth First Search (DFS)
Bellman-Ford Algorithm
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?
Neither DFS nor BFS can determine if a path exists between two nodes.
Both DFS and BFS have the same efficiency for this task.
Breadth-First Search (BFS)
Depth-First Search (DFS)
Which of the following is NOT a characteristic of a bipartite graph?
It can be used to model matching problems.
Vertices can be divided into two disjoint sets.
It can have an odd-length cycle.
Edges can only connect vertices from different sets.
In an undirected graph with 5 vertices, what is the maximum number of edges possible?
25
10
20
5