深さ優先遍歴DFS隣接表で示す図
12735 ワード
深さ優先ループ隣接テーブルで表される図
DFS the Adjacency List Graph
[email protected]
一、紹介
図を作成した後、図の頂点から残りの頂点を訪問し、各頂点に1回だけアクセスさせることを望んでいます.この過程が図の遍歴(Traversing Graph)である.図の遍歴アルゴリズムは,図の連通性問題,トポロジーソート,キーパスの解などのアルゴリズムを解く基礎である.
深さ優先探索(Depth First Search)は再帰的な遍歴法である.そのプロセスは、図中の任意の頂点から、それに接続されたアクセスされていない頂点にアクセスすることである.したがって、グラフを巡回するプロセスは、実質的に各頂点に対して隣接点を検索するプロセスである.
二、実現コード
図の記憶構造を表す隣接テーブルは依然として使用され、深さ優先遍歴プログラムは以下のコードに示す.
1: //------------------------------------------------------------------------------
2: // Copyright (c) 2012 eryar All Rights Reserved.
3: //
4: // File : Main.cpp
5: // Author : [email protected]
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