

In [2]:

    
# %load ../../preconfig.py
%matplotlib inline
import matplotlib.pyplot as plt
import seaborn as sns
sns.set(color_codes=True)
plt.rcParams['axes.grid'] = False

#import numpy as np
#import pandas as pd
#import itertools

import logging
logger = logging.getLogger()

22 Elementary Graph Algorithms

This chapter presents methods for representing a graph and for searching a graph.

22.1 Representations of graphs

adjacency-list: sparse graphs
- pros: save memory.
adjacency-matrix: dense graphs
- pros: tell quickly if there is an edge connecting two given vertices.
- $A = A^T$, in some applications, only store half of entries.



In [4]:

    
plt.figure(figsize=(12,8))
plt.imshow(plt.imread('./res/fig22_2.png'))









    Out[4]:





<matplotlib.image.AxesImage at 0x10a6e8780>



In [5]:

    
# Exercises

22.2 Breadth-first search

Given a graph $G = (V, E)$ and a distinguished source vertex $x$. The breadth-first search computes the distance (smallest number of edges) from $s$ to each reachable vertex.

For any vertex $v$ reachable from $s$, the simle path in the breadth-first tree from $s$ to $v$ corresponds to "shortest path" from $s$ to $v$ in $G$.



In [6]:

    
plt.imshow(plt.imread('./res/BFS.png'))









    Out[6]:





<matplotlib.image.AxesImage at 0x10a748f98>



In [8]:

    
plt.figure(figsize=(8,12))
plt.imshow(plt.imread('./res/fig22_3.png'))









    Out[8]:





<matplotlib.image.AxesImage at 0x10ce68978>



In [9]:

    
# Exercises

22.3 Depth-first search

Depth-first search explores edges out of the most recently discovered vertex $v$ that still has unexplored edges leaving it.

depth-first search may produce several trees $\to$ we use the predecessor subgraph: $G_{\pi} = (V, E_{\pi})$, where $E_{\pi} = \{ (v.{\pi}, v) : v \in V \text{ and } v.{\pi} \neq \operatorname{NIL} \}$.

Each vertex is initially white, is grayed when it is discovered in the search, and is blacked when it is finished.
depth-first search also timestamps each vertex.



In [2]:

    
plt.imshow(plt.imread('./res/DFS.png'))









    Out[2]:





<matplotlib.image.AxesImage at 0x1098bd898>



In [4]:

    
plt.figure(figsize=(10,12))
plt.imshow(plt.imread('./res/fig22_4.png'))









    Out[4]:





<matplotlib.image.AxesImage at 0x10bcec630>

properties

the predecessor subgraph $G_{\pi}$ does indeed form a forest of trees.
discovery and finishing times have parenthesis structure.
classification of edges:
- Tree edges edges in the depth-first forest $G_{\pi}$. WHITE
- Back edges edges $(u,v)$ connecting a vertex $u$ to an ancestor $v$ in a depth-first tree. GRAY
- Forward edges those nontree deges $(u,v)$ connecting a vertex $u$ to a descendant $v$ in a depth-first tree. BLACK
- Cross edges all other edges BLACK



In [7]:

    
plt.figure(figsize=(10,20))
plt.imshow(plt.imread('./res/fig22_5.png'))









    Out[7]:





<matplotlib.image.AxesImage at 0x10cc12c18>



In [8]:

    
# Exercises

22.4 Topological sort

used for directed acyclic graph.

A topological sort of a dag $G = (V, E)$ is a linear ordering of all its vertices such that if $G$ contains an edge $(u,v)$, then $u$ appears before $v$ in the ordering.

Many applications use directed acyclic graphs to indicate precedences among events.



In [4]:

    
plt.imshow(plt.imread('./res/tolo.png'))









    Out[4]:





<matplotlib.image.AxesImage at 0x1095ffc18>



In [6]:

    
plt.figure(figsize=(12,8))
plt.imshow(plt.imread('./res/fig22_7.png'))









    Out[6]:





<matplotlib.image.AxesImage at 0x10a794dd8>

22.5 Strongly connected components

classic application of depth-first search: decomposing a directed graphh into strongly connectd components.

a strong connected component of a directed graph $G = (V, E)$ is a maximal set of vertices $C \subseteq V$ such that vertices $u$ and $v$ are reachable from each other for every pair of verticies $u$ and $v$ in $C$.

define: $G^T = (V, E^T)$, where $E^T = { (u, v) : (v, u) \in E }



In [7]:

    
plt.imshow(plt.imread('./res/str_con.png'))









    Out[7]:





<matplotlib.image.AxesImage at 0x10b1b7e80>

即先在$G$中搜出子树，再在子树中反向搜索出强连通域。



In [8]:

    
plt.figure(figsize=(8,12))
plt.imshow(plt.imread('./res/fig22_9.png'))









    Out[8]:





<matplotlib.image.AxesImage at 0x10b997cc0>



In [9]:

    
# Exercise