+关注继续查看

eryar@163.com

#### 二、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:

#### 四、结论

|
4月前
|

41 0
|
4月前
|

64 0
|
10月前
|

es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法
es 实现图的基本算法 图的深度优先搜索 广度优先搜索 普利姆算法
78 0
|
10月前

75 0
|
11月前
|

54 0
UPC Graph （最小生成树 || 并查集+二分）
UPC Graph （最小生成树 || 并查集+二分）
53 0
|

80 0
|

C++实现图 - 05 拓扑排序

336 0
|

C++实现图 - 02 图的遍历（DFS、BFS）

247 0
|

PTA——7-2 图深度优先遍历
PTA——7-2 图深度优先遍历
399 0