0

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

创建欧拉循环：

  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();
    }
}
4

1 回答 1

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

-- 选择任何顶点并继续遍历该顶点上的任何边缘事件，这些边缘事件之前没有被遍历过。继续遍历.....最终，当您遍历所有边时，您将得到欧拉循环。

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

于 2013-05-23T12:48:15.727 回答