2016秋季龙岩市武平县事业单位考试：计算机之数据结构与算法之图的遍
福建省公务员考试网 | 2016-07-07
分享
图的遍历
图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。
对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。
2.1 深度优先遍历
深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。
它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。
我们用邻接矩阵的方式，则代码如下所示。
如果使用的是邻接表存储结构，其DFSTraverse函数的代码几乎是相同的，只是在递归函数中因为将数组换成了链表而有不同，代码如下。
对比两个不同的存储结构的深度优先遍历算法，对于n个顶点e条边的图来说，邻接矩阵由于是二维数组，要查找某个顶点的邻接点需要访问矩阵中的所有元素，因为需要O(n2)的时间。而邻接表做存储结构时，找邻接点所需的时间取决于顶点和边的数量，所以是O(n+e)。显然对于点多边少的稀疏图来说，邻接表结构使得算法在时间效率上大大提高。#p#副标题#e#
2.2 广度优先遍历
广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。
邻接矩阵做存储结构时，广度优先搜索的代码如下。
对于邻接表的广度优先遍历，代码与邻接矩阵差异不大， 代码如下。
对比图的深度优先遍历与广度优先遍历算法，会发现，它们在时间复杂度上是一样的，不同之处仅仅在于对顶点的访问顺序不同。可见两者在全图遍历上是没有优劣之分的，只是不同的情况选择不同的算法。#p#副标题#e#
7.堆 (Heap)
在计算机科学中，堆是一种特殊的树形数据结构，每个结点都有一个值。通常我们所说的堆的数据结构，是指二叉堆。堆的特点是根结点的值小(或大)，且根结点的两个子树也是一个堆。
例程
为将元素X插入堆中，找到空闲位置，建立一个空穴，若满足堆序性(英文：heap order)，则插入完成;否则将父节点元素装入空穴，删除该父节点元素，完成空穴上移。直至满足堆序性。这种策略叫做上滤(percolate up)。
void Insert( ElementType X, PriorityQueue H ){ int i; if( IsFull(H) ) { printf( "Queue is full. " ); return; } for( i = ++H->Size; H->Element[i/2] > X; i /= 2 ) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X;}
以上是插入到一个二叉堆的过程。
DeleteMin，删除小元，即二叉树的根或父节点。删除该节点元素后，队列后一个元素必须移动到堆得某个位置，使得堆仍然满足堆序性质。这种向下替换元素的过程叫作下滤。
ElementType DeleteMin( PriorityQueue H ){ int i, Child; ElementType MinElement, LastElement; if( IsEmpty( H ) ) { printf( "Queue is empty. " ); return H->Elements[0]; } MinElement = H->Elements[1]; LastElement = H->Elements[H->Size--]; for( i = 1; i*2 <= H->Size; i = Child ) { /* Find smaller child. */ Child = i*2; if( Child != H->Size && H->Elements[Child+1] < H->Elements[Child] ) Child++; /* Percolate one level. */ if( LastElement > H->Elements[Child] ) H->Elements[i] = H->Elements[Child]; else break; } H->Elements[i] = LastElement; return MinElement;}
7.算法设计的分析技术
算法是对问题求解过程的准确描述，由有限条指令组成，这些指令能在有限时间内执行完毕并产生确定性的输出。
进行算法的时间复杂度分析，就是求其T(n)，并用O、Ω或是Θ以尽可能简单的形式进行表示。
理想情况下，希望能够使用Θ表示算法的时间复杂性。退而求其次，可以使用O或是Ω。
使用O时，希望估计的上界的阶越小越好。
使用Ω时，希望估计的下界的阶越大越好。
树的高度为ëlognû,所以将一个元素插入大小为n的堆所需要的时间是O(logn).
delete(H,i) 所需要的时间是O(logn).
make-heap(A): 从数组A创建堆
方法1：从一个空堆开始，逐步插入A中的每个元素，直到A中所有元素都被转移到堆中。
时间复杂度为O(nlogn).
方法2：
MAKEHEAP(创建堆)
输入：数组A[1…n]
输出：将A[1…n]转换成堆
1. fori← ën/2û downto 1
2. Sift-down(A,i){使以A[i]为根节点的子树调整成为堆，故调用down过程}
3. endfor
时间复杂度为O(n).
延伸阅读