数据结构——图的遍历

接下来今天讲数据结构——图的遍历~

上个学期在上海泰瑞达的春季招聘中曾被考过这类问题。

前面有一题是多态和另外一个名词的解释，有点记不清了。

然后还有一道题考的是括号解析，这个很简单的，用栈就能直接处理。

然后后面就是连续的两个图的问题。

之前好像只是简单的看了看源代码，对于什么是深度优先遍历和广度优先遍历稍微有点认识吧。

结果自然是可想而知，比较惨的。

当时我在卷子上是这么写的：“今天不会，明天就会了”。

当天回去就开始看图论，但是确实是搞的差不多了，不过现在嘛，呵呵~

首先，图的存储结构有简单的两种：1 邻接矩阵法 2临界表法

邻接矩阵我觉得是非常明了的一种图的表示方法，当然了，其缺点就是，在图的点数多而连接线少的时候，比较浪费资源。

我的邻接矩阵简单代码如下：

1 int main() 3 cout > nLineNumbers;23 // while(nLineNumbers --)24 // {25 // cout > nItem >> Point;27 // tmpGphLst.AddToListByOrder(nItem, Point);28 // }29 // tmpGphLst.BFS();30 // cout 这样从1点开始进行深度优先遍历，我们很容易就能得出其遍历结果：

1 2 3 5 4

这个结果相信不用我多说吧，具体可以看代码及其运行结果：

1 int Graph::DeepSearch(int Point) 2 { 3 p_nVisitList[Point] = 1; 4 cout 而邻接矩阵的广度优先遍历则是逐层访问，比较适合邻接表来做。

邻接矩阵的广度优先遍历方法如下：

1 void Graph::BFS() 3 p_nVisitList[4] = 1; 4 cout DL; 6 DL.push(4); 7 while(!DL.empty()) 9 int val = DL.front();10 DL.pop();11 for(int i = 0;i 看下这个类的代码：

1 class ListNode 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)14 class GraphList16 public:17 GraphList();18 ~GraphList();19 void AddToListByOrder(int nitem, int Point);20 void BFS(int n = 0);//这个广度优先遍历的代码太好写了21 private:22 int visit[5];23 ListNode * Next[5];24 };

上面的代码中包含了两个类，一个是邻接表的节点类，另外一个是邻接表本身。

代码还是很简单的，而且因为邻接表的特性，使得分层遍历十分方便，看主函数代码结构：

1 GraphList tmpGphLst; 2 int nLineNumbers = 0; 3 int nItem, Point; 4 cout > nLineNumbers; 6 while(nLineNumbers --) 8 cout > nItem >> Point;10 tmpGphLst.AddToListByOrder(nItem, Point);12 tmpGphLst.BFS();13 cout 2 #include 4 using namespace std; 6 class Graph 8 private: 9 //访问控制 10 int p_nVisitList[5]; 11 int (* pBlock)[5]; 13 public: 14 Graph(int (*pParam)[5]); 15 ~Graph(); 16 //深度优先遍历 17 int DeepSearch(int Point = 0); 18 void BFS(); 19 void ResetVisit(); 20 }; 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);//这个广度优先遍历的代码太好写了 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 = 0 && Point val = Point; 54 pnewnode->next = Next[nitem]; 55 Next[nitem] = pnewnode; 56 } 57 } 59 void GraphList::BFS(int n) 60 { 61 for(int i = 0;i val]) 72 { 73 cout val val] = 1; 75 } 76 pLNTmp = pLNTmp -> next; 77 } 78 } 79 } 81 GraphList::GraphList() 82 { 83 for(int i = 0;i next; 98 delete Next[i]; 99 Next[i] = ptmpLN;100 }101 }102 }104 void Graph::ResetVisit()105 {106 for(int i = 0;i DL;143 DL.push(4);144 while(!DL.empty())145 {146 int val = DL.front();147 DL.pop();148 for(int i = 0;i > nLineNumbers;182 while(nLineNumbers --)183 {184 cout > nItem >> Point;186 tmpGphLst.AddToListByOrder(nItem, Point);187 }188 tmpGphLst.BFS();189 cout 数据结构,—,图,的,遍历,接下来,今天,讲,