图的遍历算法.doc

. .
优选
图的遍历问题
在实践中常常遇到这样的问题：给定n个点，从任一点出发对所有的点访问一次并且只访问一次。如果用图中的顶点表示这些点，图中的边表示可能的连接，那么这个问题就可以表示成图的遍us(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<, ++v)
visited[v] = FALSE;
initQueue(Q); //置空辅助队列Q
for(v=0; v<; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入队列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //队头元素出队并置为u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w为u的尚未访问的邻接顶点
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);}}}}
广度优先搜索算法的时间复杂度和深度优先搜索算法的时间复杂度一样。和深度优先搜索不同的是，广度优先搜索的队列是惟一的，对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次，当图是连通图时，只需要调用一次邻接矩阵或邻接链表即可完成遍历操作。故邻接矩阵表示法的遍历时间效率为O(n2)，邻接链表表示法的遍历时间效率为O(n+e)。
运行结果及分析
这里选择邻接矩阵作为图的存储构造编写程序，然后将图1的顶点和边输入程序作为测试。
f
h
d
g
e
b
a
c
图1 测试图
. .
优选
程序运行结果如以下图2：
图2运行结果图
由结果知，对图1深度优先遍历的结果为：a b d h e c f g，广度优先遍历的结果为a b c d e f g h。又因为程序的时间效率为O(n2)，当测试数值非常小时，程序运行的时间将十分小，忽略不计，故遍历时间为0。

字符串匹配(String match)是在实际工作中经常碰到的问题，通常是输入主字符串(String)和字串(又称模式Pattern)组成，然后根据一定的算法来得出字串在主字符串中的位置。通常准确的字符串匹配算法包括暴力搜索(Brute force，又叫蛮力法)，KMP(Knuth-Morris-Pratt)，BM(Boyer Moore)等等。假定原字符串长度为n，子字符串长度为m，下面将介绍以上这三种方法并给出其实现。
蛮力法
蛮力法是一种简单的匹配算法，它将字串和主字符串从左方对齐，然后从左到右将子串和主字符串中每一对相应的字符串进展匹配，如果一旦不匹配，那么把字串向右移动一格，再进展下一轮匹配。因为这种尝试的最大次数是n-m+1次，在最坏的情况下，每次尝试需要进展m次比较，所以在最坏的情况下，字符比较的次数为m*(n-m+1)。故蛮力法的时间效率为O(mn)。其设计思想为：
①在串S、T中比较的起始下标为i和j；
②循环直到S中剩下的字符个数小于T的长度或T的所有
字符都比较完：
如果S[i]=T[j]，那么继续比较S和T的下一个字符，否那么
将i和j回溯，进展下一趟比较；
③如果T中的字符都比较完，那么匹配成功，返回匹配的起
始下标，否那么匹配失败，返回0。
KMP算法
KMP算法使用了输入增强的思想，对模式进展预处理以得到一些信息，把这些信息存储在表中，然后在给定文本中实际查找模式时使用这些信息。KMP算法也是将子字符串从左到右和主串进展匹配，和蛮力法不同的是，KMP算法在匹配失败后，并不是简单的从目标串的下一个字符串开场新一轮的检测，而是依据在检测之前得到的有用信息，直接跳过不必要的检测，从主串中找一个和子串字符匹配成功的字符，以这个字符为起点将字串对齐，然后开场新的匹配。从而到达一个较高的匹配效率。KMP算法的时间复杂度为O(n+m)，当m远小于n的时候，算法的效率将取决于主字符串的长度，即时间复杂度为O(n)。其设计思想为：
. .
优选
①在串S、T中比较的起始下标为i和j；
②循环直到S中剩下的字符个数小于T的长度或T的所有字符都比较完：如果S[i]=T[j]，那么继续比较S和T的下一个字符，否那么将i向右滑动到next[j]的位置，即j=next[i];如果j=0，那么将i和j分别加1，准备进展下一趟比较。
③如果T中的字符都比较完，那么