浙江大學-數據結構-小白專場：C語言實現如何建立圖-6.5.1

小白專場：如何建立圖

用鄰接矩陣表示圖

剛剛講到，圖主要有兩種表示方法，一種是鄰接矩陣，一種是用鄰接表，我們先從簡單的開始，來考慮一下用鄰接矩陣表示的圖在程序裡面怎麼寫出來，用鄰接矩陣表示圖非常簡單，主要的就是一個矩陣，也就是在程序里對應的二維數組，如果 和 是有一條邊的話，那麼相應的第i,j個元素就等於1，如果沒有邊的話就等於0，這是當我們在說一個無權圖的時候，如果這個圖是有權的話，那麼當有一條邊的時候，應該對應的是它的權重，沒有邊的時候，有可能是0，有可能是無窮大，那麼在程序里怎麼寫呢？其實一個非常簡單直觀的寫法，我就定義一個二維的數組，那這個數組的大小是由它的MaxVertexNum,是由這個圖裡面所有頂點的數量決定的，前面把這個二維數組的類型定義為WeightType,這是一個抽象的寫法，大多數情況下它就是個整型的，但是它有時候也有可能是double類型的，甚至有可能是字元類型的，都是有可能的，這個根據具體的情況，到前面去定義，在這我們抽象的把它寫成WeightType,除此之外，關於這個圖還有兩個很重要的變數需要定義，一個是它的頂點數，一個是它的邊數，其實如果是在考試的時候，讓你寫一個圖的話呢，這麼寫就已經夠了，因為它比較簡單快捷，但是我們是想成為真正的程序員的騷年，而不是碼農2333，所以寫的程序儘可能的通用，而且要讓別人看的懂，所以回到鄰接矩陣表示的圖，如果就這樣簡單實現一個圖的話，有一個顯然的問題，兩個變數Nv,Ne,當別人在用你這個模塊的時候，他有可能不理解這兩個變數的含義，

那麼我們現在要保證的告訴他說，這兩個東西Nv,Ne是跟圖是一體的，既然它們是一體的，我們就得把它們打一個包，打在一個結構體裡面，於是我們就定義這樣一個結構體

把結構體的結點起個名字叫GNode, 那麼我習慣於在結構體的前面加一個PtrToGNode,就是指向結構體的指針，那麼我們把鄰接矩陣存儲的圖的類型取個名字叫MGraph,M代表Matrix,

矩陣的縮寫，那麼把這個類型就定義為指向這個結點的指針，為什麼要把它定義為指向結點的指針而不是就把這個結點本身叫做一個圖呢？那是因為我們在後面，向函數裡面傳遞一個圖的時候，肯定傳一個指針進去比較方便，而不是把整個結點複製到那個函數裡面，在這裡頭還可能存在的一個數組我們把它取個名字叫Data,它是用來存頂點的數據的，也就是當處理某一類問題的時候，和圖裡的每一個頂點它有自己的一個意義，在圖的每一個頂點裡面還要存一些東西，這個DataType有可能是任何東西，它甚至有可能是一個Struct, 那麼到此為止就完成了圖的定義

接下來我們就看怎麼在程序裡面建立一個圖