接下來今天講數(shù)據(jù)結構——圖的遍歷~
上個學期在上海泰瑞達的春季招聘中曾被考過這類問題。前面有一題是多態(tài)和另外一個名詞的解釋，有點記不清了。然后還有一道題考的是括號解析，這個很簡單的，用棧就能直接處理。然后后面就是連續(xù)的兩個圖的問題。之前好像只是簡單的看了看源代碼，對于什么是深度優(yōu)先遍歷和廣度優(yōu)先遍歷稍微有點認識吧。結果自然是可想而知，比較慘的。當時我在卷子上是這么寫的：“今天不會，明天就會了”。當天回去就開始看圖論，但是確實是搞的差不多了，不過現(xiàn)在嘛，呵呵~
首先，圖的存儲結構有簡單的兩種：1 鄰接矩陣法 2臨界表法
鄰接矩陣我覺得是非常明了的一種圖的表示方法，當然了，其缺點就是，在圖的點數(shù)多而連接線少的時候，比較浪費資源。
我的鄰接矩陣簡單代碼如下：
1 int main()
2 {
3 cout << "Hello world!" << endl;
4 int Block[5][5] = \
5 {
6 0, 1, 1, 1, 0, \
7 1, 0, 1, 1, 0, \
8 1, 1, 0, 0, 1, \
9 1, 1, 0, 0, 1, \
10 0, 0, 1, 1, 0 \
11 };
12 Graph tmpGph(Block);
13 tmpGph.DeepSearch();
14 tmpGph.ResetVisit();
15 cout << endl;
16 tmpGph.BFS();
17 //New Job!!!
18 // GraphList tmpGphLst;
19 // int nLineNumbers = 0;
20 // int nItem, Point;
21 // cout << "How Many Lines Inside?" << endl;
22 // cin >> nLineNumbers;
23 // while(nLineNumbers --)
24 // {
25 // cout << "Input Line Point A, B" << endl;
26 // cin >> nItem >> Point;
27 // tmpGphLst.AddToListByOrder(nItem, Point);
28 // }
29 // tmpGphLst.BFS();
30 // cout << endl;
31 return 0;
32 }因為遍歷的是無向圖，所以我做的是一個對稱鄰接矩陣，其對應的圖是這樣的：（其中的箭頭你就當他不存在吧，無向圖哦）
我發(fā)現(xiàn)我在寫博文題同時，還能提高我的visio繪圖能力~不過現(xiàn)在實在不怎么樣。一點點練吧。
這樣從1點開始進行深度優(yōu)先遍歷，我們很容易就能得出其遍歷結果：
1 2 3 5 4
這個結果相信不用我多說吧，具體可以看代碼及其運行結果：
1 int Graph::DeepSearch(int Point)
2 {3 p_nVisitList[Point] = 1;
4 cout << Point << ends;
5
6 for(int i = 0;i < 5;++ i)
7 {8 if(1 == pBlock[Point][i] && 0 == p_nVisitList[i])
9 {10 DeepSearch(i);
11 }
12 }
13 }
就是這樣一段簡單的代碼~其中在函數(shù)生命中Point的參數(shù)默認為0，其運行結果如下：
其中逐個加1，就對應上了1 2 3 5 4了。
就這么簡單。深度優(yōu)先遍歷使用的方法是針對當前的這個點的鄰接點進行查找，只要找到了一個未訪問的節(jié)點，就對這個節(jié)點采用同樣的方式進行遍歷。所以深度優(yōu)先遍歷使用遞歸是很好的方式，我的那個代碼只有13行~
而鄰接矩陣的廣度優(yōu)先遍歷則是逐層訪問，比較適合鄰接表來做。鄰接矩陣的廣度優(yōu)先遍歷方法如下：
1 void Graph::BFS()
2 {
3 p_nVisitList[4] = 1;
4 cout << 4 << ends;
5 queue<int> DL;
6 DL.push(4);
7 while(!DL.empty())
8 {
9 int val = DL.front();
10 DL.pop();
11 for(int i = 0;i < 5;++ i)
12 {
13 if(1 == pBlock[val][i] && p_nVisitList[i] == 0)
14 {
15 cout << i << ends;
16 p_nVisitList[i] = 1;
17 DL.push(i);
18 }
19 }
20 }
21 }運行結果：
還是一樣的圖，運行結果就是第二行的結果。你可以自己算一下對不對（BFS遍歷的起始點為4，注意下）。
鄰接表的廣度優(yōu)先遍歷
我覺得，因為鄰接表的較為特殊的存儲形式，使得其較為適合以廣度優(yōu)先的方式進行遍歷。但是需要注意的是，鄰接矩陣和鄰接表這兩種圖的存儲形式，都能夠使用深度優(yōu)先遍歷和廣度優(yōu)先遍歷的。
廣度優(yōu)先遍歷的思想是逐層訪問，每當當前節(jié)點的全部相鄰節(jié)點都被訪問完成之后，再訪問下一層節(jié)點。
我在用鄰接表表示的圖的類中，專門制作了一個方法用于添加點和點關系的函數(shù)。通過這個函數(shù)，來實現(xiàn)圖的創(chuàng)建。
看下這個類的代碼：
1 class ListNode
2 {
3 public:
4 int val;
5 int weight;
6 ListNode * next;
7 public:
8 ListNode();
9 };
10 ListNode::ListNode():val(0), weight(0), next(NULL)
11 {
12 ;
13 }
14 class GraphList
15 {
16 public:
17 GraphList();
18 ~GraphList();
19 void AddToListByOrder(int nitem, int Point);
20 void BFS(int n = 0);//這個廣度優(yōu)先遍歷的代碼太好寫了
21 private:
22 int visit[5];
23 ListNode * Next[5];
24 };上面的代碼中包含了兩個類，一個是鄰接表的節(jié)點類，另外一個是鄰接表本身。代碼還是很簡單的，而且因為鄰接表的特性，使得分層遍歷十分方便，看主函數(shù)代碼結構：
1 GraphList tmpGphLst;
2 int nLineNumbers = 0;
3 int nItem, Point;
4 cout << "How Many Lines Inside?" << endl;
5 cin >> nLineNumbers;
6 while(nLineNumbers --)
7 {
8 cout << "Input Line Point A, B" << endl;
9 cin >> nItem >> Point;
10 tmpGphLst.AddToListByOrder(nItem, Point);
11 }
12 tmpGphLst.BFS();
13 cout << endl;在看演示效果：
因為鏈表采用的是前插法，所以你會看到第二層的遍歷結果是3 2 1，反過來的。
很容易發(fā)現(xiàn)，在使用鄰接表來表示的時候進行廣度優(yōu)先遍歷很方便。
圖論，我就寫這些啦~
最后附上本次的全部代碼：
1 #include <iostream>
2 #include <queue>
3
4 using namespace std;
5
6 class Graph
7 {
8 private:
9 //訪問控制
10 int p_nVisitList[5];
11 int (* pBlock)[5];
12
13 public:
14 Graph(int (*pParam)[5]);
15 ~Graph();
16 //深度優(yōu)先遍歷
17 int DeepSearch(int Point = 0);
18 void BFS();
19 void ResetVisit();
20 };
21
22 class ListNode
23 {
24 public:
25 int val;
26 int weight;
27 ListNode * next;
28 public:
29 ListNode();
30 };
31 ListNode::ListNode():val(0), weight(0), next(NULL)
32 {
33 ;
34 }
35 class GraphList
36 {
37 public:
38 GraphList();
39 ~GraphList();
40 void AddToListByOrder(int nitem, int Point);
41 void BFS(int n = 0);//這個廣度優(yōu)先遍歷的代碼太好寫了
42 private:
43 int visit[5];
44 ListNode * Next[5];
45 };
46 void GraphList::AddToListByOrder(int nitem, int Point)//前插法，代碼好寫
47 {
48 if(nitem >= 0 && nitem < 5 && Point >= 0 && Point < 5)
49 {
50 ListNode * pnewnode = new ListNode;
51 if(pnewnode == NULL)
52 return;
53 pnewnode->val = Point;
54 pnewnode->next = Next[nitem];
55 Next[nitem] = pnewnode;
56 }
57 }
58
59 void GraphList::BFS(int n)
60 {
61 for(int i = 0;i < 5;++ i)
62 {
63 if(visit[i] == 0)
64 {
65 cout << i << ends;
66 visit[i] = 1;
67 }
68 ListNode * pLNTmp = Next[i];
69 while(pLNTmp != NULL)
70 {
71 if(0 == visit[pLNTmp->val])
72 {
73 cout << pLNTmp->val << ends;
74 visit[pLNTmp->val] = 1;
75 }
76 pLNTmp = pLNTmp -> next;
77 }
78 }
79 }
80
81 GraphList::GraphList()
82 {
83 for(int i = 0;i < 5;++ i)
84 {
85 visit[i] = 0;
86 Next[i] = NULL;
87 }
88 }
89
90 GraphList::~GraphList()
91 {
92 for(int i = 0;i < 5;++ i)
93 {
94 ListNode * ptmpLN;
95 while(Next[i] != NULL)
96 {
97 ptmpLN = Next[i]->next;
98 delete Next[i];
99 Next[i] = ptmpLN;
100 }
101 }
102 }
103
104 void Graph::ResetVisit()
105 {
106 for(int i = 0;i < 5;++ i)
107 {
108 p_nVisitList[i] = 0;
109 }
110 }
111 Graph::Graph(int (*pParam)[5])
112 {
113 for(int i = 0;i < 5;++ i)
114 p_nVisitList[i] = 0;
115 pBlock = pParam;
116 }
117
118 Graph::~Graph()
119 {
120 ;//nothing!
121 }
122
123 int Graph::DeepSearch(int Point)
124 {
125 p_nVisitList[Point] = 1;
126 cout << Point << ends;
127
128 for(int i = 0;i < 5;++ i)
129 {
130 if(1 == pBlock[Point][i] && 0 == p_nVisitList[i])
131 {
132 DeepSearch(i);
133 }
134 }
135 return 0;
136 }
137
138 void Graph::BFS()
139 {
140 p_nVisitList[4] = 1;
141 cout << 4 << ends;
142 queue<int> DL;
143 DL.push(4);
144 while(!DL.empty())
145 {
146 int val = DL.front();
147 DL.pop();
148 for(int i = 0;i < 5;++ i)
149 {
150 if(1 == pBlock[val][i] && p_nVisitList[i] == 0)
151 {
152 cout << i << ends;
153 p_nVisitList[i] = 1;
154 DL.push(i);
155 }
156 }
157 }
158 }
159
160 int main()
161 {
162 cout << "Hello world!" << endl;
163 int Block[5][5] = \
164 {
165 0, 1, 1, 1, 0, \
166 1, 0, 1, 1, 0, \
167 1, 1, 0, 0, 1, \
168 1, 1, 0, 0, 1, \
169 0, 0, 1, 1, 0 \
170 };
171 Graph tmpGph(Block);
172 tmpGph.DeepSearch();
173 tmpGph.ResetVisit();
174 cout << endl;
175 tmpGph.BFS();
176 //New Job!!!
177 GraphList tmpGphLst;
178 int nLineNumbers = 0;
179 int nItem, Point;
180 cout << "How Many Lines Inside?" << endl;
181 cin >> nLineNumbers;
182 while(nLineNumbers --)
183 {
184 cout << "Input Line Point A, B" << endl;
185 cin >> nItem >> Point;
186 tmpGphLst.AddToListByOrder(nItem, Point);
187 }
188 tmpGphLst.BFS();
189 cout << endl;
190 return 0;
191 }
