前提・実現したいこと
C++で有向辺付きグラフから指定した始点から終点までの経路探索し、すべての経路を出力するプログラムを作りたいですのですがうまく経路を出力することができません。
例)AからEまでの経路をすべて出力する。
出力結果
A-B-D-E
A-C-E
発生している問題・エラーメッセージ
深さ優先探索を利用しており、作成したプログラムではAからEまでの経路は出ますが、
例えばAからFまでの経路を求めると
A-B-D-A-C-F
のような結果が出力されてしまいます。
理想としては
A-C-F
という出力結果が望ましいです。
コンソールに出力する命令が深さ優先探索する関数内に含まれているため、経路を出力する用として別の関数を生成し、指定した頂点に到達しない場合は経路を出力しないという処理をすればいいのかと考えていますが、どういった処理をすればいいのか思いつきません。どうかご教授のほどよろしくお願いいたします。
該当のソースコード
C++
1#include<iostream> 2#include<string> 3#include<list> 4#include<iostream> 5#include<string> 6#include<list> 7#include<map> 8#include<fstream> 9#include<vector> 10 11using namespace std; 12 13class Vertex; 14 15class Adjacent { // 「隣接頂点」のデータ構造。 16 // 「頂点へのポインタ」と「重み」をもつ。 17 Vertex* vertex; 18 string control; 19 20public: 21 Adjacent( Vertex* v, string c ) : vertex(v), control(c) { }; 22 Adjacent( ) : vertex(NULL), control("") { }; 23 24 friend class Vertex; 25 friend class Graph; 26}; 27 28class Vertex { // 頂点のデータ構造 29 30 string name; // 頂点の名前 31 list<Adjacent> adj_list; // 隣接頂点のリスト 32 bool flag; 33 string con; 34 Vertex* prev; 35 36 Vertex( string n ) : name(n), flag(false), con(""), prev(NULL) { }; 37 38 void AddAdjacent( Vertex* v, string c ) // 隣接頂点の追加 39 { adj_list.push_back( Adjacent( v, c ) ); }; 40 void PrintAdjList( ); 41 42 void PrintSpanTree(); 43 44 void Reset(); 45 46 friend class Graph; 47}; 48 49 50void Vertex::PrintAdjList( ) 51{ 52 53 cout << name << " : "; 54 list< Adjacent >::iterator itr; 55 for( itr = adj_list.begin(); itr != adj_list.end(); itr++ ) 56 cout << itr -> vertex -> name << "(" << itr -> control << ") "; 57 cout << endl; 58} 59 60void Vertex::Reset(){ 61 62 flag = false; 63 con = ""; 64 prev = NULL; 65 66} 67class Graph { 68 69 map < string, Vertex* > vmap; // 頂点名と頂点オブジェクトへのポインタの対応 70 int n_vertex; // 頂点数 71 int n_edge; // 辺数 72 73 void dfs( Vertex* v,Vertex* ve ); 74 75public: 76 Graph ( ) : n_vertex(0), n_edge(0) { }; 77 ~Graph(){ 78 map< string, Vertex* >::iterator itr; 79 for( itr = vmap.begin(); itr != vmap.end(); itr++ ) 80 delete itr -> second; 81 }; 82 void AddEdge( string v1, string v2, string control ); 83 void PrintAdjList( ); 84 void Reset(); 85 void DFS(string start,string goal); 86}; 87 88// 89// 辺の追加。 90// 91void Graph::AddEdge( string v1name, string v2name, string control ) 92{ 93 if ( vmap.find(v1name) == vmap.end() ) { 94 vmap[ v1name ] = new Vertex( v1name ); 95 n_vertex++; 96 } 97 if ( vmap.find(v2name) == vmap.end() ) { 98 vmap[ v2name ] = new Vertex( v2name ); 99 n_vertex++; 100 } 101 vmap[ v1name ] ->AddAdjacent( vmap[ v2name ], control ); 102 n_edge++; 103} 104 105void Graph::PrintAdjList() 106{ 107 108 map< string, Vertex* >::iterator itr; 109 for( itr = vmap.begin(); itr != vmap.end(); itr++ ) 110 itr -> second -> PrintAdjList(); 111} 112 113void Graph::Reset(){ 114 115 map< string, Vertex* >::iterator itr; 116 for( itr = vmap.begin(); itr != vmap.end(); itr++ ) 117 itr -> second -> Reset(); 118 119} 120 121 122void Graph::DFS( string start,string goal ){ 123 124 if( vmap.find( start ) == vmap.end() ){ 125 cout<< "not found"; 126 return ; 127 } 128 129 Vertex* v = vmap[ start ]; 130 v -> flag = true; 131 v -> con = ""; 132 v -> prev = NULL; 133 134 Vertex* ve = vmap[ goal ]; 135 136 137 // cout << v -> name << "-(" << v -> con << ")-" <<ve -> name<<endl; 138 dfs( v , ve); 139 140} 141//現在問題となっている箇所 142void Graph::dfs( Vertex* v ,Vertex* ve ){ 143 144 list< Adjacent >::iterator itr; 145 146 for( itr = v -> adj_list.begin(); itr != v -> adj_list.end(); itr++ ){ 147 148 149 Vertex* w = itr -> vertex; 150 //cout<< w-> name; 151 152 if(w->name==ve->name){ 153 w -> con = itr -> control; 154 cout << v -> name << "-(" << w -> con << ")-" << w->name <<endl<<endl; 155 break; 156 } 157 158 if( !w -> flag ){ 159 w -> prev = v; 160 w -> flag = true; 161 w -> con = itr -> control; 162 163 cout << v -> name << "-(" << w -> con << ")-"; 164 dfs( w , ve ); 165 166 167 } 168 } 169} 170 171 172int main() 173{ 174 Graph g; 175 string a,b,c,filename; 176 177 g.AddEdge( "A", "B", "CA1" ); 178 g.AddEdge( "B", "D", "CA2" ); 179 g.AddEdge( "D", "E", "CA3" ); 180 g.AddEdge( "A", "C", "CA4" ); 181 g.AddEdge( "C", "E", "CA6" ); 182 g.AddEdge( "C", "F", "CA5" ); 183 184 /* 185 g.AddEdge( "D", "C", "CA7" ); 186 g.AddEdge( "D", "E", "CA8" ); 187 g.AddEdge( "D", "F", "CA9" ); 188 g.AddEdge( "D", "G", "CA10" ); 189 g.AddEdge( "E", "G", "CA11" ); 190 g.AddEdge( "G", "F", "CA12" ); 191*/ 192 g.PrintAdjList(); 193 cout << endl; 194 195 g.Reset(); 196 g.DFS( "A" , "E"); // 深さ優先探索 197 cout << endl; 198 199 200 201 return 0; 202} 203
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。