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.