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

LGraph初始化

那實際上建立LGraph的過程跟建立MGraph的過程原理上來講是一樣的，我們都是初始化一個包含了一個所有的頂點但是一條邊都沒有的這麼一個圖，然後在一條邊一條邊插到這個圖裡面，最後就把一個完整的圖建立起來，只不過是實現這兩個步驟的細節略微有點區別，因為它們結構不一樣嘛，對於LGraph來說，前面這一塊都是一模一樣的，就是把前面M都換成L,僅此而已，我仍然是申明一個圖結點，然後把頂點個數賦值給它，邊的個數也先初始化好，最重要的是什麼叫沒有邊，在用鄰接矩陣表示的圖裡面，沒有邊就表示任意一對頂點之間，二維數組它的值或者是1或者是無窮大，但是在LGraph裡面什麼叫沒有邊呢？每一個頂點跟著那個鏈表都是空的，

對於這個Graph裡面鄰接表每一個頂點V來說，它的FirstEdge，它指向第一條邊的指針都是空的，這樣我們就初始化了所有空的邊，那麼這個對應的是一個一重循環，而不是二重循環，

這樣就完成了圖的初始化，接下來我們看怎麼向LGraph裡面插入一條邊呢？插入邊的過程就是把一個頂點插到一個鏈表裡面去的過程，那麼我們來看一個圖，更好理解一點，現在如果我們插入的一條邊是從V1到V2的，也就是說我們要對V2建立一個邊的結點，然後把這個結點插到V1所在的鏈表裡面，插到鏈表的哪個位置呢？可以插在頭裡，也可以插在尾巴上，也可以插在任何的地方，但是從實現的角度講，顯然是插在鏈表的頭部是最簡單的

那麼對應的程序應該怎麼寫呢？首先我們應該申明一個邊的新結點叫NewNode,把V2的名字給進去，把它的權重存進去，

接下來就是我們要把新建的結點，插到G[V1]鏈表的頭部，也就是把V2插入V1的表頭，要怎麼做呢？就是V2的next指針要指向第一條邊，第一條邊是什麼邊呢？也就是G[V1]它的FirstEdge所指向的結點，

然後把G[V1]的FirstEdge換個方向，讓它指向V2,在程序實現的時候就是這麼兩句話

這個NewNode指的是V2了，這個新的結點它的Next指向G[V1]的第一條邊，G[V1]的第一條邊指向新的結點，就完成了這麼一個插入，如果是無向圖的話呢，除了要把V1,V2插進去以外，還需要插入V2,V1,那怎麼做呢？直接把上面的一段代碼copy下來，然後把V2,V1換一個位置，就完成了這條邊的插入

那麼在實現了前面兩步之後，接下來我們要完整的建立一個LGraph,那麼我們仍然仿照MGraph的情況，還是把函數名起名為BulidGraph,它返回的是一個鄰接表的LGraph的類型，回想一下MGraph的BuildGraph在裡面做的事情，在這裡面還會有區別嗎？但是如果你用最簡化的代碼，它會有區別嗎？自己好好的去思考一下

推薦閱讀：