Generowanie grafu :: 4programmers.net

lukasz93

2012-12-22T11:14:29+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 46

0

Witam, potrzebuje napisać program który wygeneruje mi graf (nie musi być spójny) nieskierowany o N wierzchołkach, w którym z każdego wierzchołka wychodzi dokładnie M krawędzi.

Rozpisałem sobie to w ten sposób:
Tworzę pusty graf np. tablica NxN.
Każdy wierzchołek posiada licznik wychodzących od niego krawędzi (początkowo wyzerowana). tablica[N]
No i w pętli dla każdego wierzchołka sprawdzam, czy posiada mniej niż M krawędzi, jeśli tak to losuje drugi wierzchołek z którym ma być połączony. Jeśli wylosowany wierzchołek ma mniej niż M krawędzi wtedy wpisuje do grafu połączenie między nimi i pętla leci dalej. Sprawdzane jest również, czy wylosowany wierzchołek nie został już wylosowany wcześniej.

Niestety program się zapętla w nieskończoność, nie wiem jaki warunek musi zostać spełniony, aby zakończyło program. Teoretycznie jeżeli mam np. 20 wierzchołków i z każdego ma wychodzić 4 połączenia to łącznie powinno być 80 połączeń. Jako, że graf jest nieskierowany więc krawędzi będzie 40. Zatem program powinien zakończyć generowanie grafu, gdy wylosuje 40 krawędzi. Niestety program nie działa tak jak chce, i losuje dla niektórych wierzchołków mniej niż 4 krawędzie. Kod który napisałem wygląda następująco:

Kopiuj

#include <iostream>
#include <windows.h>
#include <time.h>

int main(int argc, char* argv[])
{
    const int V = 20;
    const int E = 4;

    srand(time(NULL));

    int graph[V][V];

    for(int i=0; i<V; i++)
        for(int j=0; j<V; j++)
            graph[i][j]=0;

    int filled[V];
    for(int i=0; i<V; i++)
        filled[i] = 0;

    int r,c,t,count=0;
    bool b;

    for(int i=0; i<V; i++)
    {
        while(filled[i] < E && count < 40)
        {
            r = rand()%V;
            b = true;

            for(int j=0; j<filled[i]; j++)
                if(r == graph[i][j])
                    b=false;

            if(b==true)
                if(filled[r] < E)
                {
                    graph[i][r] = graph[r][i] = 1;
                    count++;
                    filled[i]++;
                    filled[r]++;
                }
        }
    }

    for(int i=0; i<V; i++)
    {
        for(int j=0; j<V; j++)
        {
            std::cout << graph[i][j];
        }
        std::cout << std::endl;
    }
}

_13th_Dragon

2012-12-22T14:54:25+01:00

Rejestracja: dni
Ostatnio: dni

0

Czy zdajesz sobie sprawę że przy pewnych N M może nie istnieć rozwiązanie?
Np:
N=5
M=3

lukasz93

2012-12-23T02:39:17+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 46

0

Tak. Docelowo graf ma mieć 100 000 wierzchołków i każdy z nich dokładnie 20 sąsiadów.

_13th_Dragon

2012-12-23T03:43:42+01:00

Rejestracja: dni
Ostatnio: dni

1

Kopiuj

#include <ctime>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;

const size_t V=20;
const size_t E=4;
 
int main()
  {
   size_t VE=V*E;
   if((VE)&1) cout<<"Imposible"<<endl;
   else
     {
      srand(time(0));
      bool graph[V][V]={false};
      unsigned filled[V]={0};
      VE>>=1;
      while(VE)
        {
         size_t a=rand()%V,b=rand()%V;
         if((a!=b)&&(!graph[a][b])&&(filled[a]<E)&&(filled[b]<E))
           {
            graph[a][b]=graph[b][a]=true;
            ++filled[a];
            ++filled[b];
            --VE;
           }
        }
      for(size_t y=0;y<V;++y)
        {
         unsigned e=0;
         for(size_t x=0;x<V;++x)
           {
            cout<<graph[y][x]<<' ';
            e+=graph[y][x];
           }
         cout<<e<<endl;
        }
      for(size_t x=0;x<V;++x)
        {
         unsigned e=0;
         for(size_t y=0;y<V;++y) e+=graph[y][x];
         cout<<e<<' ';
        }
      cout<<endl;
     }
   cin.sync(); cin.get();
   return 0;
  }