VC++2012程式設計演練資料結構《29》圖

圖是由結點的有窮集合V和邊的集合E組成。其中，為了與樹形結構加以差別，在圖結構中常常将結點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關系。

　　在上面兩個圖結構中，一個是有向圖，即每條邊都有方向，另一個是無向圖，即每條邊都沒有方向。

　　在有向圖中，通常将邊稱作弧，含箭頭的一端稱為弧頭，另一端稱為弧尾，記作<vi,vj>，它表示從頂點vi到頂點vj有一條邊。

　　若有向圖中有n個頂點，則最多有n(n-1)條弧，我們又将具有n(n-1)條弧的有向圖稱作有向完全圖。以頂點v為弧尾的弧的數目稱作頂點v的出度，以頂點v為弧頭的弧的數目稱作頂點v的入度。在無向圖中，邊記作(vi,vj)，它蘊涵着存在< vi,vj>和<vj,vi>兩條弧。若無向圖中有n個頂點，則最多有n(n-1)/2條弧，我們又将具有n(n-1)/2條弧的無向圖稱作無向完全圖。與頂點v相關的邊的條數稱作頂點v的度。

　　路徑長度是指路徑上邊或弧的數目。

　　若第一個頂點和最後一個頂點相同，則這條路徑是一條回路。

　　若路徑中頂點沒有重複出現，則稱這條路徑為簡單路徑。

　　在無向圖中，如果從頂點vi到頂點vj有路徑，則稱vi和vj連通。如果圖中任意兩個頂點之間都連通，則稱該圖為連通圖，否則，将其中的極大連通子圖稱為連通分量。

　　在有向圖中，如果對于每一對頂點vi和vj，從vi到vj和從vj到vi都有路徑，則稱該圖為強連通圖；否則，将其中的極大連通子圖稱為強連通分量。

圖的基本操作

　　（1）建立一個圖結構 CreateGraph(G)

　　（2）檢索給定頂點 LocateVex(G,elem)

　　（3）擷取圖中某個頂點 GetVex(G,v)

　　（4）為圖中頂點指派 PutVex(G,v,value)

　　（5）傳回第一個鄰接點 FirstAdjVex(G,v)

　　（6）傳回下一個鄰接點 NextAdjVex(G,v,w)

　　（7）插入一個頂點 InsertVex(G,v)

　　（8）删除一個頂點 DeleteVex(G,v)

　　（9）插入一條邊 InsertEdge(G,v,w)

　　（10）删除一條邊 DeleteEdge(G,v,w)

　　（11）周遊圖 Traverse(G,v)

d打開ＩＤＥ

我們來建立一個工程

類的聲名如下

類的實作如下

代碼調用如下

效果如下

代碼下載下傳

http://download.csdn.net/detail/yincheng01/4789890