|
|
|
《数据结构》自学方法指导 |
|
|
来源： 发布时间：2006-5-29 16:56:48 点击： |
最后我们要注意两点:一个图的邻接矩阵表示是唯一的，而一个图的邻接表表示是不唯一的。
图的遍历算法:
因为图是一种非线性数据结构，因此我们有使其序列化的需要--即图的遍历。和树的遍历类似，图的遍历(traversing graph)，就是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。图的遍历算法是其后我们要学习的许多算法的基础。
按照搜索次序的不同，通常有两种遍历图的方法：深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。
深度优先搜索(depth一first search)遍历类似于树的先根遍历。
假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v0出发，访问此顶点，然后依次从vo的未被访问的邻接点出发深度优先遍历图，直至图中所有和v0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[ 1:n]，其初值为"false"，一旦某个顶点被访问，则其相应的分量置为 "true"。整个图的遍历算法如下所示。你也可以通过演示加深印象。
void traver_dfs(Graph g，bool visited［］)
{ /*对图按深度优先进行遍历*/
for (i=1;i<=vexnum;i++)
visited[i]＝false；//标志数组初始化
for (i=1;i<=vexnum;i++)
if (!visited[i])
dfs(g，i);
}
void dfs(Graph g ,vtx * v0){
/*从v0出发深度优先遍历图g*/
visit(v0);
visited[v0] = true;
w=FIRSTADJ(g，v0); //w为v0的邻接点
while (w!=0) { //当邻接点存在时
if (!visited[w])
dfs (g，w);
w= NEXTADJ(g，v0，w)//找下一邻接点
}
}//dfs
分析上述过程，在遍历图时，对图中每个顶点至多调用一次dfs过程，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n＋e)。
广度优先搜索(breadth一first search)遍历类似于树的按层次遍历的过程。 假设从图中某顶点v0出发，在访问了v0之后依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发广度优先搜索遍历图，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v0为起始点，由近至远，依次访问和v0有路径相通且路径长度为1，2，…的顶点。
和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1，2，…的顶点。广度优先遍历的算法如下所示。
分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。
void traver_bfs(Graph g，bool visited［］){ /*对图按广度优先进行遍历*/
for (i=1;i<=vexnum;i++)
visited[i]＝false；//标志数组初始化
for (i=1;i<=vexnum;i++)
if (!visited[i］)
dfs(g，i);
}
void bfs(Graph g ,vtx * v0){
/*从v0出发广度优先遍历图g*/
visit(v0);
visited[v0]=true;
INIQUEUE(Q);//初始化队列
ENQUEUE(Q,v0);
while (!EMPTY(Q)) {
v=DLQUEUE(Q); //队头元素出队
w=FIRSTADJ(g,v);//求v的邻接点
while (w!=0){
if (!visited[w]) {
visit(w);
visited[w]=true;
ENQUEUE(Q,w);
}
w=NEXTADJ(g,v,w);//求下一邻接点
}
}
}//bfs
18.排序
排序 (sorting) 是计算机程序设计中的一种重要运算。它的功能是将一个数据元素 (或记录) 的任意序列，重新排列成一个按关键字有序的序列。在许多算法中都要利用到排序。
我们需要掌握的有两种插入排序方法：直接插入排序和希尔排序：
(1)插入排序
直接插入排序(straight insertion sort)是一种最简单的排序方法。它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数加 1 的有序表。
直接插入排序是逐趟进行的。我们来看一看，第 i 趟直接插入排序是怎样进行的： 在含有 i-1 个记录的有序子序列 r[1]...r[i-1] 中插入一个记录 r[i]后，变成含有 i 个记录的有序子序列 r[1]...r[i]。并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r[0] 处设置监视哨。请注意为了提高效率，在搜索的过程中同时也移动记录。 一趟直接插入排序的算法如下：
整个排序过程为进行n-1趟插入，是一个迭代的过程：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。算法如下:
void InsertSort(SeqList r)
//对r1..n]进行直接插入排序，使其按关键字非递减有序
int i,j;
for (int i=2;i<=n;i++)
if(ri].key<r[i-1].key)
{//若r[i].key大于等于有序区中所有地keys,则r[i]应在原有位置上
r[0]=r[i];j=i-1; //r[0]是哨兵，且是r[i]的副本
do{//从右向左在有序区r[1..i-1]中查找r[i]的插入位置
r[j+1]=r[j]; //将关键字大于r[i].key的记录后移
j- -;
}while(r[0].key<r[j].key);
r[j+1]=r[0];
}
}
当待排序列中记录按关键字非递减有序排列(以下称之为"正序")时，所需进行关键字间比较的次数达最小值n-1; 当待排序列中记录按关键字非递增有序排列(以下称之为"逆序")时，总的比较次数达最大值(n＋2)(n-1)/2 则我们可取上述最小值和最大值的平均值，作为直接插入徘序时所需进行关键字间的比较次数和移动记录的次数，约为n2／4。由此，直接插入排序的时间复杂度为O(n2)。
(2)希尔排序
希尔排序(Shell's methed)又称缩小增量排序(diminishing increment sort)，它也是一种插入排序类的方法，但在时间效率上较前述几种排序方法有较大的改进。它是一种较快速的排序算法。其时间复杂度是O(n3/2)。
希尔排序产生的原因是来自对直接插入排序的分析，当直接排序中其算法时间复杂度为O(n2) ，但是，若待排记录序列按关键字"基本有序"，直接插入排序的效率就可大大提高。希尔排序就是主要针对这一点对直接插入排序进行改进而得到的。
它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行一次直接插入排序。
在希尔排序中，子序列的构成不是简单地"逐段分割"，而是将相隔某个"增量"的记录组成一个子序列。如在第一趟排序时的增量为7，即将相隔为7的元素编成一组进行直接插入排序。第二趟排序时的增量为3，增量进一步缩小。由于在这两趟的插入排序中在子序列中逆序的关键字是跳跃式地移动，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序，只要作少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。 本新闻共 6页,当前在第 5页 1 2 3 4 5 6 |
|
|
|
