我正在尝试打印深度优先遍历.我有以下代码继续给我一个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 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代码,那么我的程序运行正常.当我尝试打印第三张图时,这是我的输出.请注意,我的遍历运行不正常.
解决方法
所以我使用以下算法找出了我的问题.希望这可以帮助任何有同样问题的人.
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
}
