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

02-25

向MGraph中插入邊

那前面我們已經初始化了一個有所有的頂點但是一條邊都沒有的圖，那麼接下來要做的動作就是每次向這個圖裡面插入一條邊，那麼現在我們的問題又來了，首先你得有一條邊，那麼這個Edge邊的類型要怎麼定義呢？其實每一種結構都可以模仿剛才圖結點的定義，先定義一個邊結點，然後定義它的PtrToENode,就是指向邊結點的指針(即typedef struct ENode *PtrToENode)，然後把邊定義為指向結點的指針(typedef PtrToENode Edge),當我們要插入一條邊的時候，就把這個指針傳進去，

那麼這個結點裡頭，應該包含些什麼東西呢？那我們先來考慮一下，你要定義一條邊，有哪些東西決定了一條邊呢？最基本的就是一條邊是由兩個頂點來決定的，如果我們在討論一個從V1指向V2的有向邊的時候，那我們就定義一個頂點是它的出發點，一個頂點是它的終點，那除了這兩個頂點之外，還可能有什麼呢？如果我們在討論無權圖的話呢，這樣就可以了，如果是有權圖的話呢，那當然還得定義一個權重，那麼這個權重的類型，是WeightType,跟我們前面鄰接矩陣的類型是一致的，在定義好了一條邊以後，我們就看怎麼往圖裡面插入一條邊，對於鄰接矩陣來說呢，插入一條邊是一件非常簡單的事情，就是把相應的權重賦給相應的鄰接矩陣的元素就可以了，所以如果我們插入的是V1,V2的話，那麼就把這個Graph裡面，鄰接矩陣對應的V1和V2的這個元素賦值為邊上面的權重，就這麼簡單，當然如果我們說的是無向圖的話，其實我們是要插入兩條邊的，如果是無向圖的話，還要把V2,V1也插進去，也就是把Graph裡面的Graph->G[E->V2][E->V1] = E->Weight賦值為它的權重，就完成這個插入。