《數(shù)據(jù)結(jié)構(gòu)題集》答案 第7章 圖

《《數(shù)據(jù)結(jié)構(gòu)題集》答案 第7章 圖》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)題集》答案 第7章 圖（46頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第七章 圖 7.14 Status Build_AdjList(ALGraph &G)/輸入有向圖的頂點數(shù),邊數(shù),頂點信息和邊的信息建立鄰接表InitALGraph(G);scanf(%d,&v);if(v0) return ERROR; /頂點數(shù)不能為負(fù)G.vexnum=v;scanf(%d,&a);if(a0) return ERROR; /邊數(shù)不能為負(fù)G.arcnum=a;for(m=0;mv;m+)G.verticesm.data=getchar(); /輸入各頂點的符號for(m=1;m=a;m+)t=getchar();h=getchar(); /t為弧尾,h為弧頭if(i=Loc

2、ateVex(G,t)0) return ERROR;if(j=LocateVex(G,h)nextarc;q=q-nextarc);q-nextarc=p;p-adjvex=j;p-nextarc=NULL;/whilereturn OK;/Build_AdjList 7.15 /本題中的圖G均為有向無權(quán)圖,其余情況容易由此寫出Status Insert_Vex(MGraph &G, char v)/在鄰接矩陣表示的圖G上插入頂點vif(G.vexnum+1)MAX_VERTEX_NUM return INFEASIBLE;G.vexs+G.vexnum=v;return OK;/Inser

