在圖(下圖)所示的各無向圖中
()找出所有的簡單環
()哪些圖是連通圖?對非連通圖給出其連通分量
()哪些圖是自由樹(或森林)?
在圖所示(下圖)的有向圖中
() 該圖是強連通的嗎? 若不是則給出其強連通分量
() 請給出所有的簡單路徑及有向環
() 請給出每個頂點的度入度和出度
() 請給出其鄰接表鄰接矩陣及逆鄰接表
假設圖的頂點是AB請根據下述的鄰接矩陣畫出相應的無向圖或有向圖
┌ ┓
┌ ┓ | |
| | | |
| | | |
| | | |
| | | |
┕ ┙ ┕ ┙
(a) (b)
假設一棵完全二叉樹包括ABC等七個結點寫出其鄰接表和鄰接矩陣
對n個頂點的無向圖和有向圖采用鄰接矩陣和鄰接表表示時如何判別下列有關問題?
() 圖中有多少條邊?
() 任意兩個頂點i和j是否有邊相連?
() 任意一個頂點的度是多少?
n個頂點的連通圖至少有幾條邊?強連通圖呢?
DFS和BFS遍歷各采用什麼樣的數據結構來暫存頂點?當要求連通圖的生成樹的高度最小應采用何種遍歷?
畫出以頂點v為初始源點遍歷圖(下圖)所示的有向圖所得到的DFS 和BFS生成森林
按順序輸入頂點對()()()()()()()()()()()根據第節中算法CreatALGraph畫出相應的鄰接表並寫出在該鄰接表上從頂點開始搜索所得的DFS和BFS序列及DFS和BFS生成樹
什麼樣的圖其最小生成樹是唯一的?用PRIM 和Kruskal求最小生成樹的時間各為多少?它們分別適合於哪類圖?
對圖（下圖）所示的連通圖請分別用Prim和Kruskal算法構造其最小生成樹
對圖（下圖）所示的有向圖試利用Dijkstra算法求出從源點到其它各頂點的最短路徑並寫出執行算法過程中擴充紅點集的每次循環狀態(見表)
試寫出圖（下圖）所示有向圖的所有拓撲序列並指出就用節給出的NonPreFirstTopSort算法求得的是哪個序列設鄰接表的邊表結點中的鄰接點序號是遞增有序的
什麼樣的DAG的拓撲序列是唯一的?
請以V為源點給出用DFS搜索圖（上圖）得到的逆拓撲序列
From:http://tw.wingwit.com/Article/program/sjjg/201311/23789.html
