c++ - 深度优先图遍历

Question

我正在尝试打印深度优先遍历。我有以下代码继续给我一个段错误。当我尝试打印图中的最后一个顶点时，它似乎正在发生。我从顶点“A”开始的第一次遍历按预期工作。但是当我尝试从 D 开始进行深度优先打印时，我遇到了段错误。这是我的源代码:

这是我的原始源代码:

void wdigraph::depth_first(int u) const {

  bool found = false;

  vector<bool> visited;             // create a boolean vector
  for(int i =0; i < size; i++)      // the size of the graph
    visited.push_back(false);       // to mark when a node has been visited

  stack<int> depth_first;           // used to hold vertices that have been visited
  visited[u] = true;                // mark as visited
  cout << label[u];                 // print first vertex
  depth_first.push(u);              // put first vertex on stack

  while(!all_visited(visited)) {    // continue until all vertices have been visited
    found = false;

    for(unsigned i = 0; i < visited.size() && !found; i++) {
      if(adj_matrix[u][i] != 0 && !visited[i]) {  // found next vertex
        cout << "->" << label[i];   // print vertex
        visited[i] = true;          // mark vertex as visited
        depth_first.push(i);        // push vertx onto stack
        found = true;               // set found = true to end for loop
        u = i;
      }//endif
    }//endfor  

    if(found == false) {            // no available neighbors
      u = depth_first.top();        // get top of stack
      depth_first.pop();            // pop from stack
    }//endif
  }//endwhile 

  cout << '\n';
}

void wdigraph::print_graph() const {
  cout << '\n';
  cout << "No of Nodes = " << size << endl;

  cout << "\nAdjacency Matrix\n" << endl;

  cout << "  |";
  for(int i = 0; i < size; i++)
    cout << "  " << label[i];

  cout << '\n';

  cout << "--|";
  for(int i = 0; i < size; i++)
    cout << "---";
  cout << '\n';

  for(int i = 0; i < size; i++) {
    cout << label[i] << " |";

    for(int j = 0; j < size; j++) {
      if(adj_matrix[i][j] != 0)
        cout << " " << setw(2) << right << adj_matrix[i][j];
      else
        cout << "  -";
    }//endjfor

      cout << '\n';

      if(i != size-1)
        cout << "  |" << endl;
  }//endifor

  cout << '\n';
}
bool all_visited(vector<bool> &v) {
  for(unsigned i = 0; i < v.size(); i++)
    if(v[i] == false)
      return false;

  return true;
}

这是头文件和构造函数:

// definition of weighted digraph

#define NO_NODES   1    // default size for no of nodes in digraph
#define LINK_PROB  0.25 // prob of having direct link between nodes
#define MAX_WEIGHT 10   // max weight factor for links
class wdigraph {
public:
    wdigraph ( int = NO_NODES );            // default constructor
    ~wdigraph ( ) { };                      // destructor
    int get_size ( ) const { return size; } // returns size of digraph

    void depth_first ( int ) const;// traverses graph using depth-first search
    void print_graph ( ) const;    // prints adjacency matrix of digraph

private:
    int size;                               // size of digraph
    vector < char > label;                  // node labels
    vector < vector < int > > adj_matrix;   // adjacency matrix
};

// default class constructor

wdigraph :: wdigraph ( int n ) : size ( n )
{
    // allocate dynamic memory

    label = vector < char > ( size );
    adj_matrix = vector < vector < int > > ( size );
    for ( int i = 0; i < size; i++ )
        adj_matrix [ i ] = vector < int > ( size );

    // assign labels to each node

    label [ 0 ] = 'A';
    for ( int i = 1; i < size; i++ )
        label [ i ] = label [ i - 1 ] + 1;

    // determine weights for links between nodes randomly
    // and build adjacency matrix

    srand ( 1 );
    for ( int i = 0; i < size; i++ ) {
        adj_matrix [ i ] [ i ] = 0;
        bool flag = false;
        for ( int j = 0; j < size; j++ ) {
            if ( j == i ) continue;
            double r = ( double ) rand ( ) / RAND_MAX;
            adj_matrix [ i ] [ j ] =
                ( r <= LINK_PROB ) ? rand ( ) % MAX_WEIGHT + 1 : 0;
            if ( adj_matrix [ i ] [ j ] > 0 ) flag = true;
        }

        // if node is not connected to any other node, then
        // connect this node to random node

        if ( size > 1 && !flag ) {
            int k; while ( ( k = rand ( ) % size ) == i ) ;
            adj_matrix [ i ] [ k ] = rand ( ) % MAX_WEIGHT + 1;
        }
    }
}

这是主要程序:

#define M  3   // print every M-th node's path when traversing
#define N2 5   // number of nodes in second graph
#define N3 20  // number of nodes in third graph


void proc_graph(wdigraph&);       // function declaration

int main() {
  // create three weighted digraphs
  wdigraph graph1(NO_NODES);
  wdigraph graph2(N2);
  wdigraph graph3(N3);

  //proc_graph(graph1);   // print first graph
  proc_graph(graph2);   // print first graph
  //proc_graph(graph3);   // print first graph

  return 0;
}

void proc_graph(wdigraph &g) {
  cout << '\n';
  cout << "A Weighted Digraph" << endl;    // print header
  cout << "__________________" << endl;    // print header underline

  g.print_graph();                         // print graph

  cout << "Paths by Depth-First Search" << endl;
  for(int i = 0; i < g.get_size(); i += M)
    g.depth_first(i);
}

这是我得到的输出。该图显示了每条边的权重。 '-' 表示没有边缘。

A Weighted Digraph
__________________

No of Nodes = 5

Adjacency Matrix

  |  A  B  C  D  E
--|---------------
A |  -  -  -  6  -
  |
B |  -  -  8  -  -
  |
C |  7  -  -  -  -
  |
D |  7  9 10  -  1
  |
E |  4  - 10  -  -

Paths by Depth-First Search
A->D->B->C->E
Segmentation fault (core dumped)

如果我从 for 循环中删除 u = i 代码，那么我的程序可以正常运行。这是我尝试打印第三张图时的输出。请注意，我的遍历没有正确行进。

Answer 1

所以我使用以下算法解决了我的问题。希望这对遇到同样问题的人有所帮助。

push current onto stack
mark as visited
print current
while (stack is not empty) {
  current = stack top
  of N neighbors of current, find first that hasnt been visited
    if such neighbor exists
      add to stack
      mark as visited
      print
    if no neighbor exists
      pop from stack
}