Scribd
Upload
142 views5 pages

Graph Algorithms: Problems and Solutions

This document contains sample exam questions and answers related to graphs and graph algorithms. It includes questions about identifying whether a diagram represents a graph based on the textbook definition, representing graphs using adjacency lists, applying the source-removal algorithm to solve topological sorting, and performing breadth-first search and depth-first search on graphs. The document provides the definitions, diagrams, and step-by-step workings for analyzing graphs and solving problems using common graph algorithms.

Uploaded by

api-427618266
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
142 views5 pages

Graph Algorithms: Problems and Solutions

This document contains sample exam questions and answers related to graphs and graph algorithms. It includes questions about identifying whether a diagram represents a graph based on the textbook definition, representing graphs using adjacency lists, applying the source-removal algorithm to solve topological sorting, and performing breadth-first search and depth-first search on graphs. The document provides the definitions, diagrams, and step-by-step workings for analyzing graphs and solving problems using common graph algorithms.

Uploaded by

api-427618266
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1. (5 points) (a) Based on our textbook’s definition, is this a graph? (True/False) Explain to support your answer.

a e

b c f

Answer:
False, since vertices and edges in the graph definition are sets, they can't have duplicates while this image has
duplicate edge (a, e), (a, e)

(b) Based on our textbook’s definition, is this a graph? (True/False) Explain to support your answer

b c

d e f g

Answer:
True, this is directed graph without duplicate edges and without duplicate vertices.

2. (5 points) Represent the following graph in the adjacency list as you learned in the class. Note that there are
six vertices (= A, B, C, D, E, and F) in the graph.

Answer:
A→C
B→A→C
C→D
D→C
E→F
F
3. (5 points) Represent the following weighted digraph in an adjacency list as we covered in the class.

2
A B
1
4
5 3 6
8
C D
7

A → B(2) → D(8)
B → A(1) → C(4) → D(6)
C → A(5) → B(3)
D → C(7)

2. (5 points) Apply the source-removal algorithm to solve the topological sorting problem for the
following digraph. You should explain your answer and present the topological order clearly.

Answer: f → e → a → b → c → d → g
Every time we have to delete a source without incoming edges (following alphabetical ascending order
convention).
3.
5. (10 points) Consider the following directed graph.
Starting at vertex a, traverse the graph using the breadth-first search algorithm. You should present the mark
array and BFS tree with only tree edges as we covered in the class. For the algorithm, you have to use our
convention of the class (= ascending order for the alphabetical characters).
6. (10 points) Consider the following graph.

a b d h

e f c g

Starting at vertex a, traverse the graph using the depth-first search (DFS) algorithm. After that, you should
present a mark array and a depth-first search tree with only tree edges. For the algorithm, you have to use our
convention of the class (= ascending order for the alphabetical characters).

You might also like