基本介紹
- 中文名：優先選擇權
- 外文名：first refusal right
- 別名：優先度優先搜尋
- 簡稱：PFS
- 定義：結點優先值的高低決定其訪問順序
- 套用學科：計算機原理
概述,算法,
概述
優先度優先搜尋PFS與DFS，BFS方式都不同，它在選擇下一個被訪問的鄰接頂點時，是根據頂點的優先權作為標準的。首先，假定從某個頂點開始，進行優先度優先搜尋，訪問該頂點並做訪問標誌。接著，考察它的鄰接頂點的優先權，取優先權最高的鄰接頂點進行訪問，同樣訪問並作訪問標誌。依次類推，直至所有的頂點都被訪問完為止。在具體實現時，可以採取和廣度優先搜尋類似的方式，只不過將佇列換成優先佇列而已。
如果每個進隊的頂點的優先權總是比上一次進隊的頂點的優先權低，那么優先佇列的功能與普通的佇列完全一樣。那么，優先度優先搜尋PFS和廣度優先搜尋是相同的。如果每個進隊的頂點的優先權都比上一次進隊的頂點的優先權高。那么優先佇列的功能與棧類似，並且搜尋方式和深度優先搜尋DFS是完全一樣的。
在求圖的最短路徑時的Dijktra算法，實際上就是優先度優先搜尋PFS的一種套用。
算法
procedure pfs； {priority first search．}
procedure visit(n：node)；
begin
將插入到優先佇列Priority queue；
while優先佇列非空時；
得到優先權最高的結點，且處理它(包括把其狀態值status改變為processed)，把它的任何一個狀態status為Waiting的鄰接結點進入到優先佇列priorit/queue，這些結點的狀態status將改變為ready。如果狀態status為ready的結點被給出了一個新的優先值，則和原來的優先值進行比較。若新的優先渣比原來的優先值高，則用新的優先值取代老的優先值。
end；
begin
initstatus；
for每個在圖G中的結點，比如n
if n的狀態status值為waiting
then visit(n)
end；
如果每個進隊的結點的優先值比上次進隊的結點的優先值低，則優先佇列的功能和普通佇列沒有二樣，那么優先度優先搜尋將和寬度優先搜尋相同．如果每個迸從的結點的優先值比上次進隊的結點優先值高，則優先佇列的功能和棧相似，並且搜尋方式和深度優先搜尋完全一樣。
