有向图基础

这是coursera上的princeton算法课程的读书笔记

这个princeton公开课的源地址，如果对课程感兴趣可以在coursera上搜这一门课程。

图有两种表示方式， 邻接矩阵和邻接表

邻接表适用于大量的顶点，而每一个顶点的边不多的情况

In practice. Use adjacency-lists representation. ・Algorithms based on iterating over vertices pointing from v. ・Real-world digraphs tend to be sparse. huge number of vertices, small average vertex degree

representation			space			insert edge from v to w?	edge from v to w?	iterate over vertices pointing from v?
list of edges			E			1	E	E
adjacency matrix			V2			1†	1	V
adjacency lists			E + V			1	outdegree(v)	outdegree(v)

† disallows parallel edges

Reachability application: program control-flow analysis Every program is a digraph. ・Vertex = basic block of instructions (straight-line program). ・Edge = jump. Dead-code elimination. // 检查deadcode Find (and remove) unreachable code. Infinite-loop detection. // 检查无限循环 Determine whether exit is unreachable.

标记-清除垃圾回收器 Reachability application: mark-sweep garbage collector