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

  1. adjacency-list: sparse graphs

    • pros: save memory.
  2. 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

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

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} \}$.

  1. Each vertex is initially white, is grayed when it is discovered in the search, and is blacked when it is finished.

  2. 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
  1. the predecessor subgraph $G_{\pi}$ does indeed form a forest of trees.

  2. discovery and finishing times have parenthesis structure.

  3. 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