オイラーサイクルでグラフを作成するアプリケーションがあります。私の 2 番目のアプリケーションは、オイラー サイクルを見つけることです。
オイラー サイクルの作成:
- オイラーサイクルはグラフを接続する必要があるため、3->6->5->2->0->1->4->3 などのサイクルを作成します。
- 次に、ランダムなエッジを作成します。
- グラフをファイルに保存しています。
オイラー サイクルの検索は、OD DFS に基づいています。
オイラー サイクルの検索は、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();
}
}