CS130-lecture-20201202

Exercise solutions #

IMAGE IMAGE

On the whiteboard:

IMAGE

Start on vertex 0

IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE

Move onto vertex 2, need to exhaust all vertices

IMAGE IMAGE

Move onto vertex 7

IMAGE IMAGE IMAGE

The reverse post order is : 8, 7, 2, 3, 0, 6, 9, 10, 11, 12, 1, 5, 4

IMAGE

Graph cont. #

IMAGE IMAGE IMAGE

These are considered strongly connected. Also considered a strongly connected digraph.

IMAGE

5 strongly connected components.

IMAGE

Reversed graphs are still strongly connected in the same components. A reversed graph’s reverse post order will show each component. Visit each vertex in the reverse post order and keep track of which ones have been visited, each vertex will be able to reach all the other vertex in the same component.

IMAGE

IMAGE

A strongly connected digraph has 1 strong component.

A DAG has (V) strong components.

Weighted graphs #

IMAGE

If a graph is not connected, it doesn’t have a spanning tree.

For an edge-weighted graph with (V) vertices, a MST has (V - 1) edges.

IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE

Another look at the implementation:

IMAGE

Worst case time comes from the pq operation.

IMAGE

This type of graph gives the maximum size of the pq.

IMAGE IMAGE

Skipping the eager prim implementation

IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE

The for loop on 13 is O(ElgE). The union find is O(ElgV). and since E is greater than or equal to the vertices minus 1, the overall runtime is O(ElgE).

IMAGE

It won’t connect v and w because it will create a cycle.

Edge weighted digraphs #

IMAGE IMAGE IMAGE IMAGE IMAGE IMAGE