Lecture 26: Graphs

CS61B

Intro

Graph Types

Graph Terminology

Graph Example

Graph Representation

Graph API

Graph Representation 1 : Adjacency Matrix

Order of growth of Runtime:

G.adj(i)returns a Iterable(like a set, list etc)

Graph representation 2: edge set (trivial)

Graph Representation 3: Adjacent lists (most popular)

runtime analysis:

Summary:

implementation:

Depth-First Traversal

Recursive method to check if s is connected to t:

Depth-first traversal definition:

good example for Depth-first Traversal:

Depth First Search Implementation

Graphs Intro Study Guide

B LEVEL:

1.

if we count .adj() as our cost model, runtime is Θ（V）；
if we count .print(), runtime is Θ（E）;

2.

注意一下啥叫tightest bound.

3.

3题和A LEVEL都不会