posts - 398, comments - 568, trackbacks - 0, articles - 0

Breadth First Search Graph

eryar@163.com

一、简介

广度优先遍历类似于树的按层次遍历过程。

假设从图中某顶点V出发,在访问了V之后依次访问V的各个未曾访问过的邻接顶点,然后分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直到图中所有已被访问的顶点的邻接点都被访问到。到此时图中尚有未被访问的顶点,则另选图中一个未曾访问的顶点作为始点,重复上述过程,直到图中所有顶点都被访问到为止。换言之,广度优先遍历图的过程是以V为起始点,由近至远,依次访问和V有路径相通且路径长度为1,2,……的顶点。

为了顺序访问路径长度为1,2,……的顶点,需要利用队列的数据特性:先进先出来存储已被访问的路径长度为1,2,……的顶点。

二、C++实现

  1: //------------------------------------------------------------------------------
  2: //	Copyright (c) 2012 eryar All Rights Reserved.
  3: //
  4: //		File    : Main.cpp
  5: //		Author  : eryar@163.com
  6: //		Date    : 2012-8-25 17:11
  7: //		Version : 0.1v
  8: //
  9: //	Description : Use Adjacency List data structure to store Digraph.
 10: //
 11: //==============================================================================
 12: 
 13: #include <vector>
 14: #include <queue>
 15: #include <string>
 16: #include <iostream>
 17: using namespace std;
 18: 
 19: struct SVertexNode
 20: {
 21:     bool          bIsVisited;
 22:     string        data;
 23:     vector<int> vecLoc;
 24: };
 25: 
 26: typedef struct SEdge
 27: {
 28:     int iInitialNode;
 29: 
 30:     int iTerminalNode;
 31: 
 32: }Edge;
 33: 
 34: typedef struct SGraph
 35: {
 36:     int iVertexNum;
 37:     int iEdgeNum;
 38:     vector<SVertexNode> vecVertex;
 39: }Graph;
 40: 
 41: ///////////////////////////////////////////////////////////////////////////////
 42: // Functions of Graph
 43: void    Initialize(Graph& g, int v);
 44: Edge    MakeEdge(int v, int w);
 45: void    InsertEdge(Graph& g, const Edge& e);
 46: void    ShowGraph(const Graph& g);
 47: void    ClearVisitFlag(Graph& g);
 48: 
 49: // Use Depth First Search method to Traverse the graph.
 50: void    DepthFirstSearch(Graph& g);
 51: void    DepthFirstSearch(Graph& g, int v);
 52: 
 53: // Use Breadth First Search method to Traverse the graph.
 54: void    BreadthFirstSearch(Graph& g);
 55: 
 56: ///////////////////////////////////////////////////////////////////////////////
 57: // Main function.
 58: 
 59: int main(int agrc, char* argv[])
 60: {
 61:     Graph   aGraph;
 62: 
 63:     // Initialize the graph.
 64:     Initialize(aGraph, 4);
 65: 
 66:     // Insert some edges to make graph.
 67:     InsertEdge(aGraph, MakeEdge(0, 1));
 68:     InsertEdge(aGraph, MakeEdge(0, 2));
 69:     InsertEdge(aGraph, MakeEdge(2, 3));
 70:     InsertEdge(aGraph, MakeEdge(3, 0));
 71: 
 72:     // Show the graph.
 73:     ShowGraph(aGraph);
 74: 
 75:     // DFS traverse the graph.
 76:     DepthFirstSearch(aGraph);
 77: 
 78:     // BFS traverse the graph.
 79:     BreadthFirstSearch(aGraph);
 80: 
 81:     return 0;
 82: }
 83: 
 84: ///////////////////////////////////////////////////////////////////////////////
 85: 
 86: /**
 87: * brief	Initialize the graph.
 88: *
 89: *       v: vertex number of the graph.
 90: */
 91: void Initialize( Graph& g, int v )
 92: {
 93:     char    szData[6];
 94:     SVertexNode node;
 95: 
 96:     g.iVertexNum    = v;
 97:     g.iEdgeNum      = 0;
 98: 
 99:     for (int i = 0; i < v; i++)
100:     {
101:         sprintf(szData, "V%d", i+1);
102:         node.data   = szData;
103:         node.bIsVisited = false;
104:         g.vecVertex.push_back(node);
105:     }
106: }
107: 
108: /**
109: * brief	Make an edge by initial node and terminal node.
110: */
111: Edge MakeEdge( int v, int w )
112: {
113:     Edge    e;
114: 
115:     e.iInitialNode  = v;
116:     e.iTerminalNode = w;
117: 
118:     return e;
119: }
120: 
121: /**
122: * brief	Insert an edge to the graph.
123: */
124: void InsertEdge( Graph& g, const Edge& e )
125: {
126:     g.vecVertex.at(e.iInitialNode).vecLoc.push_back(e.iTerminalNode);
127: 
128:     // If the graph is Undigraph, need do something here...
129:     //g.vecVertex.at(e.iTerminalNode).vecLoc.push_back(e.iInitialNode);
130: 
131:     g.iEdgeNum++;
132: }
133: 
134: /**
135: * brief	Show the graph.
136: */
137: void ShowGraph( const Graph& g )
138: {
139:     cout<<"Show the graph: "<<endl;
140: 
141:     for (int i = 0; i < g.iVertexNum; i++)
142:     {
143:         cout<<"Node "<<i<<"("<<g.vecVertex.at(i).data<<")";
144: 
145:         for (int j = 0; j < g.vecVertex.at(i).vecLoc.size(); j++)
146:         {
147:             cout<<"->"<<g.vecVertex.at(i).vecLoc.at(j);
148:         }
149: 
150:         cout<<endl;
151:     }
152: }
153: 
154: void ClearVisitFlag( Graph& g )
155: {
156:     for (int i = 0; i < g.iVertexNum; i++)
157:     {
158:         g.vecVertex.at(i).bIsVisited    = false;
159:     }
160: }
161: 
162: void DepthFirstSearch( Graph& g )
163: {
164:     cout<<"Depth First Search the graph:"<<endl;
165: 
166:     for (int i = 0; i < g.iVertexNum; i++)
167:     {
168:         if (!(g.vecVertex.at(i).bIsVisited))
169:         {
170:             DepthFirstSearch(g, i);
171:         }
172:     }
173: }
174: 
175: void DepthFirstSearch(Graph& g, int v)
176: {
177:     int     iAdjacent   = 0;
178:     SVertexNode node    = g.vecVertex.at(v);
179: 
180:     // Visit the vertex and mark it.
181:     cout<<g.vecVertex.at(v).data<<endl;
182:     g.vecVertex.at(v).bIsVisited = true;
183: 
184:     // Visit the adjacent vertex.
185:     for (int i = 0; i < node.vecLoc.size(); i++)
186:     {
187:         iAdjacent   = node.vecLoc.at(i);
188: 
189:         if (!(g.vecVertex.at(iAdjacent).bIsVisited))
190:         {
191:             DepthFirstSearch(g, iAdjacent);
192:         }
193:     }
194: 
195: }
196: 
197: void BreadthFirstSearch( Graph& g )
198: {
199:     SVertexNode         node;
200:     queue<SVertexNode> visitedNodes;
201: 
202:     cout<<"Breadth First Search the graph:"<<endl;
203: 
204:     ClearVisitFlag(g);
205: 
206:     for (int i = 0; i < g.iVertexNum; i++)
207:     {
208:         node    = g.vecVertex.at(i);
209: 
210:         if (!node.bIsVisited)
211:         {
212:             // Visit it.
213:             cout<<node.data<<endl;
214: 
215:             // Set visite flag.
216:             g.vecVertex.at(i).bIsVisited = true;
217: 
218:             // Enqueue.
219:             visitedNodes.push(node);
220: 
221:             while (!visitedNodes.empty())
222:             {
223:                 node    = visitedNodes.front();
224: 
225:                 visitedNodes.pop();
226: 
227:                 for (int j = 0; j < node.vecLoc.size(); j++)
228:                 {
229:                     if (!g.vecVertex.at(j).bIsVisited)
230:                     {
231:                         cout<<g.vecVertex.at(j).data<<endl;
232: 
233:                         g.vecVertex.at(j).bIsVisited    = true;
234: 
235:                         visitedNodes.push(g.vecVertex.at(j));
236:                     }
237:                 }
238:             }
239:         }
240:     }
241: }
242: 

 

三、程序输出

程序的数据来源为原先用邻接表生成图的程序,可以根据需要自定义数据来验证程序的正确性。

  1: Show the graph:
  2: Node 0(V1)->1->2
  3: Node 1(V2)
  4: Node 2(V3)->3
  5: Node 3(V4)->0
  6: Depth First Search the graph:
  7: V1
  8: V2
  9: V3
 10: V4
 11: Breadth First Search the graph:
 12: V1
 13: V2
 14: V3
 15: V4
 16: Press any key to continue
 17: 

四、结论

由上程序可知,广度优先遍历图的过各实质上也是查找邻接点的过程。因此,广度优先遍历和深度优先遍历时间复杂度相同,两者不同之处仅仅在于对顶点的访问顺序不同。


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理