Graph

--------普林斯顿大学算法公开课笔记

一、Definition

Graph: set of vertices connected pairwise by edges

Path: sequence of vertices connected by edges

Cycle: path whose first and last vertices are the same

二、Problems

Is there a path between s and t ?   [Path] 

What is the shortest path between s and t ?   [Shortest path] 

Is there a cycle in the graph?   [Cycle] 

Is there a cycle that uses each edge exactly once?  [Euler tour] 

Is there a cycle that uses each vertex exactly once?   [Hamilton tour] 

Is there a way to connect all of the vertices?   [Connectivity] 

三、Representation

how to represent a graph?  

==> 1.lists of edges 

0 - 1,0 - 2, 3 - 4,...

==> 2. adjacency-matrix 

data structure: two-dimension array

==> 3. adjacency-list

data structure:  vertex table,edge table

notations: V(num of vertices) E(num of edges)

[C++ code] implementation of adjacent matrix and adjacent lists

四、Search

1.Depth-First Search

[idea] To visit a vertex v:

a. marked vertex v as visited

b.recursively visit all unmarked vertices adjacent to v

[C++ code] implementation of DFS

2.Breadth-First Search       used to find shortest path

[idea]From source vertex s,put s onto a FIFO queue,mark s as visited,then repeat until the queue is empty:

a.remove the least recently added vertex v

b. add all of v's unmarked neighbors to the queue,and mark them as visited

[C++ code] implementation of BFS

五、Connected Components

1.Connected components: a maximal set of connected vertices

2.Connectivity: whether v is connected to w or not

3.find connected components in graph G

[idea] Initialize all vertices as unmarked,for each unmarked vertex v,run DFS to identify all vertices discovered as part of the same component.

[C++ code] to find connected components in G

4. connectiviy queries

[idea] Work out all connected components in G.If vertex v and vertex w are in the same connected component,then they are connected.

[C++ code] work out the connectivity problem