2015年国家电网考试备考计算机之数据结构与算法(14)

　　对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。

　　2.2 广度优先遍历

　　广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。

　　邻接矩阵做存储结构时，广度优先搜索的代码如下。

　　对于邻接表的广度优先遍历，代码与邻接矩阵差异不大， 代码如下。

　　对比图的深度优先遍历与广度优先遍历算法，会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的，只是不同的情况选择不同的算法。

　　7.堆 (Heap)

　　在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值最小(或最大)，且根结点的两个子树也是一个堆。

　　例程

　　为将元素X插入堆中，找到空闲位置，建立一个空穴，若满足堆序性(英文：heap order)，则插入完成;否则将父节点元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。

　　void Insert( ElementType X, PriorityQueue H ){ int i; if( IsFull(H) ) { printf( "Queue is full.\n" ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}

　　以上是插入到一个二叉堆的过程。

　　DeleteMin，删除最小元，即二叉树的根或父节点。删除该节点元素后，队列最后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。