Graph Theory Quiz

What is the primary purpose of a graph in computer science?

• To create visual graphics

• To perform arithmetic operations

• To represent relationships between objects

• To store data in a linear format

Which of the following is a common way to store a graph?

• Hash table

• Binary tree

• Adjacency matrix

• Array list

In an adjacency matrix, what does a value of 1 indicate?

• A vertex is isolated

• An edge exists between vertices

• The graph is directed

• No edge between vertices

What is the main characteristic of an undirected graph's adjacency matrix?

• It has a diagonal of ones

• It contains only zeros

• It is symmetric

• It is asymmetric

Which algorithm is used for depth-first search (DFS)?

• Backtracking

• Breadth-first search

• Dijkstra's algorithm

• Recursive traversal

What does a spanning tree of a connected undirected graph contain?

• All vertices and some edges

• Only the longest path

• All edges and no vertices

• A cycle of all vertices

What is the goal of a minimum spanning tree (MST)?

• To connect all vertices with the least number of edges

• To minimize the total edge weight

• To find the shortest path between two vertices

• To create a cycle with all vertices

Which algorithm is used to find the shortest path in a graph?

• Dijkstra's algorithm

• Kruskal's algorithm

• Depth-first search

• Prim's algorithm

In breadth-first search (BFS), which vertices are visited first?

• All vertices in a random order

• Only leaf vertices

• Only the deepest vertices

• All adjacent vertices of the starting vertex

What is the time complexity of Dijkstra's algorithm using a priority queue?

• O(E log V)

• O(V^2)

• O(V log V)

• O(E + V)