Breadth First Search Graph
一、简介
广度优先遍历类似于树的按层次遍历过程。
假设从图中某顶点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:
四、结论
由上程序可知，广度优先遍历图的过各实质上也是查找邻接点的过程。因此，广度优先遍历和深度优先遍历时间复杂度相同，两者不同之处仅仅在于对顶点的访问顺序不同。
