图的遍历算法.doc

1 图的遍历问题在实践中常常遇到这样的问题：给定n个点，从任一点出发对所有的点访问一次并且只访问一次。如果用图中的顶点表示这些点，图中的边表示可能的连接，那么这个问题就可以表示成图的遍历问题，即从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。图的遍历操作和树的遍历操作功能相似，是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础上。由于图结构本身的复杂性，所以图的遍历操作也比较复杂，主要表现在以下几个方面：(1) 在图结构中，没有一个确定的首结点，图中任意一个顶点都可以作为第一个被访问的结点。(2) 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需要考虑如何选取下一个出发点以访问图中其余的连通分量。(3) 在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点。(4) 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。 基于以上分析，图的遍历方法目前有深度优先搜索(DFS)和广度优先搜索(BFS)两种算法。下面将介绍两种算法的实现思路，分析算法效率并编程实现。1.1 深度优先搜索算法深度优先搜索算法是树的先根遍历的推广，它的实现思想是：从图G的某个顶点V0出发，访问V0，然后选择一个与V0相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且未被访问的顶点Vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：Boolean visitedMAX_VERTEX_NUM; /访问标志数组Status (*VisitFunc)(int v); /VisitFunc是访问函数，对图的每个顶点调用该函数void DFSTraverse (Graph G, Status(*Visit)(int v)VisitFunc = Visit;for(v=0; vG.vexnum; +v)visitedv = FALSE; /访问标志数组初始化for(v=0; v=0; w=NextAdjVex(G,v,w)/FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。/若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。/若w是v的最后一个邻接点，则返回空（0）。if(!visitedw)DFS(G, w); /对v的尚未访问的邻接顶点w调用DFS由以上叙述可知，深度优先搜索算法的效率取决于图的数据结构的表示方法。当访问某顶点Vi时，DFS的时间主要消耗在从该顶点出发搜索它的所有邻接点上。用邻接矩阵表示图时，其搜索时间为O(n)；用邻接表表示图时，需搜索第i个边表上的所有结点。因此，对所有n个顶点访问，在邻接矩阵上共需检查n2个矩阵元素，而在邻接表上需将边表中所有e个结点检查一遍。故由理论分析可知，DFS的时间复杂度为O(n2)或O(n+e)。1.2 广度优先搜索算法广度优先搜索算法是树的按层次遍历的推广，它的基本思路是：首先访问初始点Vi，并将其标记为已访问点，然后访问Vi的所有未被访问过的邻接点Vi1，Vi2，Vit，并均标记为已访问，再按照Vi1，Vi2，Vit的顺序，依次访问每一个顶点的所有未被访问过的邻接点，并标记为已访问。依次类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。如果仍有未被访问过的顶点，该算法必须从图的其它连通分量的任意顶点重新开始。其非递归算法如下：Boolean visitedMAX_VERTEX_NUM; /访问标志数组Status (*VisitFunc)(int v); /VisitFunc是访问函数，对图的每个顶点调用该函数void BFSTraverse (Graph G, Status(*Visit)(int v)VisitFunc = Visit;for(v=0; vG.vexnum, +v)visitedv = FALSE;initQueue(Q); /置空辅助队列Qfor(v=0; v=0; w=NextAdjVex(G,u,w)if(!Visitedw) /w为u的尚未访问的邻接顶点Visitedw=TRUE; VisitFunc(w);EnQueue(Q, w);广度优先搜索算法的时间复杂度和深度优先搜索算法的时间复杂度相同。和深度优先搜索不同的是，广度优先搜索的队列是惟一的，对于具有n个顶点和e条边的无向图或有向图，每个顶点均入队一次，当图是连通图时，只需要调用一次邻接矩阵或邻接链表即可完成遍历操作。故邻接矩阵表示法的遍历时间效率为O(n2)，邻接链表表示法的遍历时间效率为O(n+e)。1.3 运行结果及分析这里选择邻接矩阵作为图的存储结构编写程序，然后将图1的顶点和边输入程序作为测试。fhdgebac图1 测试图程序运行结果如下图2：图2运行结果图 由结果知，对图1深度优先遍历的结果为：a b d h e c f g，广度优先遍历的结果为a b c d e f g h。又因为程序的时间效率为O(n2)，当测试数值非常小时，程序运行的时间将十分小，忽略不计，故遍历时间为0。2.字符串匹配问题字符串匹配(String match)是在实际工作中经常碰到的问题，通常是输入主字符串(String)和字串(又称模式Pattern)组成，然后根据一定的算法来得出字串在主字符串中的位置。通常精确的字符串匹配算法包括暴力搜索(Brute force，又叫蛮力法)，KMP(Knuth-Morris-Pratt)，BM(Boyer Moore)等等。假定原字符串长度为n，子字符串长度为m，下面将介绍以上这三种方法并给出其实现。2.1 蛮力法蛮力法是一种简单的匹配算法，它将字串和主字符串从左方对齐，然后从左到右将子串和主字符串中每一对相应的字符串进行匹配，如果一旦不匹配，则把字串向右移动一格，再进行下一轮匹配。因为这种尝试的最大次数是n-m+1次，在最坏的情况下，每次尝试需要进行m次比较，所以在最坏的情况下，字符比较的次数为m*(n-m+1)。故蛮力法的时间效率为O(mn)。其设计思想为：在串S、T中比较的起始下标为i和j；循环直到S中剩下的字符个数小于T的长度或T的所有字符都比较完：如果Si=Tj，则继续比较S和T的下一个字符，否则将i和j回溯，进行下一趟比较；如果T中的字符都比较完，则匹配成功，返回匹配的起始下标，否则匹配失败，返回0。2.2 KMP算法KMP算法使用了输入增强的思想，对模式进行预处理以得到一些信息，把这些信息存储在表中，然后在给定文本中实际查找模式时使用这些信息。KMP算法也是将子字符串从左到右和主串进行匹配，和蛮力法不同的是，KMP算法在匹配失败后，并不是简单的从目标串的下一个字符串开始新一轮的检测，而是依据在检测之前得到的有用信息，直接跳过不必要的检测，从主串中找一个和子串字符匹配成功的字符，以这个字符为起点将字串对齐，然后开始新的匹配。从而达到一个较高的匹配效率。KMP算法的时间复杂度为O(n+m)，当m远小于n的时候，算法的效率将取决于主字符串的长度，即时间复杂度为O(n)。其设计思想为： 在串S、T中比较的起始下标为i和j； 循环直到S中剩下的字符个数小于T的长度或T的所有字符都比较完：如果Si=Tj，则继续比较S和T的下一个字符，否则将i向右滑动到nextj的位置，即j=nexti;如果j=0，则将i和j分别加1，准备进行下一趟比较。如果T中的字符都比较完，则匹配成功，返回匹配的起 始下标，否则匹配失败，返回0。2.3 BM算法BM算法是一种精确字符串匹配算法，采用输入增强思想，对模式进行预处理以得到一些有用信息。和KMP算法不同的是，BM算法采用从右到左比较的方法，同时应用到了坏字符规则和好后缀规则，来决定向右跳跃的距离。所谓坏字符规则就是在BM算法从右到左扫描过程中，若发现某个字符x不匹配，则按如下两种情况考虑：A. 如果字符x在模式p中没有出现，那么从字符x开始的m个文本显然不可能与p匹配成功，直接跳过该区域即可。B. 如果x在模式p中出现，则以该字符为起点将子串对齐。好后缀规则为：若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下情况考虑：A. 如果在模式p中位置t处已匹配部分p1在p中某位置t1也出现，且位置t1前一个字符与位置t的前一个字符不相同，则将p右移使t1对于t方才所在的位置。B. 如果在p中任何位置已匹配部分p1都没有再出现，则找到与p1的后缀p2相同的p的最长前缀x,向右移动p，使得x对应方才p2后缀所在位置。BM算法的时间复杂度为O(n+m2)，当子串长度m非常小时，算法效率取决与主字符串的长度n。故其时间复杂度为O(n)。2. 运行结果及分析 根据上面的介绍，我们编写程序来实现三种字符串匹配算法。如图3所示图3匹配算法运行结果图 由图3我们可知当随机输入主字符串和子字符串时，BF算法运行时间为0.016秒，而另外两种算法的时间为0，可忽略不计。可知明显蛮力法所花费的时间比较多，这和前面的理论分析中的蛮力法的时间复杂度为O(m*n)相符合。而通过对结果分析知，KMP算法和BM算法的匹配效率非常高，这和理论分析中二者时间复杂度为O(n)也相符合。事实上，当我们输入的字符串长度非常大时，这种时间上的优势将更加明显，这里就不再一一测试了。附录(程序代码)1. 图的遍历#include # include time.h#define INFINITY 32767#define MAX_VEX 20 /最大顶点个数#define QUEUE_SIZE (MAX_VEX+1) /队列长度using namespace std;bool *visited; /访问标志数组/图的邻接矩阵存储结构typedef struct char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数Graph;/队列类class Queue public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear;/图G中查找元素c的位置int Locate(Graph G,char c) for(int i=0;iG.vexnum;i+) if(G.vexsi=c) return i; return -1;/创建无向网void CreateUDN(Graph &G) int i,j,w,s1,s2; char a,b,temp; printf(输入顶点数和弧数:); scanf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf(输入%d个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化顶点 printf(输入顶点%d:,i); scanf(%c,&G.vexsi); temp=getchar(); /接收回车 for(i=0;iG.vexnum;i+) /初始化邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(输入%d条弧.n,G.arcnum); for(i=0;i=0 & kG.vexnum) /k合理 for(int i=0;i=0 & i=0 & jG.vexnum) /i,j合理 for(int k=j+1;kG.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1;/深度优先遍历void DFS(Graph G,int k) int i; if(k=-1) /第一次执行DFS时,k为-1 for(i=0;i=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /对k的尚未访问的邻接顶点i递归调用DFS /广度优先遍历void BFS(Graph G) int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i=0;w=NextVex(G,k,w) if(!visitedw) /w为k的尚未访问的邻接顶点 visitedw=true; printf(%c ,G.vexsw); Q.EnQueue(w); /主函数int main() int i; time_t DFSstart,DFSend; time_t BFSstart,BFSend; double totaltime1,totaltime2; Graph G; CreateUDN(G); visited=(bool *)malloc(G.vexnum*sizeof(bool); printf(n深度优先遍历: ); DFSstart=clock(); for(i=0;iG.vexnum;i+) visitedi=false; DFS(G,-1); DFSend=clock(); totaltime1=(double)(DFSend - DFSstart)/CLOCKS_PER_SEC; printf(n深度优先遍历时间:n); couttotaltime1endl; printf(n广度优先遍历: ); BFSstart=clock(); for(i=0;iG.vexnum;i+) visitedi=false; BFS(G); BFSend=clock(); totaltime2=(double)(BFSend - BFSstart)/CLOCKS_PER_SEC; printf(n广度优先遍历时间:n); couttotaltime2endl; printf(n程序结束.n); return 0;2. 字符串匹配#include #include #includetime.husing namespace std;class stringcomprivate:char s256,t256;/分别代表主串与要匹配的串int num,pos256;/分别记录匹配次数与所出现匹配的位置int next256,dist256;/KMP,BM记录的不匹配时下一位置FILE *fp1,*fp2;public:void file (); void BF ();void KMP ();void BM ();void GetNext ();void GetDist ();void Input ()cinst;void Output ();void main ()stringcom str;cout请输入主串S，和子串t：endl;str.Input ();/这里选择输入字符串str.BF ();str.KMP ();str.BM ();void stringcom:BF () /蛮力法匹配int i,j=0; time_t start,end;double totaltime;num=0;start=clock();for (i=0;istrlen (s);i+)if (si=tj)j+;if (!tj)posnum=i-j+2;num+;i=i-strlen (t)+1;/i从下一个位置开始，避免了重叠的串j=0;else i=i-j;j=0;coutendl按BF算法实现:0)if (j=0|(si=tj)i+;j+;if (!tj)posnum=i-strlen (t)+1;/位置从1开始记录，下标从0开始i=posnum;/i从下一个位置开始，避免了重叠的串num+;j=0;else j=nextj;coutendl按KMP算法实现:endl;Output ();end=clock();totaltime=(double)(end-start)/CLOCKS_PER_SEC;printf(KMP算法运行时间为：%.8f,totaltime)