Witam,
Mam problem. Zadanie polega na napisaniu programu, który zmierzy czas wyszukania cyklu Eulera oraz cyklu Hamiltona w 2 grafach o n wierzchołkach: o nasyceniu 30% i 70% .
Nie wiem jak się za to zabrać. Największy problem to wygenerowanie takich grafów (grafów - bo czas ma być mierzony dla 15 wartości n).
Na razie napisałem tyle:
#include<iostream>
#include<cstdlib>
#include <time.h>
using namespace std;
const int n=10;
int tab[n][n];
void MacierzJednostkowa(int a[n][n])
{
srand (time(NULL));
int q,w;
for(q=0;q<n;q++)
{
for(w=q+1;w<n;w++)
{
a[q][w]=rand()%2;
a[w][q]=a[q][w];
}
}
}
int main()
{
MacierzJednostkowa(tab);
for(int a=0;a<n;a++)
{
for(int b=0;b<n;b++)
{
cout.width(2);
cout<<tab[a][b];
}
cout<<endl;
}
cout<<endl<<endl<<endl;
for(int a=0;a<n;a++)
{
cout<<a+1<<" ==> ";
for(int b=0;b<n;b++)
{
if (tab[a][b]==1) cout<<b+1<<" ";
}
cout<<endl;
}
system("PAUSE");
return 0;
}
Program tworzy losowy graf za pomocą macierzy jednostkowej, wyświetla ją oraz reprezentacje tego grafu za pomocą listy incydencji. No ok... ale co z tego? co dalej?
Aby występował cykl eulera waga wszystkich wierzchołków musi być parzysta - jak to osiągnąć?
Widzę sposób w importowaniu grafu z pliku txt - jeśli posiadacie jakiś generator proszę o link/mail.
Przeszukiwanie grafu odbywałoby się za pomocą DFS
void DFSEuler(int v)
{
while(!L[v].empty())
{
int x = L[v].front();
L[v].pop_front();
for(list<int>::iterator i = L[x].begin(); i != L[x].end(); i++)
if((* i) == v)
{
L[x].erase(i); break;
}
DFSEuler(x);
}
q.push_front(v);
}
// Rekurencyjna procedura DFS przechodzenia grafu
void DFS(int v)
{
visited[v] = true;
for(list<int>::iterator i = L[v].begin(); i != L[v].end(); i++)
if(!visited[*i]) DFS(*i);
}
Proszę o wskazówki.