一、鄰接表存儲無向圖回顧
鄰接表存儲無向圖
圖中紅色框住的部分媒殉，是B頂點與C頂點的邊担敌，我們可以看到在邊表中被表示了兩次，會導(dǎo)致刪除效率比較低（需要遍歷兩個頂點進行邊的刪除）
二廷蓉、無向圖的存儲結(jié)構(gòu)鄰接多重表法
2.1 鄰接多重表法定義
鄰接多重表法
頂點結(jié)構(gòu)定義
- data：數(shù)據(jù)域全封，存放頂點數(shù)據(jù)
- firstedge：第一條邊的指針
邊表節(jié)點結(jié)構(gòu)定義
- ivex：邊的兩個頂點其中一個頂點 i 的序號
- ilink：邊的兩個頂點其中一個頂點 i 的相連的下一條邊
- jvex：邊的兩個頂點其中一個頂點 j 的序號
-jlink：邊的兩個頂點其中一個頂點 j 的相連的下一條邊
-info：信息域，可以存放邊的信息
-mark：標記域桃犬，可以存放標記信息
2.2 鄰接多重表法示例
鄰接多重表法示例
三刹悴、鄰接多重表發(fā)C語言定義
鄰接多重表法C語言定義
四、十字鏈表法與鄰接多重表法對比
十字鏈表法與鄰接多重表法對比
共同點
- 都是鏈式存儲結(jié)構(gòu)
- 邊結(jié)構(gòu)都需要存放info域來保存權(quán)重
不同點
- 十字鏈表法針對有向圖
- 鄰接多重表法針對無向圖
- 十字鏈表法需要快速找到入邊與出邊攒暇，所以頂點結(jié)構(gòu)需要兩個邊指針
- 鄰接多重表法沒有入邊與出邊之分土匀，所以定點結(jié)構(gòu)只需要一個指針
