當一個AOV網用鄰接表表示時可按下列方法進行拓撲排序
()．查鄰接表中入度為______的頂點並進棧
()．若棧不空則①輸出棧頂元素Vj並退棧②查Vj的直接後繼Vk對Vk入度處理處理方法是______
()．若棧空時輸出頂點數小於圖的頂點數說明有______否則拓撲排序完成【南京理工大學 二 (分)】
．已知圖的鄰接表結構為
CONST vtxnum={圖的頂點數}
TYPE vtxptr=vtxnum;
arcptr=^arcnode;
arcnode=RECORD adjvex:vtxptr; nextarc:arcptr END;
vexnode=RECORD vexdata:{和頂點相關的信息}firstarc:arcptr END;
adjlist=ARRAY[vtxptr]OF vexnode;
本算法是實現圖的深度優先遍歷的非遞歸算法其中使用一個順序棧stack棧頂指針為topvisited為標志數組
PROC dfs(g:adjlist;v:vtxptr);
top=; write(v); visited[v]:=ture; p:=g[v]firstarc;
WHILE (top<>)OR(p<>NIL)DO
[WHILE()_______DO
[v:=p^adjvex;
IF()_______ THEN p:=p^nextarc
ELSE [write(v); visited[v]:=true; top:=top+; stack[top]:=p; ()_______] ]
IF top<> THEN[p:=stack[top]; top:=top; ()_______]
]
ENDP 【同濟大學 二 (分)】
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23129.html
