有向图的邻接表描述 c++
生活随笔
收集整理的這篇文章主要介紹了
有向图的邻接表描述 c++
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
有向圖的鄰接表表示法
圖的鄰接表表示法類似于樹的孩子鏈表表示法。對于圖G中的每個頂點(diǎn)vi，該方法把所有鄰接于vi的頂點(diǎn)vj鏈成一個帶頭結(jié)點(diǎn)的單鏈表，這個單鏈表就稱為頂點(diǎn)vi的鄰接表(Adjacency List)。
1． 鄰接表的結(jié)點(diǎn)結(jié)構(gòu)
（1）表結(jié)點(diǎn)結(jié)構(gòu)
? ??┌────┬───┐?
? ??│adjvex??│next??│
? ? └────┴───┘
? ? 鄰接表中每個表結(jié)點(diǎn)均有兩個域:
① 鄰接點(diǎn)域adjvex
存放與vi相鄰接的頂點(diǎn)vj的序號j。
② 鏈域next
將鄰接表的所有表結(jié)點(diǎn)鏈在一起。
??注意：
? ? 若要表示邊上的信息(如權(quán)值)，則在表結(jié)點(diǎn)中還應(yīng)增加一個數(shù)據(jù)域。
（2）頭結(jié)點(diǎn)結(jié)構(gòu)
? ??┌────┬─────┐?
? ??│vertex??│firstedge │
? ? └────┴─────┘
? ? 頂點(diǎn)vi鄰接表的頭結(jié)點(diǎn)包含兩個域：
① 頂點(diǎn)域vertex
存放頂點(diǎn)vi的信息
② 指針域firstedge
vi的鄰接表的頭指針。
??注意：
? ? ① 為了便于隨機(jī)訪問任一頂點(diǎn)的鄰接表，將所有頭結(jié)點(diǎn)順序存儲在一個向量中就構(gòu)成了圖的鄰接表表示。
? ? ② 有時希望增加對圖的頂點(diǎn)數(shù)及邊數(shù)等屬性的描述，可將鄰接表和這些屬性放在一起來描述圖的存儲結(jié)構(gòu)。
2.代碼實(shí)例
輸出結(jié)果為：
3.代碼實(shí)例2(ps:補(bǔ)充于2011-6-14)
? ? ? 總體而言，鄰接表表示法中主要含有兩種結(jié)點(diǎn)，分別是頭結(jié)點(diǎn)和表結(jié)點(diǎn)(也叫做邊結(jié)點(diǎn))，在頭結(jié)點(diǎn)(s)到表結(jié)點(diǎn)(d)之間存在著一條邊。如果頭結(jié)點(diǎn)后面有多個表結(jié)點(diǎn)，即s->d1->d2，則表示存在著兩條邊，分別是e(s,d1)和e(s,d2)。鄰接表表示法中，頭結(jié)點(diǎn)的數(shù)量是固定的，就是圖中的頂點(diǎn)數(shù)量V，表結(jié)點(diǎn)的數(shù)量由邊的數(shù)量來決定。如果是有向圖，表結(jié)點(diǎn)的數(shù)量=邊的數(shù)量；如果是無向圖，則表結(jié)點(diǎn)的數(shù)量=邊的數(shù)量*2。
? ? ? 在構(gòu)造圖的時候，如果一個頭結(jié)點(diǎn)后面有多個表結(jié)點(diǎn)，那么表結(jié)點(diǎn)按次序添加在頭結(jié)點(diǎn)后面。比如原先有結(jié)構(gòu)s->d1->d2，現(xiàn)在需要添加表結(jié)點(diǎn)d3，那么需要打斷s->d1的指針，讓d3指向d1，s指向d3。即s->d3->d1->d2。
總結(jié)
以上是生活随笔為你收集整理的有向图的邻接表描述 c++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CDH、CM下载403，Cloudera
- 下一篇： ClouderaManager agen