Which of the following graph algorithms is best suited for finding the shortest path in a weighted graph?
Topological Sort
Depth-First Search
Dijkstra's Algorithm
Breadth-First Search
What data structure is typically used to implement the core of a Breadth-First Search (BFS) algorithm?
Stack
Queue
Linked List
Heap
What is a cycle in a graph?
The longest path between any two vertices.
A graph that is not connected.
A vertex with a degree of 1.
A path that starts and ends at the same vertex.
Which data structure is most efficient for checking if an edge exists between two vertices in a sparse graph?
Adjacency Matrix
Adjacency List
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?
Adding an edge between two vertices in an undirected graph always:
Creates a cycle.
Decreases the number of connected components.
May increase or decrease the number of connected components.
Increases the number of connected components.
Which of the following is NOT a characteristic of a bipartite graph?
It can have an odd-length cycle.
Vertices can be divided into two disjoint sets.
Edges can only connect vertices from different sets.
It can be used to model matching problems.
You are performing a Breadth-First Search on a graph. Which of the following best describes the order in which vertices are visited?
Alphabetical order
Increasing order of their degree (number of connections)
Vertices at the same distance from the source vertex are visited before moving to vertices further away
Random order
Which graph traversal algorithm uses a queue to visit vertices?
Breadth First Search (BFS)
Depth First Search (DFS)
Bellman-Ford Algorithm
Which type of graph is MOST suitable for representing a one-way system on a city map?
Weighted Graph
Directed Graph
Tree
Undirected Graph