深度优先遍历DFS用邻接表表示的图

深度优先遍历用邻接表表示的图 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 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

图的BFS/DFS 树是一种特殊的图：有向无环图 图分为有向图和无向图 无向图可以看作是特殊的有向图，一条边a-b可以建立一条a到b的，再建立一条b到a的
C++实现图 - 02 图的遍历（DFS、BFS） 上一讲我们对图有了一个大概的了解，但是只讲了如何存储图，还没有讲如何遍历图。这一讲我们来介绍图的遍历方式，一共分为深度优先搜索（DFS）和宽度优先搜索（BFS）。
图的广度优先搜索和深度优先搜索（邻接链表表示） 邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如下图所示，邻接表表示为