質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

2回答

971閲覧

有向辺付きグラフによる指定した頂点間の経路出力

yoduru

総合スコア11

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2022/01/09 20:37

前提・実現したいこと

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

Vertexprevに直前の頂点が入っているのだから、終点からprevを順番にたどったうえで逆順に表示する関数を作って、終点に到達したときだけ呼び出せばよいでしょう。

実装例

c++

1void Graph::PrintRoute(Vertex* ve) { 2 vector<Vertex*> route; 3 for (Vertex* v = ve; v != NULL; v = v->prev) 4 route.push_back(v); 5 for (auto i = route.rbegin(); i != route.rend(); ++i) { 6 if ((*i)->prev) 7 cout << "-(" << (*i)->con << ")-"; 8 cout << (*i)->name; 9 } 10 cout << endl << endl; 11}

投稿2022/01/09 21:37

編集2022/01/11 12:06
actorbug

総合スコア2429

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

自己解決

別で答えを格納するvectorを用意して探索後格納していき、ゴールに到達ししたら出力することをしたらできました。

投稿2022/01/12 07:33

yoduru

総合スコア11

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問