-?

圖的存儲結構主要有鄰接矩陣和鄰接表存儲兩種存儲方式

在遍歷方式上有廣度遍歷和深度遍歷

廣度遍歷就是按層次遍歷，可以借助隊列實現

深度遍歷可以理解為一種遞歸遍歷

在練習程序中選擇用鄰接表結構存儲圖，圖的結構如圖所示

如果鄰接矩陣結構存儲圖的話，當圖的節點較多，但邊數較時浪費了存儲空間。

鄰接表結構的話可以先用頭節點鏈表存儲所有的圖的節點，每一個頭節點又是以該頭節點為起始節點的邊的鏈表的起始點。

每個鏈接表的節點結構為

該節點在頭節點鏈表中的位置，和其下一節點。

我覺得做圖的相關存儲時的關鍵點：

?圖的頭節點鏈表的結構和邊鏈表的結構

頭節點中要包含該節點的值和邊鏈表的鏈表指針，在C#中用類的示例來表示

示例代碼為：

?

?

Code
??1?using?System;
??2?using?System.Collections.Generic;
??3?using?System.Text;
??4?
??5?namespace?LinkGraph
??6?{
??7?????///?<summary>
??8?????///?采用鄰接表方式存儲圖
??9?????///?</summary>
?10?????///?<typeparam?name="T">圖的節點的數據類型</typeparam>
?11??public?class?GraphLink<T>
?12?????{
?13??????????/*圖的節點*/
?14?
?15??????public?GraphLink()?
?16??????{
?17??????????NodeList?=?new?List<GraphLink<T>.HeadNode>();
?18??????????nodeCount?=?0;
?19??????????borderCount?=?0;
?20??????}
?21??????public?class?HeadNode
?22??????{
?23????????public??T?data;
?24????????public???bool?isVisited;
?25????????public???SubNode<HeadNode>?Next;
?26??????}
?27?
?28??????public?class?SubNode<vType>
?29??????{
?30??????????///?<summary>
?31??????????///?該子節點在節點鏈表中的位置
?32??????????///?</summary>
?33????????public???vType?adjex;//指向頭節點鏈表中的前一個節點
?34??????????///?<summary>
?35??????????///?以該節點為目的節點的邊的權值
?36??????????///?</summary>
?37????????public???T?weight;??//以該節點為目的節點的邊的權值
?38?????????///?<summary>
?39?????????///?子節點的下一個子節點
?40?????????///?</summary>
?41??
?42????????public???SubNode<vType>?next;
?43?
?44????????public?SubNode(vType?value)?
?45????????{
?46????????????adjex?=?value;
?47????????}??
?48??????}
?49??????///?<summary>
?50??????///?存放圖的所有節點的鏈表
?51??????///?</summary>
?52??????public?List<HeadNode>?NodeList;
?53??????///?<summary>
?54??????///?圖中節點數
?55??????///?</summary>
?56??????public?int?nodeCount;
?57??????///?<summary>
?58??????///?圖中邊的數目
?59??????///?</summary>
?60??????public?int?borderCount;
?61??????///?<summary>
?62??????///?在圖中增加一個節點
?63??????///?</summary>
?64??????///?<param?name="NewNodeValue">節點的值</param>
?65??????public?void?AddNode(T?NewNodeValue)?
?66??????{
?67??????????if?(NodeList?==?null)?NodeList?=?new?List<GraphLink<T>.HeadNode>();
?68??????????foreach?(HeadNode?h?in?NodeList)?
?69??????????{
?70??????????????/*
?71???????????????*?判斷圖中時有已存在的節點
?72???????????????*/
?73??????????????if?(h.data.Equals(NewNodeValue)?==?true)?
?74??????????????{
?75??????????????????Console.WriteLine("圖中已經存在該節點");
?76??????????????????return;
?77??????????????}
?78?
?79??????????}
?80??????????HeadNode?t?=?new?GraphLink<T>.HeadNode();
?81??????????t.data?=?NewNodeValue;
?82??????????t.isVisited?=?false;
?83??????????t.Next?=?null;
?84??????????/*
?85?????????????圖的節點鏈表加入該子節點
?86???????????*/
?87??????????NodeList.Add(t);
?88??????????nodeCount?=?NodeList.Count;
?89??????}
?90?
?91??????///?<summary>
?92??????///?在圖中添加一條邊
?93??????///?</summary>
?94??????///?<param?name="FromValue">起始節點的值</param>
?95??????///?<param?name="ToValue">目的節點的值</param>
?96??????///?<param?name="BorderWeight"></param>
?97??????public?void?AddBorder(T?FromValue,?T?ToValue,?T?BorderWeight)?
?98??????{
?99?
100??????????DirectAddBorder(FromValue,ToValue,BorderWeight);
101??????????DirectAddBorder(ToValue,?FromValue,?BorderWeight);????????
102??????????borderCount++;
103?????????
104??????}
105?
106??????void?DirectAddBorder(T?FromValue,?T?ToValue,?T?w)
107??????{
108??????????HeadNode?FromNode;
109??????????HeadNode?ToNode;
110??????????FromNode?=?Find(FromValue);
111??????????if?(FromNode?==?null)
112??????????{
113??????????????ErrorShow("圖中找不到起始節點");
114??????????????return;
115??????????}
116??????????ToNode?=?Find(ToValue);
117??????????if?(ToNode?==?null)
118??????????{
119??????????????ErrorShow("圖中找不到目的節點");
120??????????????return;
121??????????}
122?
123?
124?
125??????????SubNode<HeadNode>?t?=?new?GraphLink<T>.SubNode<GraphLink<T>.HeadNode>(ToNode);
126??????????t.weight?=?w;
127?
128??????????if?(FromNode.Next?==?null)???//頭節點沒有子節點的情況
129??????????{
130??????????????FromNode.Next?=?t;
131??????????}
132??????????else
133??????????{
134?
135??????????????SubNode<HeadNode>?p?=?FromNode.Next;
136??????????????SubNode<HeadNode>?pr?=?p;
137?
138??????????????while?(p?!=?null)
139??????????????{
140??????????????????/*
141????????????????????判斷時有已有存在的邊
142???????????????????*?如果有的話則提示并且返回
143???????????????????*/
144??????????????????if?(p.adjex.data.Equals(ToValue)?==?true)
145??????????????????{
146??????????????????????ErrorShow("這條邊已經存在");
147??????????????????????return;
148??????????????????}
149??????????????????pr?=?p;
150??????????????????p?=?p.next;
151?
152??????????????}
153??????????????pr.next?=?t;
154??????????}
155??????????
156?
157??????}
158??????///?<summary>
159??????///?遞歸方式?深度優先遍歷圖??
160??????///?</summary>
161??????///?<param?name="StartNodeValue">起始節點的值</param>
162??????public?void?DFSTraverse(T?StartNodeValue)?
163??????{
164??????????HeadNode?h?=?Find(StartNodeValue);
165??????????if?(h?==?null)?
166??????????{
167??????????????ErrorShow("圖中不存在該起始節點");
168??????????}
169??????????DFS(h);
170?
171??????}
172?
173??????void?DFS(HeadNode?n)?
174??????{
175??????????VistNode(n);
176?
177??????????if?(n.Next?!=?null)?
178??????????{
179??????????????/*
180????????????????訪問已訪問節點的子節點?
181???????????????*/
182??????????????SubNode<HeadNode>?p?=?n.Next;
183??????????
184??????????????while?(p?!=?null)?
185??????????????{
186??????????????????/*如果已訪問節點n的子節點中有未訪問的節點
187???????????????????*?則遞歸訪問該節點
188???????????????????*/
189??????????????????if?(p.adjex.isVisited?==?false)?
190??????????????????{
191??????????????????????DFS(p.adjex);?//遞歸遍歷未訪問過的頭節點
192??????????????????}??
193?
194??????????????????p?=?p.next;
195??????????????}
196??????????}
197??????}
198??????///?<summary>
199??????///?廣度優先遍歷圖
200??????///?</summary>
201??????///?<param?name="StartNodeValue">起始節點的值</param>
202??????public?void?BFSTraverse(T?StartNodeValue)?
203??????{
204??????????HeadNode?h?=?Find(StartNodeValue);
205??????????if?(h?==?null)
206??????????{
207??????????????ErrorShow("圖中不存在該起始節點");
208??????????}
209??????????BFS(h);
210??????}
211?
212??????void?BFS(HeadNode?n)?
213??????{
214??????????/*借助先入先出的隊列來按層次訪問圖*/
215??????????Queue<HeadNode>?NodeQueue?=?new?Queue<GraphLink<T>.HeadNode>();
216?
217??????????NodeQueue.Enqueue(n);
218??????????while?(NodeQueue.Count>0)?
219??????????{
220??????????????HeadNode?h=?NodeQueue.Dequeue();
221??????????????/*如果該節點還未被訪問則訪問該節點*/
222??????????????if?(h.isVisited?==?false)
223??????????????{
224??????????????????VistNode(h);
225??????????????}
226?
227??????????????if?(h.Next?!=?null)?
228??????????????{
229??????????????????SubNode<HeadNode>?p?=?h.Next;
230??????????????????while?(p?!=?null)?
231??????????????????{
232??????????????????????/*如果該節點還未被訪問則訪問該節點*/
233??????????????????????if?(p.adjex.isVisited?==?false)
234??????????????????????{
235??????????????????????????VistNode(p.adjex);
236??????????????????????????NodeQueue.Enqueue(p.adjex);
237??????????????????????}
238??????????????????????p?=?p.next;
239?
240??????????????????}
241??????????????}
242??????????}
243??????}
244?
245??????void?VistNode(HeadNode?n)?
246??????{
247??????????Console.WriteLine(n.data.ToString());
248??????????/*設置已訪問標志*/
249??????????n.isVisited?=?true;??
250??????????
251??????}
252?
253??????void?ErrorShow(string?txt)?
254??????{
255??????????Console.WriteLine(txt);
256??????}
257??????///?<summary>
258??????///?在節點鏈表中查找節點
259??????///?</summary>
260??????///?<param?name="keyValue">待查找節點的數據域的值</param>
261??????///?<returns></returns>
262???????HeadNode?Find(T?keyValue)?
263??????{
264??????????foreach?(HeadNode?t?in?NodeList)?
265??????????{
266??????????
267????????????if(t.data.Equals(keyValue)==true)
268????????????{
269??????????????return?t;
270????????????}
271??????????}
272??????????return?null;
273??????}
274??????///?<summary>
275??????///?顯示所有節點的值
276??????///?</summary>
277???????public?void?ShowAllNodes()?
278???????{
279???????????foreach?(HeadNode?t?in?NodeList)?
280???????????{
281???????????????Console.WriteLine(t.data);
282???????????}
283???????}
284?
285?
286?????}
287?
288??
289?}
290?

?

?

?

?

轉載于:https://www.cnblogs.com/smile2you/archive/2009/03/06/1404932.html

總結

以上是生活随笔為你收集整理的图的存储与遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。