problem z DFS'em: nie zatrzymuje mi sie

Odpowiedz Nowy wątek
lexus00
2010-06-08 19:19
lexus00
0

nie wiem czemu zawiesza mi program jak uruchamiam funkcje DFS

//DFS 
#include<iostream>
#include<vector>

using namespace std;
vector <int> tab[21]; // tablicw sąsiadów każdego wierzchołka
vector<char> kolor;

void DFS(int u);
int war;
//***********
main()
{
int n,m,wyb=0,od,do_;
cout<<"ile wierzcholkow ma miec graf (max 20): ";
cin>>n;
cout<<"ile krawedzi ma miec graf (max "<<(n*(n-3))/2+n<<" ): ";
cin>>m; 
system("cls");
for(int i=0;i<m;i++)
        {
            int a,b;
            wyz:;
            cout<<"podaj krance krwedzi : ";
            cin>>a;
            cin>>b;
            if((a>n)or(b>n))
            {
            cout<<"\n podany nr. wierzcholka jest niewlasciwy, podaj jego nr. ponownie";
            goto wyz;
            }
            tab[a].push_back(b);  
            tab[b].push_back(a);    
            if(!(i%10)){ system("cls"); }
        }
system("cls");
do{
cout<<"menu\n1-wypisz opis grafu\n2-czy istnieje droga miedzy dwoma wierzcholkami?\n"
    <<"3-czy podany graf jest spojny?\n"
    <<"4-koniec"<<endl;
cin>>wyb  ;
system("cls");
switch(wyb)
{
  case 1: {          
                 for(int i=1;i<=n;i++)
                     {    
                       cout<<"\nwierzcholek  "<<i<<" jest polonczony z: ";       

                       for(int j=0;j<tab[i].size();j++)   
                        {                             
                         cout<<tab[i][j]<<" ";
                        }
                     }
                 cout<<endl;
                 system("pause");                
                 system("cls");
                 break;
        }
  case 2:{       int odp=0,wybor=1;
                 cout<<"od ktorego wierzcholka chcesz zaczac??\n";
                 cin>>od;
                 cout<<"a do jakiego wierzchołka chcesz dojsc??\n";
                 cin>>do_;
                 DFS(od);
                 if(odp==1){cout<<"istniej droda z wierzcholka "<<od<<" do wierzcholka "<<do_;}
                 else{cout<<"nie istniej droda z wierzcholka "<<od<<" do wierzcholka "<<do_; }                 
                 break;
         }
  case 3:{

                /*    int odp;
                    do_=0;
                  //  spojny=1;
                   // odp=DFS(tab,ilosc,od,do_,spojny,kol);
                    if(odp==0)
                       {
                              cout<<"graf jest niespojny\n";
                              system("pause");                
                              system("cls");
                       }
                    else{
                              cout<<"graf jest spojny\n";
                              system("pause");                
                              system("cls");
                        }
                   */ 
                    break;
         }
}
}while(wyb!=4);

}
//******************

void DFS(int u)   // DFS - przeglądanie grafu w głąb
{
  kolor[u]=1;     
  int v,s=tab[u].size();
  for(int i=0;i<s;i++) 
  {
    v = tab[u][i];    
    if(kolor[v]==0){ DFS(v); }
  } 
}
<\cpp>

Pozostało 580 znaków

2010-06-09 16:35

Rejestracja: 11 lat temu

Ostatnio: 7 lat temu

0

Nigdzie nie zwiększasz rozmiaru vectora kolor(zamiast niego możesz użyć zwykłej tablicy). Dodatkowo jeszcze źle jest sprawdzanie czy istnieje połączenie między dwoma wierzchołkami. Wystarczy, że sprawdzisz kolor wierzchołka docelowego.

Pozostało 580 znaków

lexus00
2010-06-09 17:21
lexus00
0

dzięki Ci wielkie. właśnie tak myślałem że funkcja odwołuje się do nieistniejącego elementu ale ze mam minimalne pojęcie o wektorach to nie przyszło mi do głowy że to jest od tego że ten wektor jest za mały
jeszcze raz dzięki

Pozostało 580 znaków

lexus00
2010-06-09 17:33
lexus00
0

mam jeszcze taka proźbe mógłbyś mi powiedzieć jak zrobić to żeby wyznaczało najkrótsza drogę między 2 wierzchołkami

Pozostało 580 znaków

2010-06-09 21:19

Rejestracja: 11 lat temu

Ostatnio: 7 lat temu

0

Najkrótszą drogę czy stwierdzało czy istnieje droga między wierzchołkami? Najkrótszą DFS'em to może być problem.

Pozostało 580 znaków

lexus00
2010-06-09 21:34
lexus00
0

to nic będzie bez .

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0