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

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

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

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

解決済

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

yoduru
yoduru

総合スコア11

C++

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

2回答

0評価

0クリップ

229閲覧

投稿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++

#include<iostream> #include<string> #include<list> #include<iostream> #include<string> #include<list> #include<map> #include<fstream> #include<vector> using namespace std; class Vertex; class Adjacent { // 「隣接頂点」のデータ構造。 // 「頂点へのポインタ」と「重み」をもつ。 Vertex* vertex; string control; public: Adjacent( Vertex* v, string c ) : vertex(v), control(c) { }; Adjacent( ) : vertex(NULL), control("") { }; friend class Vertex; friend class Graph; }; class Vertex { // 頂点のデータ構造 string name; // 頂点の名前 list<Adjacent> adj_list; // 隣接頂点のリスト bool flag; string con; Vertex* prev; Vertex( string n ) : name(n), flag(false), con(""), prev(NULL) { }; void AddAdjacent( Vertex* v, string c ) // 隣接頂点の追加 { adj_list.push_back( Adjacent( v, c ) ); }; void PrintAdjList( ); void PrintSpanTree(); void Reset(); friend class Graph; }; void Vertex::PrintAdjList( ) { cout << name << " : "; list< Adjacent >::iterator itr; for( itr = adj_list.begin(); itr != adj_list.end(); itr++ ) cout << itr -> vertex -> name << "(" << itr -> control << ") "; cout << endl; } void Vertex::Reset(){ flag = false; con = ""; prev = NULL; } class Graph { map < string, Vertex* > vmap; // 頂点名と頂点オブジェクトへのポインタの対応 int n_vertex; // 頂点数 int n_edge; // 辺数 void dfs( Vertex* v,Vertex* ve ); public: Graph ( ) : n_vertex(0), n_edge(0) { }; ~Graph(){ map< string, Vertex* >::iterator itr; for( itr = vmap.begin(); itr != vmap.end(); itr++ ) delete itr -> second; }; void AddEdge( string v1, string v2, string control ); void PrintAdjList( ); void Reset(); void DFS(string start,string goal); }; // // 辺の追加。 // void Graph::AddEdge( string v1name, string v2name, string control ) { if ( vmap.find(v1name) == vmap.end() ) { vmap[ v1name ] = new Vertex( v1name ); n_vertex++; } if ( vmap.find(v2name) == vmap.end() ) { vmap[ v2name ] = new Vertex( v2name ); n_vertex++; } vmap[ v1name ] ->AddAdjacent( vmap[ v2name ], control ); n_edge++; } void Graph::PrintAdjList() { map< string, Vertex* >::iterator itr; for( itr = vmap.begin(); itr != vmap.end(); itr++ ) itr -> second -> PrintAdjList(); } void Graph::Reset(){ map< string, Vertex* >::iterator itr; for( itr = vmap.begin(); itr != vmap.end(); itr++ ) itr -> second -> Reset(); } void Graph::DFS( string start,string goal ){ if( vmap.find( start ) == vmap.end() ){ cout<< "not found"; return ; } Vertex* v = vmap[ start ]; v -> flag = true; v -> con = ""; v -> prev = NULL; Vertex* ve = vmap[ goal ]; // cout << v -> name << "-(" << v -> con << ")-" <<ve -> name<<endl; dfs( v , ve); } //現在問題となっている箇所 void Graph::dfs( Vertex* v ,Vertex* ve ){ list< Adjacent >::iterator itr; for( itr = v -> adj_list.begin(); itr != v -> adj_list.end(); itr++ ){ Vertex* w = itr -> vertex; //cout<< w-> name; if(w->name==ve->name){ w -> con = itr -> control; cout << v -> name << "-(" << w -> con << ")-" << w->name <<endl<<endl; break; } if( !w -> flag ){ w -> prev = v; w -> flag = true; w -> con = itr -> control; cout << v -> name << "-(" << w -> con << ")-"; dfs( w , ve ); } } } int main() { Graph g; string a,b,c,filename; g.AddEdge( "A", "B", "CA1" ); g.AddEdge( "B", "D", "CA2" ); g.AddEdge( "D", "E", "CA3" ); g.AddEdge( "A", "C", "CA4" ); g.AddEdge( "C", "E", "CA6" ); g.AddEdge( "C", "F", "CA5" ); /* g.AddEdge( "D", "C", "CA7" ); g.AddEdge( "D", "E", "CA8" ); g.AddEdge( "D", "F", "CA9" ); g.AddEdge( "D", "G", "CA10" ); g.AddEdge( "E", "G", "CA11" ); g.AddEdge( "G", "F", "CA12" ); */ g.PrintAdjList(); cout << endl; g.Reset(); g.DFS( "A" , "E"); // 深さ優先探索 cout << endl; return 0; }

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

同じタグがついた質問を見る

C++

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