Hierholzer算法找到eulerian路徑

Question

我已經實現了hierholzer算法來使用兩個堆棧在圖中查找eulerian路徑。以下是我的實施。有一些運行時錯誤，會很高興，如果有人能幫助

#include<bits/stdc++.h> 
using namespace std; 


stack<int> result; 
stack<int> temp; 


class graph 
{ 
int v; 
list<int> *adj; 
public: 
graph(int v) 
{ 
    this->v=v; 
    adj=new list<int> [v]; 
} 

~graph() 
{ 
    delete []adj; 
} 

void add_edge(int u,int v) 
{ 
    adj[u].push_back(v); 
    adj[v].push_back(u); 

} 

void remove_edge(int u, int v); 
int start_vertex(); 
void print_euler_path(int u); 
bool allvisited(); 


}; 

    int graph::start_vertex() 
{ 
int u=0; 
for(int u=0;u<v;u++) 
{ 
    if(adj[u].size() & 1) 
    break; 


} 

return u; 
} 


bool graph::allvisited() 
{ 
for(int i=0;i<v;i++) 
{ 
    if(adj[i].size()>0) 
    { 
     list<int>::iterator it; 
     for(it=adj[i].begin();it!=adj[i].end();it++) 
     { 
       if(*it!=-1) 
       return false; 

     } 
    } 
} 

return true; 


} 


void graph::remove_edge(int u,int v) 
{ 
list<int>::iterator i; 
i=find(adj[u].begin(),adj[u].end(),v); 
*i=-1; 
i=find(adj[v].begin(),adj[v].end(),u); 
*i=-1; 

} 


void graph::print_euler_path(int u) 
{ 


temp.push(u); 
list<int>::iterator i; 
int flag=0; 

if(allvisited()) 
return; 


for(i=adj[u].begin();i!=adj[u].end();i++) 
{ 
    if(*i!=-1) 
    { 
     cout<<"S"; 
     remove_edge(u,*i); 
     print_euler_path(*i); 

    } 
} 
if(!temp.empty()) 
{ 
     int k=temp.top(); 
     temp.pop(); 
     result.push(k); 
     if(!temp.empty()) 
     print_euler_path(temp.top()); 
} 


} 


int main() 
{ 

graph g(6); 
g.add_edge(0,1); 
g.add_edge(1,2); 
g.add_edge(2,3); 
g.add_edge(3,0); 
g.add_edge(5,1); 
g.add_edge(5,2); 
g.add_edge(4,1); 
g.add_edge(4,2); 



int u=g.start_vertex(); 

g.print_euler_path(u); 


while(!result.empty()) 
{ 
    cout<<result.top()<<" "; 
    result.pop(); 
} 
return 0; 


} 

進行精確的邏輯，你可以參考http://iampandiyan.blogspot.in/2013/10/c-program-to-find-euler-path-or-euler.html

Answer 1

我不認爲這些行做你想要什麼：

remove_edge(u,*i); 
    print_euler_path(*i);