# eryar

PipeCAD - Plant Piping Design Software.
RvmTranslator - Translate AVEVA RVM to OBJ, glTF, etc.
posts - 564, comments - 590, trackbacks - 0, articles - 0

eryar@163.com

#### 二、C++实现

```  1: //------------------------------------------------------------------------------
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.
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.
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: {
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:     {
188:
190:         {
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: ```