????小編在上篇簡(jiǎn)書簡(jiǎn)單介紹了有關(guān)圖的一些基本的性質(zhì)牙丽，那如何去存儲(chǔ)圖呢皆撩？首先，圖的頂點(diǎn)之間的關(guān)系是m:n骤视，即任何兩個(gè)頂點(diǎn)之間都可能存在關(guān)系（邊），無法通過存儲(chǔ)位置表示這種任意的邏輯關(guān)系鹃觉，所以专酗，圖無法采用順序存儲(chǔ)結(jié)構(gòu)〉辽龋考慮圖的定義祷肯，圖是由頂點(diǎn)和邊組成的，分別考慮如何存儲(chǔ)頂點(diǎn)疗隶、如何存儲(chǔ)邊佑笋。圖的鄰接矩陣的存儲(chǔ)方式是用兩個(gè)數(shù)組來實(shí)現(xiàn)的，一個(gè)一維數(shù)組存儲(chǔ)頂點(diǎn)信息抽减，一個(gè)二維數(shù)組存儲(chǔ)線（無向圖）或辉是唷（有向圖）的信息。
????（1）無向圖的鄰接矩陣
????假設(shè)圖G＝(V卵沉，E)有n個(gè)頂點(diǎn)，則鄰接矩陣是一個(gè)n×n的方陣法牲，定義為：
? ??無向圖鄰接矩陣的特點(diǎn)為：主對(duì)角線一定為0且為對(duì)稱矩陣
????求無向圖頂點(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】
????代碼如下：
????接下來我們簡(jiǎn)單分析下該算法的時(shí)間復(fù)雜度。
????從上述的代碼截圖中命贴，我們可以發(fā)現(xiàn)程序執(zhí)行步驟最多的為CreateMGraph這個(gè)函數(shù)道宅，而該函數(shù)程序執(zhí)行步驟最多為3個(gè)for循環(huán)語句食听。
????第一個(gè)for循環(huán)語句循環(huán)n次【n為輸入的頂點(diǎn)個(gè)數(shù)】，第二次for循環(huán)語句循環(huán)n的平方次污茵，第三次for循環(huán)語句循環(huán)e次【e為圖中的邊數(shù)】樱报，在這里我們先忽略其它賦值語句執(zhí)行的次數(shù)，得到的執(zhí)行步數(shù)為n^2+n+e泞当。當(dāng)n越來越大時(shí)迹蛤，n^2將開始占據(jù)主導(dǎo)地位，其它項(xiàng)目也可以忽略襟士，因此我們就可以把代表程序總執(zhí)行步數(shù)的記為O(n^2)盗飒。
