寻找欧拉循环

Question

我有一个用Euler循环创建图形的应用程序。我的第二个应用程序是寻找Euler循环。

创建欧拉循环：

1. 创建一个循环，例如3->6->5->2->0->1->4->3，因为Euler循环应该是连通图
2. 然后创建随机边。
3. 将图表保存到文件中。

寻找欧拉循环是基于DFS的。

查找Euler循环对100,200,300个节点有效。当它是例如500，应用程序不显示欧拉循环。如果你有任何建议，我应该修改什么代码，张贴它。

下面是用Euler循环创建图形的代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<vector>
#include<ctime>
#include<cstdlib>
#include<list>
#include<stack>
#include<ctime>
#include<fstream>
using namespace std;

    bool matrix[1500][1500];
int main()
{
    srand(time(0));
    ofstream zapis;
    zapis.open("graph cycle euler.txt");

vector<int> cycle;
    //bool macierz[500][500];
    int N, density;
cout<<"N and density: "<<endl;
cin>>N>>density;

    for (int i = 0; i<1500; i++)
    {
        for (int j=0; j<1500; j++)
        {
            matrix[i][j]=0;
        }
    }


for (int i = 0; i<N; i++)
{
    cycle.push_back(i);
}


random_shuffle (cycle.begin(), cycle.end());


matrix[cycle[0]][cycle[cycle.size()-1]]=1;
matrix[cycle[cycle.size()-1]][cycle[0]]=1;

for (int i=0; i<cycle.size()-1; i++)
{
    matrix[cycle[i]][cycle[i+1]]=1;
    matrix[cycle[i+1]][cycle[i]]=1;
//    cout<<cycle[i]<<" "<<cycle[i+1]<<endl;
}


int randnumber, randnumeber2,randnumber3;

//ile=ile-2*N;
int howMany=0;
for (int i=0; i<N; i++)
{
    howMany=howMany+i;
}
howMany=howMany*60/100-N;

while(howMany>=0)
{

    randnumber=rand()%N;
    randnumeber2=rand()%N;
    randnumber3=rand()%N;

    if((matrix[randnumber][randnumeber2]==0) && (matrix[randnumeber2][randnumber3]==0) && (matrix[randnumber][randnumber3]==0) && (randnumber!=randnumeber2) && (randnumber!=randnumber3) && (randnumeber2!=randnumber3))
    {
        matrix[randnumber][randnumeber2]=1;
        matrix[randnumeber2][randnumber]=1;
        matrix[randnumeber2][randnumber3]=1;
        matrix[randnumber3][randnumeber2]=1;
        matrix[randnumber][randnumber3]=1;
        matrix[randnumber3][randnumber]=1;

        howMany=howMany-3;
    }
}

int M=0;
for (int i=0; i<N; i++)
{
    for (int j=0; j<N; j++)
    {
        if(matrix[i][j]==1)
        M++;
    }
}

zapis<<N<<endl<<density<<endl<<M<<endl;

for (int i=0; i<N; i++)
{
    for (int j=0; j<N; j++)
    {
        if(matrix[i][j]==1)
        zapis<< i <<" "<< j<<endl;
    }
}

}

这里是我寻找欧拉循环的代码。

#include<iostream>
#include<vector>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
#include<list>
#include <stack>
#include<fstream>
using namespace std;

int s;
list<int> L[3000];
stack<int> stos;
void dfs (int v)
{

while (!L[v].empty())
    {

        int x=L[v].front();
        L[v].pop_front();
        for (list<int>::iterator y=L[x].begin(); y != L[x].end(); y++)
            if (v==(*y))
            {
                L[x].erase(y); break;
            }
    dfs(x);
    }
stos.push(v);
}

int main()
{
    ifstream odczyt;
    odczyt.open("graph cycle euler.txt");
int N, gestosc, m;
odczyt>>N>>gestosc>>m;

int w1,w2;
for (int i=0; i<m; i++)
{
    odczyt>>w1>>w2;
    L[w1].push_back(w2);
    //L[w2].push_back(w1);
}

int start=0;

dfs(start);

    while(!stos.empty())
    {
        cout<<stos.top()<<" ";
        stos.pop();
    }
}

Answer 1

应用程序不显示或保持计算？我猜你的程序500是永远运行，因为if((matrix[randnumber][randnumeber2]==0) && (matrix[randnumeber2][randnumber3]==0) .对于生成的随机数，此条件不成立，因此howMany不会减少，循环将持续很长一段时间。

我不知道你用什么逻辑来创建图表。如果所有顶点的度均为偶数，则图中始终存在欧拉圈。代码中有大量的random，这可能需要一段时间。

你真的不需要做所有的DFS和你做过的其他事情来找到欧拉周期。下面是一个简单的逻辑：

-检查以确保所有顶点的程度是相等的。如果没有，则不存在欧拉循环。这个证据非常简单，并作为练习留下:)

"As a generalization of the Königsberg bridge problem, Euler showed (without proof) that a connected graph has an Eulerian cycle iff it has no graph vertices of odd degree." - http://mathworld.wolfram.com/EulerianCycle.html

--选择任何顶点，并继续遍历顶点上的任何边缘事件，这一点以前没有被遍历过。保持traversing.....Eventually你将结束欧拉周期，当你的边缘已经被遍历。

请注意，这与hamiltonian cycle问题(即NP-C问题)不一样。寻找欧拉循环是多项式的，O(E)，因为你只需要遍历每一条边一次。