一、鄰接表為什么不用set而用vector存儲

因?yàn)猷徑颖聿恍枰行?，它只是用來存邊的。鄰接表較好使用鏈?zhǔn)角跋蛐牵瑅ector存圖常數(shù)有點(diǎn)大。set的功能：有序、判重、查詢，這些對于鄰接表來說是累贅。鄰接表只需要把邊存下來并維護(hù)邊與邊之間的聯(lián)系即可。判重題目往往都會排除，有序和查詢就更用不到了。

鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。

由兩部分組成：表頭結(jié)點(diǎn)表和邊表。

鄰接表中每個單鏈表的名列前茅個結(jié)點(diǎn)存放有關(guān)頂點(diǎn)的信息，把這一結(jié)點(diǎn)看成鏈表的表頭，其余結(jié)點(diǎn)存放有關(guān)邊的信息

（1）表頭結(jié)點(diǎn)表：包括數(shù)據(jù)域和鏈域，數(shù)據(jù)域存儲頂點(diǎn)的名稱，鏈域用于指向鏈表中名列前茅個結(jié)點(diǎn)（與頂點(diǎn)鄰接的名列前茅個頂點(diǎn)）

（2）邊表：包括鄰接點(diǎn)域（指示與頂點(diǎn)鄰接的點(diǎn)在圖中的位置，即數(shù)組下標(biāo)）、數(shù)據(jù)域（存儲和邊相關(guān)的信息，如權(quán)值）、鏈域（指示與頂點(diǎn)鄰接的下一條邊的結(jié)點(diǎn)）。

延伸閱讀：

二、全局頁面置換算法

功能：

當(dāng)缺頁中斷發(fā)生，需要調(diào)入新的頁面而內(nèi)存已滿時，選擇內(nèi)存當(dāng)中哪個物理頁面被置換。

目標(biāo)：

盡可能地減少頁面的換進(jìn)換出次數(shù)（既缺頁中斷的次數(shù)）。具體來說，把未來不再使用的或短期內(nèi)較少使用的頁面換出，通常只能在局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計數(shù)據(jù)來進(jìn)行預(yù)測。

頁面鎖定（frame locking）：

用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時間關(guān)鍵（time-critical）的應(yīng)用程序。實(shí)現(xiàn)的方法是L在頁表中添加鎖定標(biāo)志位（lock bit）。使其不在頁面置換算法范圍之內(nèi)，也就說不會被換入換出。

通常只需要考慮頁號，因?yàn)槠铺栆话悴黄鹱饔?。只保留頁號。基于這個list來設(shè)計各種的頁面替換算法。
通過模擬一個頁面置換的行為并且記錄產(chǎn)生頁缺失數(shù)的數(shù)量。一般情況下，產(chǎn)生的缺頁次數(shù)越少，性能就越高。