数据结构——图的遍历

数据结构与算法教程ios版v1.2.1 官方版

• 类型：ios办公学习大小：12.2M语言：中文 评分：10.0
• 标签：

立即下载

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

上个学期在上海泰瑞达的春季招聘中曾被考过这类问题。前面有一题是多态和另外一个名词的解释，有点记不清了。然后还有一道题考的是括号解析，这个很简单的，用栈就能直接处理。然后后面就是连续的两个图的问题。之前好像只是简单的看了看源代码，对于什么是深度优先遍历和广度优先遍历稍微有点认识吧。结果自然是可想而知，比较惨的。当时我在卷子上是这么写的：“今天不会，明天就会了”。当天回去就开始看图论，但是确实是搞的差不多了，不过现在嘛，呵呵~

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

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

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

 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 }

因为遍历的是无向图，所以我做的是一个对称邻接矩阵，其对应的图是这样的：（其中的箭头你就当他不存在吧，无向图哦）

　　我发现我在写博文题同时，还能提高我的visio绘图能力~不过现在实在不怎么样。一点点练吧。

　　这样从1点开始进行深度优先遍历，我们很容易就能得出其遍历结果：

　　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 }

就是这样一段简单的代码~其中在函数生命中Point的参数默认为0，其运行结果如下：

其中逐个加1，就对应上了1 2 3 5 4了。

就这么简单。深度优先遍历使用的方法是针对当前的这个点的邻接点进行查找，只要找到了一个未访问的节点，就对这个节点采用同样的方式进行遍历。所以深度优先遍历使用递归是很好的方式，我的那个代码只有13行~

而邻接矩阵的广度优先遍历则是逐层访问，比较适合邻接表来做。邻接矩阵的广度优先遍历方法如下：

 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，注意下）。

邻接表的广度优先遍历

我觉得，因为邻接表的较为特殊的存储形式，使得其较为适合以广度优先的方式进行遍历。但是需要注意的是，邻接矩阵和邻接表这两种图的存储形式，都能够使用深度优先遍历和广度优先遍历的。

广度优先遍历的思想是逐层访问，每当当前节点的全部相邻节点都被访问完成之后，再访问下一层节点。

我在用邻接表表示的图的类中，专门制作了一个方法用于添加点和点关系的函数。通过这个函数，来实现图的创建。

看下这个类的代码：

 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);//这个广度优先遍历的代码太好写了
21     private:
22  int visit[5];
23  ListNode * Next[5];
24 };

上面的代码中包含了两个类，一个是邻接表的节点类，另外一个是邻接表本身。代码还是很简单的，而且因为邻接表的特性，使得分层遍历十分方便，看主函数代码结构：

 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，反过来的。

很容易发现，在使用邻接表来表示的时候进行广度优先遍历很方便。

图论，我就写这些啦~

最后附上本次的全部代码：

  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     //深度优先遍历
 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);//这个广度优先遍历的代码太好写了
 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 }