problem z DFS'em: nie zatrzymuje mi sie

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>
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.

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

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

0

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

0

to nic będzie bez .

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