假設從圖中某頂點V出發(fā)，在訪問了V之后依次訪問V的各個未曾訪問過的鄰接頂點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”被訪問，直到圖中所有已被訪問的頂點的鄰接點都被訪問到。到此時圖中尚有未被訪問的頂點，則另選圖中一個未曾訪問的頂點作為始點，重復上述過程，直到圖中所有頂點都被訪問到為止。換言之，廣度優(yōu)先遍歷圖的過程是以V為起始點，由近至遠，依次訪問和V有路徑相通且路徑長度為1，2，……的頂點。
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:
由上程序可知，廣度優(yōu)先遍歷圖的過各實質上也是查找鄰接點的過程。因此，廣度優(yōu)先遍歷和深度優(yōu)先遍歷時間復雜度相同，兩者不同之處僅僅在于對頂點的訪問順序不同。