Week 8

Question 1

Implementations to store Graphs

Answer 1

Advancency List. Each node mapped to a List of adjacent nodes
Edge Set: each node mapped to a set of Edges containing source, destination and weight of edge

Question 2

Graph Travesal Patterns

Answer 2

Breadth First

Depth First

Question 3

Breadth First

Answer 3

Start with source node
Visist all its neighbors
Then visit all their neihbors
etc. until target node found

Question 4

What does Breadth first algorithm guarantees

Answer 4

That we find always shortest path

Question 5

Depth First

Answer 5

Start at source node
visit one of its neigbors
then visit one of its neighbor
If node has no neighbors, or all already visited, go back to previous node and visit the next neighbor not visited

	private boolean doDfs(String start, String elementToFind) {
		if (start.equals(elementToFind)) {
			return true;
		} else {
			marked.add(start);
			for (String neighbor : getNodeNeighbors(start)) {
				if (!marked.contains(neighbor) && 
				    doDfs(neighbor, elementToFind))
	             return true;
			}
			return false;
		}
	}

Question 6

How many times is an edge examined in DFS

Answer 6

At most twice for undirected, and at most once for directed

Question 7

Time Complexity of BFS and DFS

Answer 7

Both O (V + E)
V = # vertices
E = # Edgeds

Question 8

BFS vs DFS which more efficient

Answer 8

Space wise DFS as it only needs to maintained data structure for marked. BFS additionally needs to maintain one for toExplore

Question 9

When use DFS

Answer 9

Find directed cycle or identifying SCC

Question 10

Is a cycle C in a graph a valid path?

Answer 10

A path is defined as a list of nodes from a start node to an end node in which each successive pair of nodes is connected by an edge. The start and end nodes being the same does not violate the definition of a path.

Question 11

Min number of edges for G to be connected

Answer 11

n-1

Question 12

Given an undirected/directed graph G with n nodes, what is the maximum number of edges possible for G if no nodes have self-loops (edges that connect a node to itself)?

Answer 12

n(n-1)/2 = undirected

n(n-1) = directed