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

Question

前提・実現したいこと

C++で有向辺付きグラフから指定した始点から終点までの経路探索し、すべての経路を出力するプログラムを作りたいですのですがうまく経路を出力することができません。
例）AからEまでの経路をすべて出力する。

出力結果
A-B-D-E
A-C-E

発生している問題・エラーメッセージ

深さ優先探索を利用しており、作成したプログラムではAからEまでの経路は出ますが、
例えばAからFまでの経路を求めると

A-B-D-A-C-F

のような結果が出力されてしまいます。
理想としては
A-C-F
という出力結果が望ましいです。

コンソールに出力する命令が深さ優先探索する関数内に含まれているため、経路を出力する用として別の関数を生成し、指定した頂点に到達しない場合は経路を出力しないという処理をすればいいのかと考えていますが、どういった処理をすればいいのか思いつきません。どうかご教授のほどよろしくお願いいたします。

該当のソースコード

#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;
}

Answer 1

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

実装例

void Graph::PrintRoute(Vertex* ve) {
    vector<Vertex*> route;
    for (Vertex* v = ve; v != NULL; v = v->prev)
        route.push_back(v);
    for (auto i = route.rbegin(); i != route.rend(); ++i) {
        if ((*i)->prev)
            cout << "-(" << (*i)->con << ")-";
        cout << (*i)->name;
    }
    cout << endl << endl;
}

Answer 2

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