????小編在上篇簡(jiǎn)書簡(jiǎn)單介紹了有關(guān)圖的一些基本的性質(zhì)，那如何去存儲(chǔ)圖呢？首先，圖的頂點(diǎn)之間的關(guān)系是m:n，即任何兩個(gè)頂點(diǎn)之間都可能存在關(guān)系（邊），無(wú)法通過(guò)存儲(chǔ)位置表示這種任意的邏輯關(guān)系，所以，圖無(wú)法采用順序存儲(chǔ)結(jié)構(gòu)?？紤]圖的定義，圖是由頂點(diǎn)和邊組成的，分別考慮如何存儲(chǔ)頂點(diǎn)、如何存儲(chǔ)邊。圖的鄰接矩陣的存儲(chǔ)方式是用兩個(gè)數(shù)組來(lái)實(shí)現(xiàn)的，一個(gè)一維數(shù)組存儲(chǔ)頂點(diǎn)信息，一個(gè)二維數(shù)組存儲(chǔ)線（無(wú)向圖）或?。ㄓ邢驁D）的信息。
????（1）無(wú)向圖的鄰接矩陣
????假設(shè)圖G＝(V，E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣，定義為：
? ??無(wú)向圖鄰接矩陣的特點(diǎn)為：主對(duì)角線一定為0且為對(duì)稱矩陣
????求無(wú)向圖頂點(diǎn)的度就是求鄰接矩陣第i行或第j列非零元素的個(gè)數(shù)
????判斷頂點(diǎn)i和j是否存在邊就是判斷Arc[i][j]是否為1
????求頂點(diǎn)i的所有鄰接點(diǎn)就是將數(shù)組中第i行重新掃描一遍，若Arc[i][j]為1，則頂點(diǎn)j為頂點(diǎn)i的鄰接點(diǎn)
????（2）有向圖的鄰接矩陣
????假設(shè)圖G＝(V，E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣，定義為：
????有向圖的鄰接矩陣不一定對(duì)稱，比如完全有向圖。
????有向圖中，頂點(diǎn)i的出度為第i行元素之和，入度為第j列元素之和【這里的有向圖中是指邊還未添加權(quán)值，默認(rèn)為1】
????代碼如下：
????接下來(lái)我們簡(jiǎn)單分析下該算法的時(shí)間復(fù)雜度。
????從上述的代碼截圖中，我們可以發(fā)現(xiàn)程序執(zhí)行步驟最多的為CreateMGraph這個(gè)函數(shù)，而該函數(shù)程序執(zhí)行步驟最多為3個(gè)for循環(huán)語(yǔ)句。
????第一個(gè)for循環(huán)語(yǔ)句循環(huán)n次【n為輸入的頂點(diǎn)個(gè)數(shù)】，第二次for循環(huán)語(yǔ)句循環(huán)n的平方次，第三次for循環(huán)語(yǔ)句循環(huán)e次【e為圖中的邊數(shù)】，在這里我們先忽略其它賦值語(yǔ)句執(zhí)行的次數(shù)，得到的執(zhí)行步數(shù)為n^2+n+e。當(dāng)n越來(lái)越大時(shí)，n^2將開始占據(jù)主導(dǎo)地位，其它項(xiàng)目也可以忽略，因此我們就可以把代表程序總執(zhí)行步數(shù)的記為O(n^2)。
