2018年國(guó)家電網(wǎng)考試備考計(jì)算機(jī)之?dāng)?shù)據(jù)結(jié)構(gòu)與算法(13)

對(duì)于無(wú)向圖，一條邊對(duì)應(yīng)都是兩個(gè)頂點(diǎn)，所以，在循環(huán)中，一次就針對(duì)i和j分布進(jìn)行插入。

本算法的時(shí)間復(fù)雜度，對(duì)于n個(gè)頂點(diǎn)e條邊來(lái)說(shuō)，很容易得出是O(n+e)。

1.3 十字鏈表

對(duì)于有向圖來(lái)說(shuō)，鄰接表是有缺陷的。關(guān)心了出度問(wèn)題，想了解入度就必須要遍歷整個(gè)圖才知道，反之，逆鄰接表解決了入度卻不了解出度情況。下面介紹的這種有向圖的存儲(chǔ)方法：十字鏈表，就是把鄰接表和逆鄰接表結(jié)合起來(lái)的。

重新定義頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)，如下所示。