3、t_Vex Status Insert_Arc(MGraph &G,char v,char w)/在鄰接矩陣表示的圖G上插入邊(v,w)if(i=LocateVex(G,v)0) return ERROR;if(j=LocateVex(G,w)0) return ERROR;if(i=j) return ERROR;if(!G.arcsij.adj)G.arcsij.adj=1;G.arcnum+;return OK;/Insert_Arc Status Delete_Vex(MGraph &G,char v)/在鄰接矩陣表示的圖G上刪除頂點vn=G.vexnum;if(m=LocateVex

4、(G,v)0) return ERROR;G.vexsmG.vexsn; /將待刪除頂點交換到最后一個頂點for(i=0;in;i+)G.arcsim=G.arcsin;G.arcsmi=G.arcsni; /將邊的關(guān)系隨之交換G.arcsmm.adj=0;G.vexnum-;return OK;/Delete_Vex分析:如果不把待刪除頂點交換到最后一個頂點的話,算法將會比較復(fù)雜,而伴隨著大量元素的移動,時間復(fù)雜度也會大大增加. Status Delete_Arc(MGraph &G,char v,char w)/在鄰接矩陣表示的圖G上刪除邊(v,w)if(i=LocateVex(G,v)0

5、) return ERROR;if(j=LocateVex(G,w)0) return ERROR;if(G.arcsij.adj)G.arcsij.adj=0;G.arcnum-;return OK;/Delete_Arc 7.16 /為節(jié)省篇幅,本題只給出Insert_Arc算法.其余算法請自行寫出. Status Insert_Arc(ALGraph &G,char v,char w)/在鄰接表表示的圖G上插入邊(v,w)if(i=LocateVex(G,v)0) return ERROR;if(j=LocateVex(G,w)adjvex=j;p-nextarc=NULL;if(!G.

6、verticesi.firstarc) G.verticesi.firstarc=p;elsefor(q=G.verticesi.firstarc;q-q-nextarc;q=q-nextarc)if(q-adjvex=j) return ERROR; /邊已經(jīng)存在q-nextarc=p;G.arcnum+;return OK;/Insert_Arc 7.17 /為節(jié)省篇幅,本題只給出較為復(fù)雜的Delete_Vex算法.其余算法請自行寫出. Status Delete_Vex(OLGraph &G,char v)/在十字鏈表表示的圖G上刪除頂點vif(m=LocateVex(G,v)0) re

7、turn ERROR;n=G.vexnum;for(i=0;itailvex=m) /如果待刪除的邊是頭鏈上的第一個結(jié)點q=G.xlisti.firstin;G.xlisti.firstin=q-hlink;free(q);G.arcnum-;else /否則for(p=G.xlisti.firstin;p&p-hlink-tailvex!=m;p=p-hlink);if(p)q=p-hlink;p-hlink=q-hlink;free(q);G.arcnum-;/else/forfor(i=0;iheadvex=m) /如果待刪除的邊是尾鏈上的第一個結(jié)點q=G.xlisti.firstout

8、;G.xlisti.firstout=q-tlink;free(q);G.arcnum-;else /否則for(p=G.xlisti.firstout;p&p-tlink-headvex!=m;p=p-tlink);if(p)q=p-tlink;p-tlink=q-tlink;free(q);G.arcnum-;/else/forfor(i=m;ihlink)p-headvex-;for(p=G.xlisti.firstout;p;p=p-tlink)p-tailvex-; /修改各鏈中的頂點序號G.vexnum-;return OK;/Delete_Vex 7.18 /為節(jié)省篇幅,本題只給

9、出Delete_Arc算法.其余算法請自行寫出. Status Delete_Arc(AMLGraph &G,char v,char w)/在鄰接多重表表示的圖G上刪除邊(v,w)if(i=LocateVex(G,v)0) return ERROR;if(j=LocateVex(G,w)jvex=j)G.adjmulisti.firstedge=G.adjmulisti.firstedge-ilink;elsefor(p=G.adjmulisti.firstedge;p&p-ilink-jvex!=j;p=p-ilink);if (!p) return ERROR; /未找到p-ilink=p

10、-ilink-ilink; /在i鏈表中刪除該邊if(G.adjmulistj.firstedge-ivex=i)G.adjmulistj.firstedge=G.adjmulistj.firstedge-jlink;elsefor(p=G.adjmulistj.firstedge;p&p-jlink-ivex!=i;p=p-jlink);if (!p) return ERROR; /未找到q=p-jlink;p-jlink=q-jlink;free(q); /在i鏈表中刪除該邊G.arcnum-;return OK;/Delete_Arc 7.19 Status Build_AdjMulis

11、t(AMLGraph &G)/輸入有向圖的頂點數(shù),邊數(shù),頂點信息和邊的信息建立鄰接多重表InitAMLGraph(G);scanf(%d,&v);if(v0) return ERROR; /頂點數(shù)不能為負(fù)G.vexnum=v;scanf(%d,&a);if(a0) return ERROR; /邊數(shù)不能為負(fù)G.arcnum=a;for(m=0;mv;m+)G.adjmulistm.data=getchar(); /輸入各頂點的符號for(m=1;m=a;m+)t=getchar();h=getchar(); /t為弧尾,h為弧頭if(i=LocateVex(G,t)0) return ERRO

12、R;if(j=LocateVex(G,h)ivex=i;p-jvex=j;p-ilink=NULL;p-jlink=NULL; /邊結(jié)點賦初值if(!G.adjmulisti.firstedge) G.adjmulisti.firstedge=p;elseq=G.adjmulisti.firstedge;while(q)r=q;if(q-ivex=i) q=q-ilink;else q=q-jlink;if(r-ivex=i) r-ilink=p;/注意i值既可能出現(xiàn)在邊結(jié)點的ivex域中,else r-jlink=p; /又可能出現(xiàn)在邊結(jié)點的jvex域中/else /插入i鏈表尾部if(!G

13、.adjmulistj.firstedge) G.adjmulistj.firstedge=p;elseq=G.adjmulisti.firstedge;while(q)r=q;if(q-jvex=j) q=q-jlink;else q=q-ilnk;if(r-jvex=j) r-jlink=p;else r-ilink=p;/else /插入j鏈表尾部/forreturn OK;/Build_AdjList 7.20 int Pass_MGraph(MGraph G)/判斷一個鄰接矩陣存儲的有向圖是不是可傳遞的,是則返回1,否則返回0for(x=0;xG.vexnum;x+)for(y=0;

14、yG.vexnum;y+)if(G.arcsxy)for(z=0;zG.vexnum;z+)if(z!=x&G.arcsyz&!G.arcsxz) return 0;/圖不可傳遞的條件/ifreturn 1;/Pass_MGraph分析:本算法的時間復(fù)雜度大概是O(n2*d). 7.21 int Pass_ALGraph(ALGraph G)/判斷一個鄰接表存儲的有向圖是不是可傳遞的,是則返回1,否則返回0for(x=0;xnextarc)y=p-adjvex;for(q=G.verticesy.firstarc;q;q=q-nextarc)z=q-adjvex;if(z!=x&!is_adj

15、(G,x,z) return 0;/for/for/Pass_ALGraph int is_adj(ALGraph G,int m,int n)/判斷有向圖G中是否存在邊(m,n),是則返回1,否則返回0for(p=G.verticesm.firstarc;p;p=p-nextarc)if(p-adjvex=n) return 1;return 0;/is_adj 7.22 int visitedMAXSIZE; /指示頂點是否在當(dāng)前路徑上 int exist_path_DFS(ALGraph G,int i,int j)/深度優(yōu)先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回1,否則返回0

16、if(i=j) return 1; /i就是jelsevisitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!visitedk&exist_path(k,j) return 1;/i下游的頂點到j(luò)有路徑/for/else/exist_path_DFS 7.23 int exist_path_BFS(ALGraph G,int i,int j)/廣度優(yōu)先判斷有向圖G中頂點i到頂點j是否有路徑,是則返回1,否則返回0int visitedMAXSIZE;InitQueue(Q);EnQueue(Q,i);while(!Q

17、ueueEmpty(Q)DeQueue(Q,u);visitedu=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(k=j) return 1;if(!visitedk) EnQueue(Q,k);/for/whilereturn 0;/exist_path_BFS 7.24 void STraverse_Nonrecursive(Graph G)/非遞歸遍歷強連通圖Gint visitedMAXSIZE;InitStack(S);Push(S,GetVex(S,1); /將第一個頂點入棧visit(1);visited=1;w

18、hile(!StackEmpty(S)while(Gettop(S,i)&i)j=FirstAdjVex(G,i);if(j&!visitedj)visit(j);visitedj=1;Push(S,j); /向左走到盡頭/whileif(!StackEmpty(S)Pop(S,j);Gettop(S,i);k=NextAdjVex(G,i,j); /向右走一步if(k&!visitedk)visit(k);visitedk=1;Push(S,k);/if/while/Straverse_Nonrecursive分析:本算法的基本思想與二叉樹的先序遍歷非遞歸算法相同,請參考6.37.由于是強連

19、通圖,所以從第一個結(jié)點出發(fā)一定能夠訪問到所有結(jié)點. 7.25 見書后解答. 7.26 Status TopoNo(ALGraph G)/按照題目要求順序重排有向圖中的頂點int newMAXSIZE,indegreeMAXSIZE; /儲存結(jié)點的新序號n=G.vexnum;FindInDegree(G,indegree);InitStack(S);for(i=1;inextarc)k=p-adjvex;if(!(-indegreek) Push(S,k);/for/whileif(countG.vexnum) return ERROR; /圖中存在環(huán)for(i=1;i0)visitedi=1;

20、for(p=G.verticesi.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)if(exist_path_len(G,l,j,k-1) return 1; /剩余路徑長度減一/forvisitedi=0; /本題允許曾經(jīng)被訪問過的結(jié)點出現(xiàn)在另一條路徑中/elsereturn 0; /沒找到/exist_path_len 7.28 int pathMAXSIZE,visitedMAXSIZE; /暫存遍歷過程中的路徑 int Find_All_Path(ALGraph G,int u,int v,int k)/求有向圖G中頂點u到v之間的所有簡

21、單路徑,k表示當(dāng)前路徑長度pathk=u; /加入當(dāng)前路徑中visitedu=1;if(u=v) /找到了一條簡單路徑printf(Found one path!n);for(i=0;pathi;i+) printf(%d,pathi); /打印輸出elsefor(p=G.verticesu.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl) Find_All_Path(G,l,v,k+1); /繼續(xù)尋找visitedu=0;pathk=0; /回溯/Find_All_Path main().Find_All_Path(G,u,v,0); /在主函數(shù)

22、中初次調(diào)用,k值應(yīng)為0./main 7.29 int GetPathNum_Len(ALGraph G,int i,int j,int len)/求鄰接表方式存儲的有向圖G的頂點i到j(luò)之間長度為len的簡單路徑條數(shù)if(i=j&len=0) return 1; /找到了一條路徑,且長度符合要求else if(len0)sum=0; /sum表示通過本結(jié)點的路徑數(shù)visitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)sum+=GetPathNum_Len(G,l,j,len-1)/剩余路徑長度減一/

23、forvisitedi=0; /本題允許曾經(jīng)被訪問過的結(jié)點出現(xiàn)在另一條路徑中/elsereturn sum;/GetPathNum_Len 7.30 int visitedMAXSIZE;int pathMAXSIZE; /暫存當(dāng)前路徑int cyclesMAXSIZEMAXSIZE; /儲存發(fā)現(xiàn)的回路所包含的結(jié)點int thiscycleMAXSIZE; /儲存當(dāng)前發(fā)現(xiàn)的一個回路int cycount=0; /已發(fā)現(xiàn)的回路個數(shù) void GetAllCycle(ALGraph G)/求有向圖中所有的簡單回路for(v=0;vG.vexnum;v+) visitedv=0;for(v=0;vn

24、extarc)w=p-adjvex;if(!visitedw) DFS(G,w,k+1);else /發(fā)現(xiàn)了一條回路for(i=0;pathi!=w;i+); /找到回路的起點for(j=0;pathi+j;i+) thiscyclej=pathi+j;/把回路復(fù)制下來if(!exist_cycle() cyclescycount+=thiscycle;/如果該回路尚未被記錄過,就添加到記錄中for(i=0;iG.vexnum;i+) thiscyclei=0; /清空目前回路數(shù)組/else/forpathk=0;visitedk=0; /注意只有當(dāng)前路徑上的結(jié)點visited為真.因此一旦遍

25、歷中發(fā)現(xiàn)當(dāng)前結(jié)點visited為真,即表示發(fā)現(xiàn)了一條回路/DFS int exist_cycle()/判斷thiscycle數(shù)組中記錄的回路在cycles的記錄中是否已經(jīng)存在int tempMAXSIZE;for(i=0;icycount;i+) /判斷已有的回路與thiscycle是否相同 /也就是,所有結(jié)點和它們的順序都相同j=0;c=thiscycle� /例如,142857和857142是相同的回路for(k=0;cyclesik!=c&cyclesik!=0;k+);/在cycles的一個行向量中尋找等于thiscycle第一個結(jié)點的元素if(cyclesik) /有與之相同的

26、一個元素for(m=0;cyclesik+m;m+)tempm=cyclesik+m;for(n=0;nk;n+,m+)tempm=cyclesin; /調(diào)整cycles中的當(dāng)前記錄的循環(huán)相位并放入temp數(shù)組中if(!StrCompare(temp,thiscycle) /與thiscycle比較return 1; /完全相等for(m=0;mG.vexnum;m+) tempm=0; /清空這個數(shù)組/forreturn 0; /所有現(xiàn)存回路都不與thiscycle完全相等/exist_cycle分析:這個算法的思想是,在遍歷中暫存當(dāng)前路徑,當(dāng)遇到一個結(jié)點已經(jīng)在路徑之中時就表明存在一條回路;

27、掃描路徑向量path可以獲得這條回路上的所有結(jié)點.把結(jié)點序列(例如,142857)存入thiscycle中;由于這種算法中,一條回路會被發(fā)現(xiàn)好幾次,所以必須先判斷該回路是否已經(jīng)在cycles中被記錄過,如果沒有才能存入cycles的一個行向量中.把cycles的每一個行向量取出來與之比較.由于一條回路可能有多種存儲順序,比如142857等同于285714和571428,所以還要調(diào)整行向量的次序,并存入temp數(shù)組,例如,thiscycle為142857第一個結(jié)點為1,cycles的當(dāng)前向量為857142,則找到后者中的1,把1后部分提到1前部分前面,最終在temp中得到142857,與this

28、cycle比較,發(fā)現(xiàn)相同,因此142857和857142是同一條回路,不予存儲.這個算法太復(fù)雜,很難保證細(xì)節(jié)的準(zhǔn)確性,大家理解思路便可.希望有人給出更加簡捷的算法. 7.31 int visitedMAXSIZE;int finishedMAXSIZE;int count; /count在第一次深度優(yōu)先遍歷中用于指示finished數(shù)組的填充位置 void Get_SGraph(OLGraph G)/求十字鏈表結(jié)構(gòu)儲存的有向圖G的強連通分量count=0;for(v=0;vG.vexnum;v+) visitedv=0;for(v=0;vG.vexnum;v+) /第一次深度優(yōu)先遍歷建立fin

29、ished數(shù)組if(!visitedv) DFS1(G,v);for(v=0;v=0;i-) /第二次逆向的深度優(yōu)先遍歷v=finished(i);if(!visitedv)printf(n); /不同的強連通分量在不同的行輸出DFS2(G,v);/for/Get_SGraph void DFS1(OLGraph G,int v)/第一次深度優(yōu)先遍歷的算法visitedv=1;for(p=G.xlistv.firstout;p;p=p-tlink)w=p-headvex;if(!visitedw) DFS1(G,w);/forfinished+count=v; /在第一次遍歷中建立finish

30、ed數(shù)組/DFS1 void DFS2(OLGraph G,int v)/第二次逆向的深度優(yōu)先遍歷的算法visitedv=1;printf(%d,v); /在第二次遍歷中輸出結(jié)點序號for(p=G.xlistv.firstin;p;p=p-hlink)w=p-tailvex;if(!visitedw) DFS2(G,w);/for/DFS2分析:求有向圖的強連通分量的算法的時間復(fù)雜度和深度優(yōu)先遍歷相同,也為O(n+e). 7.32 void Forest_Prim(ALGraph G,int k,CSTree &T)/從頂點k出發(fā),構(gòu)造鄰接表結(jié)構(gòu)的有向圖G的最小生成森林T,用孩子兄弟鏈表存儲f

31、or(j=0;jnextarc)if(p-adjvex=k) closedgej.lowcost=p-cost;/ifclosedgek.lowcost=0;for(i=1;iG.vexnum;i+)k=minimum(closedge);if(closedgek.lowcostnextarc)if(p-costadjvex.lowcost)closedgep-adjvex=k,p-cost;/ifelse Forest_Prim(G,k); /對另外一個連通分量執(zhí)行算法/for/Forest_Prim void Addto_Forest(CSTree &T,int i,int j)/把邊(i

32、,j)添加到孩子兄弟鏈表表示的樹T中p=Locate(T,i); /找到結(jié)點i對應(yīng)的指針p,過程略q=(CSTNode*)malloc(sizeof(CSTNode);q-data=j;if(!p) /起始頂點不屬于森林中已有的任何一棵樹p=(CSTNode*)malloc(sizeof(CSTNode);p-data=i;for(r=T;r-nextsib;r=r-nextsib);r-nextsib=p;p-firstchild=q; /作為新樹插入到最右側(cè)else if(!p-firstchild) /雙親還沒有孩子p-firstchild=q; /作為雙親的第一個孩子else /雙親已

33、經(jīng)有了孩子for(r=p-firstchild;r-nextsib;r=r-nextsib);r-nextsib=q; /作為雙親最后一個孩子的兄弟/Addto_Forest main().T=(CSTNode*)malloc(sizeof(CSTNode); /建立樹根T-data=1;Forest_Prim(G,1,T);./main分析:這個算法是在Prim算法的基礎(chǔ)上添加了非連通圖支持和孩子兄弟鏈表構(gòu)建模塊而得到的,其時間復(fù)雜度為O(n2). 7.33 typedef struct int vex; /結(jié)點序號 int ecno; /結(jié)點所屬的連通分量號 VexInfo;VexInfo

34、 vexsMAXSIZE; /記錄結(jié)點所屬連通分量號的數(shù)組 void Init_VexInfo(VexInfo &vexs ,int vexnum)/初始化for(i=0;i1)GetMinEdge(EdgeSet,u,v); /選出最短邊if(!is_ec(vexs,u,v) /u和v屬于不同連通分量Addto_CSTree(T,u,v); /加入到生成樹中merge_ec(vexs,vexsu.ecno,vexsv.ecno); /合并連通分量ecnum-;DelMinEdge(EdgeSet,u,v); /從邊集中刪除/while/MinSpanTree_Kruscal void Add

35、to_CSTree(CSTree &T,int i,int j)/把邊(i,j)添加到孩子兄弟鏈表表示的樹T中p=Locate(T,i); /找到結(jié)點i對應(yīng)的指針p,過程略q=(CSTNode*)malloc(sizeof(CSTNode);q-data=j;if(!p-firstchild) /雙親還沒有孩子p-firstchild=q; /作為雙親的第一個孩子else /雙親已經(jīng)有了孩子for(r=p-firstchild;r-nextsib;r=r-nextsib);r-nextsib=q; /作為雙親最后一個孩子的兄弟/Addto_CSTree分析:本算法使用一維結(jié)構(gòu)體變量數(shù)組來表示等

36、價類,每個連通分量所包含的所有結(jié)點屬于一個等價類.在這個結(jié)構(gòu)上實現(xiàn)了初始化,判斷元素是否等價(兩個結(jié)點是否屬于同一個連通分量),合并等價類(連通分量)的操作. 7.34 Status TopoSeq(ALGraph G,int new )/按照題目要求給有向無環(huán)圖的結(jié)點重新編號,并存入數(shù)組new中int indegreeMAXSIZE; /本算法就是拓?fù)渑判騀indIndegree(G,indegree);Initstack(S);for(i=0;inextarc)k=p-adjvex;if(!(-indegreek) Push(S,k);/whileif(countG.vexnum) ret

37、urn ERROR;return OK;/TopoSeq 7.35 int visitedMAXSIZE; void Get_Root(ALGraph G)/求有向無環(huán)圖的根,如果有的話for(v=0;vG.vexnum;v+)for(w=0;wG.vexnum;w+) visitedw=0;/每次都要將訪問數(shù)組清零DFS(G,v); /從頂點v出發(fā)進行深度優(yōu)先遍歷for(flag=1,w=0;wnextarc)w=p-adjvex;if(!visitedw) DFS(G,w);/DFS 7.36 void Fill_MPL(ALGraph &G)/為有向無環(huán)圖G添加MPL域FindIndeg

38、ree(G,indegree);for(i=0;inextarc)j=p-adjvex;if(G.verticesj.MPL=0) k=Get_MPL(G,j);if(kmax) max=k; /求其直接后繼頂點MPL的最大者G.verticesi=max+1;/再加一,就是當(dāng)前頂點的MPLreturn max+1;/else/Get_MPL 7.37 int maxlen,pathMAXSIZE; /數(shù)組path用于存儲當(dāng)前路徑int mlpMAXSIZE; /數(shù)組mlp用于存儲已發(fā)現(xiàn)的最長路徑 void Get_Longest_Path(ALGraph G)/求一個有向無環(huán)圖中最長的路徑m

39、axlen=0;FindIndegree(G,indegree);for(i=0;iG.vexnum;i+)for(j=0;jmaxlen&!G.verticesi.firstarc) /新的最長路徑for(j=0;jnextarc)j=p-adjvex;if(!visitedj) DFS(G,j,len+1);/elsepathi=0;visitedi=0;/DFS 7.38 void NiBoLan_DAG(ALGraph G)/輸出有向無環(huán)圖形式表示的表達式的逆波蘭式FindIndegree(G,indegree);for(i=0;iadjvex);PrintNiBoLan_DAG(G,

40、p-nexarc-adjvex);printf(%c,c);/PrintNiBoLan_DAG 7.39 void PrintNiBoLan_Bitree(Bitree T)/在二叉鏈表存儲結(jié)構(gòu)上重做上一題if(T-lchild) PrintNiBoLan_Bitree(T-lchild);if(T-rchild) PrintNiBoLan_Bitree(T-rchild);printf(%c,T-data);/PrintNiBoLan_Bitree 7.40 int Evaluate_DAG(ALGraph G)/給有向無環(huán)圖表示的表達式求值FindIndegree(G,indegree);for(i=0;iG.vexnum;i+)if(!indegreei) r=i; /找到有向無環(huán)圖的根return Evaluate_imp(G,i);/NiBoLan_DAG int Evaluate_imp(ALGraph G,int i)/求子表達式的值if(G.verticesi.tag=NUM) return G.verticesi.value;elsep=G.verticesi.firstarc;v1=Eva