c++ - 寻找欧拉循环

Question

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

创建欧拉循环:

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

求欧拉圈是基于od DFS。

求欧拉循环适用于 100,200,300 个节点。当它是例如500，应用程序不显示欧拉循环。如果您有任何建议，我应该在代码中更改什么，请发布。

这是一个用欧拉循环创建图形的代码:

#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 不会递减，循环会持续很长时间。

我不确定您使用什么逻辑来创建图表。如果所有顶点的度数都是偶数，则图中将始终存在欧拉循环。您的代码中有很多随机，这可能需要一段时间。

你真的不需要做所有的 DFS 和你已经做的其他事情来找到欧拉循环。这是一个简单的逻辑:

-- 检查以确保所有顶点的度数是偶数。否则，欧拉循环不存在。证明非常简单，留作练习:)

“作为 Königsberg 桥问题的推广，欧拉证明(没有证明)连通图具有欧拉循环当且仅当它没有奇数度的图顶点。” --- http://mathworld.wolfram.com/EulerianCycle.html

-- 选取任意一个顶点并继续遍历该顶点上的任何边，该边之前没有被遍历过。继续遍历......最终你会得到欧拉循环，当你所有的边缘都被遍历时。

请注意，这与哈密顿循环 问题是NP-C 不同。求欧拉循环是多项式，O(E)，因为您将只遍历每条边一次。