图算法基础识.ppt

图算法（一） Graph Algorithms  图 图 G = (V, E) V = 顶点的非空有限集 E = 边集 = V ? V的子集，V中顶点对，边的有限集。 |E| = O(|V|2) 简单图(Sample Graph) 任意两个顶点最多只有一条边，且每个点都没有连接到自身的边。 完全图(Complete Grapth) 若有n个顶点的无向图n(n-1)/2条边，则此图为完全图。 图的扩展 扩展: 连通图（ connected graph） 从图中每一顶点都有到其它顶点的路径 。 无向图（ undirected graph）: 边(u,v) = 边 (v,u) 有向图 （directed graph）: (u,v) 表示从顶点u 到顶点 v的一条有向边, 记为 u?v 一个不含有环的有向图称为无环有向图(Directed acyclic graphs ,DAG）。 加权图（ weighted graph） 图中不是边就是顶点与权关联，例如：公路交通图，边以距离w为权。 图 通常用边数 |E|和顶点数|V|描述运行时间。 无向图中 0≤|E|≤|V|(|V|-1)/2 有向图中 0≤|E|≤|V|(|V|-1) 若|E| ? |V|2 ，图是稠密的 dense 若 |E| ? |V| ，图是稀疏的 sparse 对稠密图和稀疏图使用不同的数据结构 图的表示 假设 V = {1, 2, …, n} 邻接矩阵（adjacency matrix） 将图表示成一个 n x n 矩阵 A: A[i, j] = 1 若边 (i, j) ? E (或边的权wij) = 0 若边 (i, j) ? E 图: 邻接矩阵 Example: 图: 邻接矩阵 Example: 图: 邻接矩阵 Example: 邻接矩阵的实现 const maxlength=100 {最大顶点数} type graph=array[1..maxlength,1..maxlength] of integer; 二维数组 输入和查看一遍邻接矩阵需要多少时间？ 答: O(|V|2) 存储一个邻接矩阵需要多少存储空间？ 答: O(|V|2) 稀疏图（|E|?|V|或|E||V|),邻接矩阵是稀疏矩阵，浪费空间，因此采用邻接表更有效。 图:邻接表 邻接表: 对每个顶点 v ? V, 将v的所有邻接点存放在一个列表中。 Example: Adj[1] = {2,3} Adj[2] = {3} Adj[3] = {} Adj[4] = {3} 图:邻接表 邻接表的实现 Type pointer=↑adjnode adjnode=record adjvex:integer; {该点在图中的位置} next:pointer; {指向下一个顶点的指针} infor: …; {与边有关的信息，如权值w} Adjlist=array[1..maxlength] of pointer; 拓扑排序算法 Function topsort:boolean; P140 var i,count:integer; wadj:Arr3;//用来表示图的邻接表表头数组 indeg:Arr1; //一维数组，存储每个顶点的入度 p:wpointer; //链表，邻接表 q:queue; //队列q保存入度为零且未被排序的顶点 begin //算法依次对q的出队元素进行编号 topsort:=true; count:=0; makenull(q); //清空队列q fillchar(indeg,sizeof(indeg),0); //数组indeg存储每个顶点入度 //通过遍历邻接表，计算所有顶点的入度 For i:=1 to n do begin p:=wadj[i]; //顶点i的邻接表的第一个邻接点 while pnil do //依次为顶点i的所有邻接点入度加1 begin inc(indeg[p^.v]); p:=p^.next; end; End; //入度为0的顶点加入队列q For i:=1 to n do if indeg[i]=0 the