1、1試基于圖的廣度優(yōu)先搜索策略寫一算法，判別以鄰接表方式存儲的有向圖中是否存在由頂點X到頂點Vj的路徑(iHj)。int fin dpath(Graph G,i nt i,i nt j)int v;int visitedG.vex nuin-I;Lin kQueue Q;Ini tQueue(Q;for(v=0;v<G.vex num;+v)visitedv=O;if(i=j)return 1;elseif(! visited i)visitedi=l;En Queue(Q,i);while(!QueueEmpry(Q)Dequeue(Q,u);for(w=FirstAdjVex(G,u)

2、;W>=0;w=NextAdjVex(G,u,w)if(!visited(w)visitedwl=l;En Queue(Q,w);if(visitedj=l)return 1;else return 0;思路：若i=j,則一定存在路。若i!=j,以頂點i為起始點，找到與i有路的所有頂點并讓他們的visiedlkj=l,循環(huán)結(jié)束后，看visitedUJM否恒等于1。若是，則存在從i至叮的路，否則不存在。2?請畫出以下無向帶權(quán)圖的鄰接矩陣和鄰接表，并按普里姆算法求其最小生成樹。鄰接矩陣cd3oooo oo8oo oo 1鄰接表頭結(jié)點3505OOCO5507oo987040559OO oooo

3、OOOO630ooooOO5OO2oo854ooOO63衣結(jié)點adjvex info5I5OOoo4l2o106 16n exttarcb- 1UI144b253/書；7 4dtc3d4 b 1S 6k5 35f6246£ :76 BBpdata firstarc7 h6361495 619AJ36A35A2SA04 APRIM算法:Clo$dgebcdef8huV-UKAdjvexaabed ?丄顯Lowcost43?)hCAdjvexgcc?，c九hbLowcost4055Adjvexb Sbc?Mdoghdlowcost0095Adjvexdddd?bud(”訃hLow:ost

4、0007654Adjvexdddobcdh8Lowcost0007650AdjvexdSa,b rcrdAh)e,ffLowcost0007200AdjvexfLowcost0003000心 tgh (?ee1591210試?yán)肈ijkstra算法求圖中從頂點 其他各頂點間的最短路徑，寫岀執(zhí) 算法過程中各步的狀態(tài)。DIST終占、八、i?l1x2i: 3is4Is51A6B15(a,b)15(afb)15(o,b)%b)%b)C2 (聯(lián))22222D12( 9td)ll(axtd)1111E8gc? d)lgc,d)101010F86(ix06666GOO816(?,cXg)I*")1

5、4?, C(?xO?xte)?xte.d仏仏 cgdbgY圖中編著為紅的的為a到各頂點的最短路徑4.試對下圖所示的AOE網(wǎng)絡(luò)，解答下列問題。注:活動可用點對表示，如 <1,2>=2, <l,3>=15o(1)這個工程最早可能在什么時間結(jié)束。答：最早可能在43后結(jié)束答:123456Ve(i)01915293843VI (i)01915373843(3)求每個活動的最早開始時間e()和最遲開始時間1()<1,2><1,3><3,2><3, 5><2,5><2, 4><5, 6><4, 6>e()001515191938291()170152719273837(4)確定哪些