#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include <iostream>
#include <stack>
#include <vector>
#include <list>
using namespace std;
stack <int> drek;
stack <int> dtop;
//int beg1, beg2, end1, end2, beg3, end3;
// tworzenie macierzy sasiedztwa
void macierz_sasiedztwa (int n, int **macierz)
{
int i,j;
for (i=0; i < n; i++)
{
for (j=0; j < n; j++)
{
if (i < j)
{
macierz[i][j]=0;
}
/*{
macierz[i][j] = 1;
}*/
else
{
macierz[i][j] = 0;
}
}
}
}
// szukanie cyklu hamiltona
int v,e;
const int wierzcholki = 16;
bool odwiedzone [wierzcholki +1];
list <int> lista, dlugosc[wierzcholki+1];
// generowanie grafu eulerowskiego
void generuj(int n, int m, int **NM)
{
cout<<"*GP0 ";
// tworzenie losowego grafu nieskierowanego o m krawÍdziach [macierz sπsiedztwa]
int i = m, x, y,deg;
cout<< i << endl;
while(i)
{
cout<< i << endl;
y = rand()%n; // losowy wierzcho≥ek (od 0 do n-1)
x = rand()%n;
if(NM[x][y] != 1 && x!=y) // bez petli w≥asnych
{
NM[x][y] = NM[y][x] = 1;
i--;
}
// nadawanie parzystoúci wierzcho≥kom
for(x=0; x<n-1; x++) // dla n-1 wierzcho≥kÛw (graf spÛjny zawiera parzysta liczbe wierzcho≥kÛw o nieparzystych stopniach)
{
deg = 0;
int g=n-1;
for(y=0; y<n; y++) if(NM[x][y]) deg++; // obliczamy deg(x)
if (deg%2) // jeúli stopieÒ wierzcho≥ka jest nieparzysty
{
y = rand()%g+(x+1); // od x+1 do n-1 (dowony wiÍkszy od x)
if( NM[x][y] ) // i wylosowana krawÍdü istnieje, to usuwamy jπ
{
NM[x][y] = 0;
NM[y][x] = 0;
i++;
}
else // else: dodajemy w wylosowanym miejscu krawÍdü
{
NM[x][y] = 1;
NM[y][x] = 1;
i--;
}
}
}
}
printf("m = %d, ", m+i); // m sie zmienia :/
// sprawdzanie spojnosci grafu
bool *visited = new bool[n];
bool all_visited = 1;
/* dfs(n, 0, visited, NM);
*/
for(int z=0; z<n-1; z++)
{
for(int l=0; l<n-1; l++)
{
if(NM[z][l]==1)
{
visited[z]=1;
break;
}
else
visited[z]=0;
}
}
for(x=0; x<n-1; x++) if (!visited[x])
{
all_visited = 0;
break;
}
if (all_visited) printf("graf spojny\n");
else
{
printf("graf niespojny\nponowne generowanie: ");
generuj(n, m, NM);
}
cout<<"*GK* ";
}
// szukanie cyklu Eulera w grafie
void Euler(int n, int** NM, int v)
{
for(int x=0; x<n; x++) // dla wszystkich wierzcho≥kow x
{
if(NM[v][x]) // jesli istnieje krawÍdz v-x
{
NM[v][x] = NM[x][v] = 0; // usun te krawÍdz (odpowiednik zaznaczenia jako odwiedzona)
Euler(n, NM, x); // analizuj x
}
}
// printf("%d, ", v); // wypisz w kolejnosci zdejmowania ze stosu
}
// szukanie cyklu Hamiltona w grafie
int nr = 0, CH = 0, found = 0; // dlugosc aktualnej sciezki, liczba cykli w grafie, flaga znalezienia cyklu
int Hamilton(int n, int v, int* path, bool* visited, int** NM)
{
cout<<"*b ";
if(found) return 5;
path[nr++] = v; // dopisujemy wierzcholek do sciezki
if (nr != n) // jesli sciezka jest jeszcze niepelna
{
visited[v] = 1;
for (int x=0; x<n; x++) // dla wszystkich wierzcho≥kow x
if (NM[v][x] && !visited[x]) // jesli istnieje krawedz v-x i x nie byl odwiedzony
Hamilton(n, x, path, visited, NM); // przejdz do x
visited[v] = 0;
}
else if (NM[v][0]) // jesli scieøka zawiera juz wszystkie wierzcho≥ki i jest cyklem
{
// printf("CH: ");
// for (int x=0; x<n; x++); printf("%d, ", path[x]); // wypisz ja
// printf("0\n");
if (!found)
{
// czas_stop(); // po znalezieniu pierwszego cyklu wypisz czas
//czas_oblicz();
//printf("H1 = ");
//czas_print();
found = 1;
}
CH++; // liczba cykli++
}
nr--; // usuwamy wierzcho≥ek ze scieøki
cout<<"*k ";
}
int main()
{
srand(time(0));
unsigned int n;
int **macierz, *lista;
bool *odwiedzone;
int r=2500;
macierz = new int*[r];
lista = new int [r];
odwiedzone = new bool [r];
for (unsigned int i = 0; i < r; i++)
{
macierz[i] = new int [r];
}
macierz_sasiedztwa(n, macierz);
for (n=10; n<=21; n++)
{
cout<< n << endl;
int wspolczynnik[6] = {20,30,40,60,80,95};
for(int z=0; z<6; z++)
{
cout<<"hamilton 0,"<< wspolczynnik[z]<<endl;
v = n;
e = (v*v*wspolczynnik[z])/100;
cout<<"gen\n";
generuj(v,e,macierz);
cout << "Nasycenie: "<< wspolczynnik[z]<< " %"<<endl;
Hamilton(v,e,lista,odwiedzone,macierz);
cout << "Ilosc krawedzi: "<<e<<endl;
for (unsigned int i = 0; i < v; i++)
{
for(int j=0; j<v; j++)
{
macierz[i][j] = 0;
}
odwiedzone[i]=0;
lista[i]=0;
}
macierz_sasiedztwa(v, macierz);
//euler
/* cout<<"euler"<<endl;
v = 100*n;
e = (v*v*wspolczynnik[z])/100;
generuj(v,e,macierz);
Euler(e,macierz,0);
for (unsigned int i = 0; i < v; i++)
{
for(int j=0; j<v; j++)
{
macierz[i][j] = 0;
}
odwiedzone[i]=0;
lista[i]=0;
}
macierz_sasiedztwa(v, macierz);
*/
}
}
return 0;
}
Mam problem z tym programem, a mianowicie z generowaniem grafu spójnego, uniemożliwia mi to sprawdzenie czy szukanie cykli jest poprawne.
Jeżeli bylibyście tak uprzejmi i pomogli osobie nieogarniającej:)