第四部分 圖[10]

    試題
　　
　　【年真題】
　　
　　下列關於無向連通圖特性的敘述中正確的是
　　I所有頂點的度之和為偶數
　　II邊數大於頂點個數減
　　III至少有一個頂點的度為
　　
　　A只有I   B只有II   CI和II   DI和III
　　
　　答案A
　　
　　（分）帶權圖（權值非負表示邊連接的兩頂點間的距離）的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑假定從初始頂點到目標頂點之間存在路徑現有一種解決該問題的方法
　　①設最短路徑初始時僅包含初始頂點令當前頂點u為初始頂點
　　②選擇離u最近且尚未在最短路徑中的一個頂點v加入到最短路徑中修改當前頂點u=v
　　③重復步驟②直到u是目標頂點時為止
　　清問上述方法能否求得最短路徑？若該方法可行請證明之否則請舉例說明
　　
　　參考答案
　　該方法求得的路徑不一定是最短路徑例如對於下圖所示的帶權圖如果按照題中的原則從A到C的最短路徑為A→B→C事實上其最短路徑為A→D→C

    返回《數據結構》考研復習精編

[]  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23296.html