Graphs

Question 1

When is an graph connected?

Answer 1

• undirected
• > =1 vertex
• there’s a path between every pair of vertices

Question 2

What is the complexity of Dijkstra’s shortest path algorithm when using an Adjacency list and PQ?

Answer 2

O((n+e)*log(n))

Question 3

Dijkstra pseudo code

Answer 3

(min distance from v to all)
while PQ not empty
 -remove u with min distance from PQ
 -for each adjacent vertex z
  -if D[u] +w(u,z)

Question 4

What kinda graph does Bellman-Ford shortest path algorithm work on?

Answer 4

Directed

Question 5

What makes Bellman-Ford different from Dijkstra?

Answer 5

negative weights allowed

Question 6

Complexity of Bellman-Ford algorithm?

Answer 6

O(n*e)

Question 7

How would you define a graph (informal)?

Answer 7

A set of nodes

• containing some USEFUL INFOrmation
• connected by edges

Question 8

How would you define a graph (formal)?

Answer 8

G(E,v)

• Set of V vertices
• Collection E oF PAIRS of vertice, edges

Question 9

What is the complexity of Dijkstra when using a list as a priority queue?

Answer 9

O(n^2)

Question 10

When is a digraph strongly connected?

Answer 10

if v is reachable from u, u is reachable from v

Question 11

What is the transitive closure of a graph G?

Answer 11

• G* that has the same vertices as g

- wherever there’s a path from (u,v) in G, G* has an edge

Question 12

What is the algorithm to compute the transitive closure called?

Answer 12

Floyd-Warshall

Question 13

The floyd warshall algorithm makes an initial copy of G and then traverses all nodes and their reachable pairs.

What 3 conditions needs to hold for it to add a directed edge (Vi,Vj) to Gk?

Answer 13

Edge (Vi,Vj) exists in Gk-1 (prev graph)
Edge (Vj,Vk) exists in Gk-1
Edge doesn’t already exist in Gk

Question 14

What is the asymptotic time complexity of the Floyd Warshall algorithm?

Answer 14

O(n^3)

Question 15

What is the degree of a vertex?

Answer 15

number of edges incident to it

Question 16

What does a spanning subgraph have?

Answer 16

Same nodes but a subset of edges

Question 17

What is a forest?

Answer 17

graph without cycles

Question 18

What is traversal?

Answer 18

A systematic procedure for visiting all edges and nodes in a graph

Question 19

Which is recursive, DFS or BFS?

Answer 19

DFS

Question 20

What do nodes of a level in BFS have in common?

Answer 20

same distance from a fixed node

Question 21

Both BFS and DFS have the same complexity which is?

Answer 21

O(n+e)

Question 22

How are live objects signified in the mark and sweep algorithm?

Answer 22

mark

Question 23

How is the digraph connected to the mark and sweep algorithm?

Answer 23

Each object in memory heap is a vertex

Each reference is an edge

Question 24

What does the mark phase of mark and sweep involve?

Answer 24

1.Directed DFS on root objects to identify live objects

Question 25

What does the sweep phase involve?

Answer 25

1. Sweep through Memory heap

2. Reclaim space from unmarked objects

Question 26

What is a eulerian trail or path?

Answer 26

A path in a finite graph the visits every Edge Exactly once

Question 27

What is a eulerian circuit in a graph?

Answer 27

A eulerian trail that starts and ends at the same vertex

Question 28

What is the chinese postman problem?

Answer 28

Find a shortest closed path (or circuit) that visits every edge of a connected undirected graph

Question 29

What is the eulerian trail’s connection to the CPP?

Answer 29

IT is the optimal solution