試在無向圖的鄰接矩陣和鄰接鏈表上實現如下算法
(
)往圖中插入一個頂點
(
)往圖中插入一條邊
(
)刪去圖中某頂點
(
)刪去圖中某條邊
下面的偽代碼是一個廣度優先搜索算法試以圖(下圖)中的v為源點執行該算法請回答下述問題
()對圖中頂點vn+它需入隊多少次？它被重復訪問多少次?
()若要避免重復訪問同一個頂點的錯誤應如何修改此算法?
void BFS(ALGraph *Gint k)
{//以下省略局部變量的說明visited各分量初值為假
InitQueue(&Q);//置空隊列
EnQueue(&Qk);//k入隊
while(!QueueEmpty(&Q)){
i=DeQueue(&Q);//vi出隊
visited[i]=TRUE;//置訪問標記
printf(%cG>adjlist[i]vertex;//訪問vi
for(p=G>adjlist[i]firstedge;p;p=p>next)
//依次搜索vi的鄰接點vj(不妨設p>adjvex=j)
if(!visited[p>adjvex])//若vj沒有訪問過
EnQueue(&Qp>adjvex);//vj入隊
}//endofwhile
}//BFS
試以鄰接表和鄰接矩陣為存儲結構分別寫出基於DFS和BFS遍歷的算法來判別頂點vi和vj(i<>j)之間是否有路徑
試分別寫出求DFS和BFS生成樹(或生成森林)的算法要求打印出所有的樹邊
寫一算法求連通分量的個數並輸出各連通分量的頂點集
設圖中各邊的權值都相等試以鄰接矩陣和鄰接表為存儲結構分別寫出算法
()求頂點vi到頂點vj(i<>j)的最短路徑
()求源點vi到其余各頂點的最短路徑
要求輸出路徑上的所有頂點(提示利用BFS遍歷的思想)
以鄰接表為存儲結構寫一個基於DFS遍歷策略的算法求圖中通過某頂點vk的簡單回路(若存在)
寫一算法求有向圖的所有根(若存在)分析算法的時間復雜度
改寫節的算法Print使輸出的從源點到各終點的最短路徑是正向的(提示使用棧暫存路徑)
對節的NonSuccFirstTopSort算法求精分別以鄰接矩陣和鄰接表作為存儲結構寫出其具體算法並分析算法的時間
設一個有向圖DAG試以鄰接矩陣和鄰接表作為存儲結構寫出對節的DFSTopSort求精算法為什麼有向圖不是DAG時該算法不能正常工作?
利用拓撲排序算法的思想寫一算法判別有向圖中是否存在有向環當有向環存在時輸出構成環的頂點
From:http://tw.wingwit.com/Article/program/sjjg/201311/23672.html
