c – 深度优先图遍历

概述我正在尝试打印深度优先遍历.我有以下代码继续给我一个seg错误.当我尝试在图中打印最后一个顶点时,似乎正在发生这种情况.我从顶点’A’开始的第一次遍历,可以正常工作.但是当我尝试从D开始进行深度优先打印时,我得到了seg错误.这是我的源代码： 这是我的原始源代码： void wdigraph::depth_first(int u) const { bool found = false; 我正在尝试打印深度优先遍历.我有以下代码继续给我一个seg错误.当我尝试在图中打印最后一个顶点时,似乎正在发生这种情况.我从顶点’A’开始的第一次遍历,可以正常工作.但是当我尝试从D开始进行深度优先打印时,我得到了seg错误.这是我的源代码：

这是我的原始源代码：

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 linksclass 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 digraphprivate:    int size;                               // size of digraph    vector < char > label;                  // node labels    vector < vector < int > > adj_matrix;   // adjacency matrix};// default class constructorwdigraph :: 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 graphvoID proc_graph(wdigraph&);       // function declarationint 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 = 5Adjacency Matrix  |  A  B  C  D  E--|---------------A |  -  -  -  6  -  |B |  -  -  8  -  -  |C |  7  -  -  -  -  |D |  7  9 10  -  1  |E |  4  - 10  -  -Paths by Depth-First SearchA->D->B->C->ESegmentation fault (core dumped)

如果我从for循环中删除u = i代码,那么我的程序运行正常.当我尝试打印第三张图时,这是我的输出.请注意,我的遍历运行不正常.

解决方法 所以我使用以下算法找出了我的问题.希望这可以帮助任何有同样问题的人.

push current onto stackmark as visitedprint currentwhile (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}

总结

以上是内存溢出为你收集整理的c – 深度优先图遍历全部内容，希望文章能够帮你解决c – 深度优先图遍历所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。