# 算法设计与分析笔记0x01 —— 图

## Basic Definition and Application

• 有向图与无向图
• 图的表示
• 邻接矩阵
• 查看二点间是否有边很方便， $\Theta(1)$
• 遍历复杂度较高, $\Theta(n^2)$
• • 邻接表
• 利于稀疏图
• 遍历复杂度 $\Theta(m+n)$， m个结点，n条边
• 检查(u,v)是否为边， O(deg(u))，检查与u相邻的边
• • Paths and Connectivity
• Def. A path in an undirected graph G = (V, E) is a sequence P of nodes v1 , v2 , …, v(k-1) , vk with the property that each consecutive pair vi , v(i+1) is joined by an edge in E.
• Def. simple path: 路径上结点不重复
• Def. connected graph: 任意两个结点间都存在路径
• Cycles
• Def. cycle: a path (v1,v2…vk)，前k-1个结点不重复
• Tree
• Def: 不含cycle的无向图
• Theorem
• connected
• no cycle
• n-1 edges (n is number of nodes)
• Rooted tree. Given a tree T, choose a root node r and orient each edge away from r.

## Graph Traversal

• s-t connectivity problem 连通性问题
• s-t shortest path problem 最短路径问题
• Applications
• Maze traversal.
• Fewest number of hops in a communication network.
• Driving direction in Google Maps
• Algorithm
• L0 = { s }.
• L1 = all neighbors of L0 .
• L2 = all nodes that do not belong to L0 or L1 , and that have an edge to a node in L1 .
• L(i+1) = all nodes that do not belong to an earlier layer, and that have
an edge to a node in Li .
• Theorem. For each i, Li consists of all nodes at distance exactly i from s. There is a path from s to t iff t appears in some layer.
• Property. Let (x, y) be an edge of G. Then the level of x and y differ by at most 1.
• • 走到底再回溯
• ### BFS/DFS Analysis

• O(m+n) 邻接表存储
• Pf.
• 初始化 访问O(n)
• 访问一条边 deg(u)，每条边访问两次
• 总访问时间 sum(deg(u)) = 2m
• BFS/DFS也可以用于查找Connected Component，连通分支

## Testing Bipartiteness

### Bipartite Graphs

• Def. An undirected graph G = (V, E) is bipartite if the nodes can be colored red or blue such that every edge has one red and one blue end.
• Applications
• Stable marriage: men=red, women=blue
• Scheduling: machines=red, jobs=blue
• • Testing bipartiteness
• 给定一个图，判断是否是二分图
• 若给定图是二分图，很多图的相关问题会变得更简单
• independent set: 多项式时间算法

### Lemma

• 二布图不含奇数长度的环（充分必要
• BFS时，以下命题仅一个发生
• (i) 没有一条边连接同一层的两个结点，为二布图
• (ii) 同一层的两个结点中至少一条边，含奇数长度的环，不为二布图
• • Pf. (i)
• Suppose no edge joins two nodes in the same layer.
• Bipartition: red = nodes on odd levels, blue = nodes on even levels.
• • Pf. (ii)
• Suppose (x, y) is an edge with x, y in same level L j .
• Let z be lowest common ancestor of x, y in BFS tree.
• Let L i be level containing z.
• Consider cycle that takes edge from x to y, then path from y to z, then path from z to x.
• Its length is 1 + (j-i) + (j-i), which is odd.
• ## Connectivity in Directed Graph

• Directed reachability
• Directed s-t shortest path problem
• Graph search
• Web crawler
• Strong Connectivity
• Def. mutually reachable. u->v and v->u
• Def. 任意两个结点都可相互抵达，则strong connectivity
• Lemma. Let s be any node. G is strongly connected iff every node is reachable from s, and s is reachable from every node.

### Strong Connectivity: Algorithm

• Theorem. Can determine if G is strongly connected in O(m + n) time.
• Pick any node s.
• Run BFS from s in G.
• Run BFS from s in Grev(reverse orientation of every edge in G).
• Return true iff all nodes reached in both BFS executions.
• Correctness follows immediately from previous lemma.

## DAGs and Topological Ordering

• Directed Acyclic Graphs
• 有向无环图
• 拓扑序列: A topological order of a directed graph G = (V, E) is an ordering of its nodes as v1 , v2 , …, vn so that for every edge (vi , vj) we have i < j.
• • Applications of Precedence Constraints
• Edge (vi , vj) means task vi must occur before vj .
• 课程先修图, course vi must be taken before vj .
• 编译顺序, module vi must be compiled before vj .
• Pipeline of computing jobs, output of job vi needed to determine input of job vj.

### Lemma

• Lemma1: 若一张图有拓扑排序，则为DAG（充分必要）。证明如下：
• Suppose that G has a topological order v1 , …, vn and that G also has a directed cycle C. Let’s see what happens.
• Let v i be the lowest-indexed node in C, and let vj be the node just before vi; thus (vj , vi) is an edge.
• By our choice of i, we have i < j.
• On the other hand, since (vj , vi) is an edge and v1 , …, vn is a topological order, we must have j < i, a contradiction.
• • Lemma2: DAG中存在一个结点，没有边指向它。证明如下:
• Suppose that G is a DAG and every node has at least one incoming edge. Let’s see what happens.
• Pick any node v, and begin following edges backward from v. Since v has at least one incoming edge (u, v) we can walk backward to u.
• Then, since u has at least one incoming edge (x, u), we can walk backward to x.
• Repeat until we visit a node, say w, twice.
• Let C denote the sequence of nodes encountered between successive visits to w. C is a cycle.
• • Lemma3: 若一张图为DAG，则有拓扑排序。证明如下：
• Base case: true if n = 1.
• Given DAG on n > 1 nodes, find a node v with no incoming edges.
• G – { v } is a DAG, since deleting v cannot create cycles.
• By inductive hypothesis, G – { v } has a topological ordering.
• Place v first in topological ordering; then append nodes of G – { v } in topological order. This is valid since v has no incoming edges.
• (即不断删除没有边指向的点)
• ### Running Time

• Theorem. Algorithm finds a topological order in O(m + n) time.
• Pf.
• Maintain the following information:
• count[w] = remaining number of incoming edges
• S = set of remaining nodes with no incoming edges
• Initialization: O(m + n) via single scan through graph.
• Update: to delete v
• remove v from S
• decrement count[w] for all edges from v to w, and add w to S if count[w] hits 0