ʵÏÖ¡£
int visited[MAXSIZE]; //ָʾ¶¥µãÊÇ·ñÔÚµ±Ç°Â·¾¶ÉÏ
int exist_path_DFS(ALGraph G,int i,int j)//Éî¶ÈÓÅÏÈÅжÏÓÐÏòͼGÖж¥µãiµ½¶¥µãjÊÇ·ñÓз¾¶,ÊÇÔò·µ»Ø1,·ñÔò·µ»Ø0 {
if(i==j) return 1; //i¾ÍÊÇj else {
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc) {
k=p->adjvex;
if(!visited[k]&&exist_path(k,j)) return 1;//iÏÂÓεĶ¥µãµ½jÓз¾¶ }//for }//else
}//exist_path_DFS
7.9 ͬÉÏÌâÒªÇó¡£ÊÔ»ùÓÚͼµÄ¹ã¶ÈÓÅÏÈËÑË÷²ßÂÔдһËã·¨¡£
int exist_path_BFS(ALGraph G,int i,int j)//¹ã¶ÈÓÅÏÈÅжÏÓÐÏòͼGÖж¥µãiµ½¶¥µãjÊÇ·ñÓз¾¶,ÊÇÔò·µ»Ø1,·ñÔò·µ»Ø0 {
int visited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i);
while(!QueueEmpty(Q)) {
DeQueue(Q,u); visited[u]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc) {
k=p->adjvex; if(k==j) return 1;
if(!visited[k]) EnQueue(Q,k); }//for }//while return 0;
}//exist_path_BFS
7.10 ÊÔÀûÓÃÕ»µÄ»ù±¾²Ù×÷£¬±àд°´Éî¶ÈÓÅÏȲßÂÔ±éÀúÒ»¸öÇ¿Á¬Í¨Í¼µÄ¡¢·ÇµÝ¹éÐÎʽµÄËã·¨¡£Ëã·¨Öв»¹æ¶¨¾ßÌåµÄ´æ´¢½á¹¹£¬¶ø½«Í¼Graph¿´³ÉÊÇÒ»ÖÖ³éÏóÊý¾ÝÀàÐÍ¡£
void STraverse_Nonrecursive(Graph G)//·ÇµÝ¹é±éÀúÇ¿Á¬Í¨Í¼G
{
int visited[MAXSIZE]; InitStack(S);
Push(S,GetVex(S,1)); //½«µÚÒ»¸ö¶¥µãÈëÕ» visit(1); visited=1;
while(!StackEmpty(S)) {
while(Gettop(S,i)&&i) {
j=FirstAdjVex(G,i); if(j&&!visited[j]) {
visit(j); visited[j]=1;
Push(S,j); //Ïò×ó×ßµ½¾¡Í· } }//while
if(!StackEmpty(S)) {
Pop(S,j); Gettop(S,i);
k=NextAdjVex(G,i,j); //ÏòÓÒ×ßÒ»²½ if(k&&!visited[k]) {
visit(k); visited[k]=1; Push(S,k); } }//if }//while
}//Straverse_Nonrecursive
·ÖÎö:±¾Ëã·¨µÄ»ù±¾Ë¼ÏëÓë¶þ²æÊ÷µÄÏÈÐò±éÀú·ÇµÝ¹éËã·¨Ïàͬ,Çë²Î¿¼6.37.ÓÉÓÚÊÇÇ¿Á¬Í¨Í¼,ËùÒÔ´ÓµÚÒ»¸ö½áµã³ö·¢Ò»¶¨Äܹ»·ÃÎʵ½ËùÓнáµã.
7.11 ²ÉÓÃÁÚ½Ó±í´æ´¢½á¹¹£¬±àдһ¸öÅбðÎÞÏòͼÖÐÈÎÒâ¸ø¶¨µÄÁ½¸ö¶¥µãÖ®¼äÊÇ·ñ´æÔÚÒ»Ìõ³¤¶ÈΪkµÄ¼òµ¥Â·¾¶£¨Ö¸¶¥µãÐòÁÐÖв»º¬ÓÐÖØÏֵĶ¥µã£©µÄËã·¨¡£
[Ìáʾ]£ºÀûÓÃÉî¶ÈËÑË÷£¬ÔöÉèÒ»¸öÉî¶È²ÎÊý£¬Éî¶È³¬¹ýk ÔòÍ£Ö¹¶Ô¸Ã½áµãµÄËÑË÷¡£
int visited[MAXSIZE];
int exist_path_len(ALGraph G,int i,int j,int k)//ÅжÏÁÚ½Ó±í·½Ê½´æ´¢µÄÓÐÏòͼGµÄ¶¥µãiµ½jÊÇ·ñ´æÔÚ³¤¶ÈΪkµÄ¼òµ¥Â·¾¶ {
if(i==j&&k==0) return 1; //ÕÒµ½ÁËÒ»Ìõ·¾¶,ÇÒ³¤¶È·ûºÏÒªÇó
else if(k>0) {
visited[i]=1;
for(p=G.vertices[i].firstarc;p;p=p->nextarc) {
l=p->adjvex; if(!visited[l])
if(exist_path_len(G,l,j,k-1)) return 1; //Ê£Óà·¾¶³¤¶È¼õÒ» }//for
visited[i]=0; //±¾ÌâÔÊÐíÔø¾±»·ÃÎʹýµÄ½áµã³öÏÖÔÚÁíÒ»Ìõ·¾¶ÖÐ }//else
return 0; //ûÕÒµ½ }//exist_path_len
7.12 ÏÂͼÊÇ´øÈ¨µÄÓÐÏòͼGµÄÁÚ½Ó±í±íʾ·¨¡£´Ó½áµãV1³ö·¢£¬Éî¶È±éÀúͼGËùµÃ½áµãÐòÁÐΪ£¨ A £©£¬¹ã¶È±éÀúͼGËùµÃ½áµãÐòÁÐΪ£¨ B £©£»GµÄÒ»¸öÍØÆËÐòÁÐÊÇ£¨ C £©£»´Ó½áµãV1µ½½áµãV8µÄ×î¶Ì·¾¶Îª£¨ D £©£»´Ó½áµãV1µ½½áµãV8µÄ¹Ø¼ü·¾¶Îª£¨ E £©¡£ ÆäÖÐA¡¢B¡¢CµÄÑ¡ÔñÓУº ¢Ù V1,V2,V3,V4,V5,V6,V7,V8 ¢Ú V1,V2,V4,V6,V5,V3,V7,V8 ¢Û V1,V2,V4,V6,V3,V5,V7,V8 ¢Ü V1,V2,V4,V6,V7,V3,V5,V8 ¢Ý V1,V2,V3,V8,V4,V5,V6,V7 ¢Þ V1,V2,V3,V8,V4,V5,V7,V6 ¢ß V1,V2,V3,V8,V5,V7,V4,V6 D¡¢EµÄÑ¡ÔñÓУº ¢Ù V1,V2,V4,V5,V3,V8 ¢Ú V1,V6,V5,V3,V8 ¢Û V1,V6,V7,V8 V1,V2,V5,V7,V8 ¢Ü
7.13 ÒÑÖªÒ»¿ÃÒÔ¶þ²æÁ´±í×÷´æ´¢½á¹¹µÄ¶þ²æÊ÷£¬ÊÔ±àд°´²ã´Î˳Ðò£¨Í¬Ò»²ã×Ô×óÖÁÓÒ£©±éÀú¶þ²æÊ÷µÄËã·¨¡£
void LayerOrder(Bitree T)//²ãÐò±éÀú¶þ²æÊ÷ {
InitQueue(Q); //½¨Á¢¹¤×÷¶ÓÁÐ EnQueue(Q,T);
while(!QueueEmpty(Q)) {
DeQueue(Q,p); visit(p);
if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }
}//LayerOrder µÚ°ËÕ ²éÕÒ
8.1 Èô¶Ô´óС¾ùΪnµÄÓÐÐòµÄ˳Ðò±íºÍÎÞÐòµÄ˳Ðò±í·Ö±ð½øÐвéÕÒ£¬ÊÔÔÚÏÂÁÐÈýÖÖÇé¿öÏ·ֱðÌÖÂÛÁ½ÕßÔڵȸÅÂÊʱµÄƽ¾ù²éÕÒ³¤¶ÈÊÇ·ñÏàͬ£¿
£¨1£© ²éÕÒ²»³É¹¦£¬¼´±íÖÐûÓйؼü×ÖµÈÓÚ¸ø¶¨ÖµKµÄ¼Ç¼¡£ £¨2£© ²éÕҳɹ¦£¬ÇÒ±íÖÐÖ»ÓÐÒ»¸ö¹Ø¼ü×ÖµÈÓÚ¸ø¶¨ÖµKµÄ¼Ç¼¡£
£¨3£© ²éÕҳɹ¦£¬ÇÒ±íÖÐÓÐÈô¸É¸ö¹Ø¼ü×ÖµÈÓÚ¸ø¶¨ÖµKµÄ¼Ç¼£¬Ò»´Î²éÕÒÒªÇóÕÒ³öËùÓмǼ¡£
[Ìáʾ]£º¾ùÓÃ˳Ðò²éÕÒ·¨¡£
8.2 »³ö¶Ô³¤¶ÈΪ10µÄÓÐÐò±í½øÐÐÕÛ°ë²éÕÒµÄÅж¨Ê÷£¬²¢ÇóÆäµÈ¸ÅÂÊʱ²éÕҳɹ¦µÄƽ¾ù²éÕÒ³¤¶È¡£
[Ìáʾ]£º¸ù¾ÝP.191 ASL¶¨Ò弯ËãÆ½¾ù²éÕÒ³¤¶È¡£
8.3 ÊÔÍÆµ¼º¬12¸ö½áµãµÄƽºâ¶þ²æÊ÷µÄ×î´óÉî¶È²¢»³öÒ»¿ÃÕâÑùµÄÊ÷¡£
[Ìáʾ]£ºÑØ×î×ó·ÖÖ§Éú³¤£¬Ç°ÌáÊÇ£ºÆäÈÎÒ»×æÏȵÄÓÒ·ÖÖ§Óë×ó·ÖÖ§µÈÉÈç²»µÈÉÔòÏÈÉú³¤ÓÒ·ÖÖ§£¬¶øÉú³¤ÓÒ·ÖÖ§µÄǰÌáÊÇ£ºÆäÈÎÒ»×æÏȵÄ×ó·ÖÖ§ÓëÓÒ·ÖÖ§µÈÉÈç²»µÈÉÔòÏÈÉú³¤×ó·ÖÖ§£¬Èç´Ë½»»¥¿¼ÂÇ£¬Öð²½Éú³¤£¬Ö±µ½12¸ö½áµã¡£
8.4 ÊÔ´Ó¿ÕÊ÷¿ªÊ¼£¬»³ö°´ÒÔÏ´ÎÐòÏò2-3Ê÷£¬¼´3½×B-Ê÷ÖвåÈë¹Ø¼üÂëµÄ½¨Ê÷¹ý³Ì£º20£¬30£¬50£¬52£¬60£¬68£¬70¡£Èç¹û´Ëºóɾ³ý50ºÍ68£¬»³öÿһ²½Ö´Ðкó2-3Ê÷µÄ״̬¡£
8.5 ѡȡ¹þÏ£º¯ÊýH(k)=(3k)£¬ÓÃÏßÐÔ̽²âÔÙÉ¢Áз¨´¦Àí³åÍ»¡£ÊÔÔÚ0¡«10µÄÉ¢ÁеØÖ·¿Õ¼äÖУ¬¶Ô¹Ø¼ü×ÖÐòÁУ¨22£¬41£¬53£¬46£¬30£¬13£¬01£¬67£©¹¹Ôì¹þÏ£±í£¬²¢ÇóµÈ¸ÅÂÊÇé¿öϲéÕҳɹ¦Óë²»³É¹¦Ê±µÄƽ¾ù²éÕÒ³¤¶È¡£ [Ìáʾ]£ºÆ½¾ù²éÕÒ³¤¶È²Î¿¼P.225¡£
0 1 2 3 4 5 6 7 8 9 10 22 41 30 01 53 46 13 67 1 1 2 2 1 1 2 6
ASLsucc = (1¡Á4 + 2¡Á3 + 6) / 8 = 2
ASLunsucc = ( 2 + 1 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 1 ) / 11 = 40 / 11