深度优先遍历用邻接表表示的图
DFS the Adjacency List Graph
eryar@163.com
一、简介
创建了图之后，我们希望从图中某个顶点出发访遍图中其余顶点，且使每个顶点仅被访问一次。这一过程就是图的遍历（Traversing Graph）。图的遍历算法是求解图的连通性问题、拓朴排序和求解关键路径等算法的基础。
深度优先搜索（Depth First Search）是一种递归的遍历方法。其过程为从图中任意一顶点出发，访问与其相连接的未被访问的顶点。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。
二、实现代码
依然使用邻接表来表示图的存储结构，深度优先遍历程序如下代码所示：
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 <string>
15: #include <iostream>
16: using namespace std;
17:
18: struct SVertexNode
19: {
20: bool bIsVisited;
21: string data;
22: vector<int> vecLoc;
23: };
24:
25: typedef struct SEdge
26: {
27: int iInitialNode;
28:
29: int iTerminalNode;
30:
31: }Edge;
32:
33: typedef struct SGraph
34: {
35: int iVertexNum;
36: int iEdgeNum;
37: vector<SVertexNode> vecVertex;
38: }Graph;
39:
40: ///////////////////////////////////////////////////////////////////////////////
41: // Functions of Graph
42: void Initialize(Graph& g, int v);
43: Edge MakeEdge(int v, int w);
44: void InsertEdge(Graph& g, const Edge& e);
45: void ShowGraph(const Graph& g);
46:
47: // Use Depth First Search method to Traverse the graph.
48: void DepthFirstSearch(Graph& g);
49: void DepthFirstSearch(Graph& g, int v);
50:
51: ///////////////////////////////////////////////////////////////////////////////
52: // Main function.
53:
54: int main(int agrc, char* argv[])
55: {
56: Graph aGraph;
57:
58: // Initialize the graph.
59: Initialize(aGraph, 4);
60:
61: // Insert some edges to make graph.
62: InsertEdge(aGraph, MakeEdge(0, 1));
63: InsertEdge(aGraph, MakeEdge(0, 2));
64: InsertEdge(aGraph, MakeEdge(2, 3));
65: InsertEdge(aGraph, MakeEdge(3, 0));
66:
67: // Show the graph.
68: ShowGraph(aGraph);
69:
70: // DFS traverse the graph.
71: DepthFirstSearch(aGraph);
72:
73: return 0;
74: }
75:
76: ///////////////////////////////////////////////////////////////////////////////
77:
78: /**
79: * brief Initialize the graph.
80: *
81: * v: vertex number of the graph.
82: */
83: void Initialize( Graph& g, int v )
84: {
85: char szData[6];
86: SVertexNode node;
87:
88: g.iVertexNum = v;
89: g.iEdgeNum = 0;
90:
91: for (int i = 0; i < v; i++)
92: {
93: sprintf(szData, "V%d", i+1);
94: node.data = szData;
95: node.bIsVisited = false;
96: g.vecVertex.push_back(node);
97: }
98: }
99:
100: /**
101: * brief Make an edge by initial node and terminal node.
102: */
103: Edge MakeEdge( int v, int w )
104: {
105: Edge e;
106:
107: e.iInitialNode = v;
108: e.iTerminalNode = w;
109:
110: return e;
111: }
112:
113: /**
114: * brief Insert an edge to the graph.
115: */
116: void InsertEdge( Graph& g, const Edge& e )
117: {
118: g.vecVertex.at(e.iInitialNode).vecLoc.push_back(e.iTerminalNode);
119:
120: // If the graph is Undigraph, need do something here...
121: //g.vecVertex.at(e.iTerminalNode).vecLoc.push_back(e.iInitialNode);
122:
123: g.iEdgeNum++;
124: }
125:
126: /**
127: * brief Show the graph.
128: */
129: void ShowGraph( const Graph& g )
130: {
131: cout<<"Show the graph: "<<endl;
132:
133: for (int i = 0; i < g.iVertexNum; i++)
134: {
135: cout<<"Node "<<i<<"("<<g.vecVertex.at(i).data<<")";
136:
137: for (int j = 0; j < g.vecVertex.at(i).vecLoc.size(); j++)
138: {
139: cout<<"->"<<g.vecVertex.at(i).vecLoc.at(j);
140: }
141:
142: cout<<endl;
143: }
144: }
145:
146: void DepthFirstSearch( Graph& g )
147: {
148: cout<<"Depth First Search the graph:"<<endl;
149:
150: for (int i = 0; i < g.iVertexNum; i++)
151: {
152: if (!(g.vecVertex.at(i).bIsVisited))
153: {
154: DepthFirstSearch(g, i);
155: }
156: }
157: }
158:
159: void DepthFirstSearch(Graph& g, int v)
160: {
161: int iAdjacent = 0;
162: SVertexNode node = g.vecVertex.at(v);
163:
164: // Visit the vertex and mark it.
165: cout<<g.vecVertex.at(v).data<<endl;
166: g.vecVertex.at(v).bIsVisited = true;
167:
168: // Visit the adjacent vertex.
169: for (int i = 0; i < node.vecLoc.size(); i++)
170: {
171: iAdjacent = node.vecLoc.at(i);
172:
173: if (!(g.vecVertex.at(iAdjacent).bIsVisited))
174: {
175: DepthFirstSearch(g, iAdjacent);
176: }
177: }
178:
179: }
180:
181:
三、输出结果
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
时间： 2024-11-06 07:40:13