Graph Algorithms

Question 1

5 typical operations of graphs as ADT

Answer 1

1. determine whether there is an edge between 2 given vertices
2. identify all edges
3. find all vertices adjacent to a given vertex
4. insert/delete a vertex
5. insert/delete an edge by 2 vertices of the graph

Question 2

3 data structures graphs can be based on

Answer 2

1. adjacency lists
2. adjacency matrix
3. incidence matrix

Question 3

describe adjacency matrix implementation

Answer 3

• for every vertex, there is a singly linked list of its neighbours
• lists are accessed using an array of vertices

Question 4

how are the matrixes implemented

Answer 4

2-d arrays

Question 5

space efficiency of adjacency lists

Answer 5

theta(n + m)

Question 6

space efficiency of adjacency matrix

Answer 6

theta(n^2)

Question 7

space efficiency of incidence lists

Answer 7

theta(nm)

Question 8

big theta of determining whether there is an edge between 2 given vertices for adjacency lists

Answer 8

deg(v)

Question 9

big theta of determining whether there is an edge between 2 given vertices for adjacency matrix

Answer 9

1

Question 10

big theta of determining whether there is an edge between 2 given vertices for incidence matrix

Answer 10

m

Question 11

big theta to identify all edges in an adjacency list

Answer 11

n + m

Question 12

big theta to identify all edges in an adjacency matrix

Answer 12

n^2

Question 13

big theta to identify all edges in an incidence matrix

Answer 13

nm

Question 14

big theta to find all vertices adjacent to a given vertex in an adjacency list

Answer 14

deg(v)

Question 15

big theta to find all vertices adjacent to a given vertex in an adjacency matrix

Answer 15

n

Question 16

big theta to find all vertices adjacent to a given vertex in an incidence list

Answer 16

m + ndeg(v)

Question 17

2 types of graph traversal algorithms

Answer 17

1. depth-first search (DFS)
2. breadth-first search (BFS)

Question 18

describe DFS

Answer 18

• algorthim selects a start vertex and marks it as visited
• goes as far down one path until it reaches the leaf node before starting to explore alternative paths
• visited nodes stored in a stack

Question 19

outputs of DFS

Answer 19

1. vertices printed in order of visit
2. depth-first numbering
3. DFS forest

Question 20

big theta of depth-first search

Answer 20

n + m

Question 21

big theta of DFS on an adjacency matrix

Answer 21

n^2

Question 22

describe BFS

Answer 22

• visits all neighbours of the start vertex and only after explores the vertices further away
• visited vertices kept in a queue

Question 23

big theta of BFS

Answer 23

n + m

Question 24

big theta of BFS as an adjacency matrix

Answer 24

n^2

Question 25

outputs of BFS

Answer 25

1. vertices printed in order of visit 2. BFS numbering 3. BFS forest

Question 26

applications of DFS & BFS

Answer 26

1. checking connectivity and identifying connected components 2. checking for a cycle 3. finding a path with the fewest numbner of edges between 2 given nodes - BFS preferred 4. finding articulation points of a graph

Question 27

describe topological sorting

Answer 27

process of assigning a linear ordering to the vertices of a directed acyclic graph so that if there is an arc from vertex v to w, then v appears before w in linear ordering

Question 28

how to achieve topological sorting

Answer 28

DFS

Question 29

pseudocode DFS

Question 30

pseudocode BFS