Witamy na forum PC Format Zapraszamy do REJESTRACJI


Użytkownicy przeglądający ten wątek: 1 gości

Grafy w C++

#1
Grafy w C++
Mam zrobić w C++ grafy. Jestem kompletnie w tym zielona i potrzebuje pomocy.
Mam zrobić:
1) Możliwość zdefiniowania dowolnego grafu (skierowanego)
2) Sprawdzenie spójności grafu (metodę wszerz i wgłąb)
3) Obliczenie stopnia grafu
4) Rysowanie grafu
5) Drag & Drop (zmiana postaci grafu) <- opcjonalnie
Mam zrobiony kod, ale metody i stopień grafu zawiera błędy.
Kod:
#include <iostream>
#include <windows.h>
#include "graf.h"
using namespace std;



int main()
{
    graf mojg;//robisz swoj graf
    int n;//ilosc wiszcholkow wybranych przed kogos
    bool tak = false;
    while (tak == false)
    {
          system("CLS");
    cout << "Ilosc wierzcholkow ? : ";
    cin >> n;
    cout << endl;
    if(n > mojg.maxn)
    {
         cout << "ZA DUZO MAX 100 " << endl;
         Sleep(1000);
         }
         else
         {
             mojg.n = n;
             tak = true;
             }
}


int zwN = n + 1;

mojg.Tworz(zwN);

system("CLS");
int wybor;
int x=1;
while(x ==1)
{
system("CLS");
cout << " _____________________________________" << endl;
cout << "|1.Przedstaw graf w postaci macierzy  |" << endl;
cout << "|2.Sprawdz graf metoda wszerz         |"<<endl;
cout << "|3.Sprawdz graf metoda w glab         |"<<endl;
cout << "|4.Sprawdz stopien grafu              |"<<endl;
cout << "|5.Dodaj krawedz                      |"<<endl;
cout << "|6.Usun krawedz                       |"<<endl;
cout << "|7.Dodaj wierzcholek                   |"<<endl;
cout << "|8.Usun OSTATNI wierzcholek            |"<<endl;
cout << "|9.Rysuj graf                         |"<<endl;
cout << "|0.Wyjdz                              |"<< endl;
cout << "|_____________________________________|"<<endl;
cout << "Wybor : " ;
cin >> wybor;
switch(wybor)
{
     case 1:
          /*
          
          MACIERZ
          
          
          */
         mojg.Pokaz();
          
          
        break;
        
        
        case 2:
             system("CLS");
             int pktw;
             cout << "podaj punkt wyjscia : ";
             cin >> pktw;
             cout << endl;
             mojg.sprWszerz(pktw);
              cout << endl;
              system("PAUSE");
        break;
            
        case 3:
             system("CLS");
             int pktw2;
             cout << "podaj punkt wyjscia : ";
             cin >> pktw2;
             cout << endl;
             mojg.sprWglab(pktw2);
              cout << endl;
              system("PAUSE");
        break;
        
         case 4:
             system("CLS");
            
             cout << endl;
             mojg.stopien();
              cout << endl;
              system("PAUSE");
        break;
        
           case 5:
             system("CLS");
            
             cout << endl;
             mojg.dodajKR();
              cout << endl;
              system("PAUSE");
        break;
         case 6:
             system("CLS");
            
             cout << endl;
             mojg.usunKR();
              cout << endl;
              system("PAUSE");
        break;
        
           case 7:
             system("CLS");
            
             cout << endl;
             mojg.dodajWI();
              cout << endl;
              system("PAUSE");
        break;
        
          case 8:
             system("CLS");
            
             cout << endl;
             mojg.n--;
              cout << endl;
              system("PAUSE");
        break;
          case 9:
             system("CLS");
            
             cout << endl;
             mojg.rysuj();
              cout << endl;
              system("PAUSE");
        break;
        case 0:
             x++;
             break;
             default:
                    
                    
               system("CLS");
                     break;    
            
             }//koniec switch wybor
             }//while
return 0;
}



class graf
{
    public:  
      void sprWszerz(int start);
  void sprWglab(int start);
      int n; // liczba wieszcholkow
      int m; //liczba krawedzi
      static const int maxn = 100;// max ilosc
      bool g[maxn][maxn]; // talbica przedstawiajaca co sie dzieje wgrafie
void stopien();
      int v[maxn];
     void Tworz(int n);
     void Pokaz();
     void dodajKR();
     void dodajWI();
     void usunKR();
     void rysuj();
      };


#include "graf.h"
#include <stdio.h>
#include <iostream>
#include <windows.h>
#include <vector>
using namespace std;
void graf::sprWszerz(int start)// sprawdzanie spójności wszerz :)
{
              for(int i = 1 ; i < n+1 ; i++)
      {
               v[i] = 0;
              
              }//for i dla v
     bool all= false;//bool na to czy wszystkie były sprawdzone
         for(int i = 1 ; i < n+1 ; i++)
      {
              if(g[start][i] == true) v[i] = 1;//szukamy jakie punkty są od punktu zaczęcia
      
              }//for i dla punktu zaczęcia
      v[start] = 2;
  
    while(!all)
    {
// spr czy da się przejść dalej od punktu
int pkt = 0;
         for(int i = 1 ; i < n+1 ; i++)//szukamy najbliższego punktu
      {
            
       if(v[i] == 1)
       {
        pkt = i;
        i = n+2;
        }
              }//koniec szukania
      for(int i = 1 ; i < n+1 ; i++)
      {
              if(g[pkt][i] == true) v[i] = 1;//dla kolejnych punktów szukamy
      
              }
      v[pkt]=2;
            int ilosc = 0;// do spr czy są pkt bez krawędzi
        for(int i = 1 ; i < n+1 ; i++)
      {
                
      if(v[i] != 2 && v[i] != 1) ilosc++;
      if(i == n & ilosc == 0)
      {
      all = true;
      cout << "jest spojnosc " << endl;
      }
              }
              if(ilosc != 0)
              {
                       all = true;
                       cout << "NIE MA SPOJNOSCI!!! " << endl;
                       }
     }//while
    
     }//całość
  

void graf::Tworz(int n)
{
     int wybor;

     for(int i = 1 ; i < n ; i++)
     {
      for(int j = 1 ; j < n ; j++)
     {
             if(i != j)
             {
                  Sleep(1000);
                  system("CLS");
                  cout << "wierzcholek [" << i <<"] do wierzcholka [" << j << "] stworzyc krawedz (1) ? nie stworzyc(0) : ";
                  cin >> wybor;
                  switch(wybor)
                  {
                      case 1 :
                           g[i][j] = true;        
                    
                      
                           break;
                
                        
                      case 0 :
                           g[i][j] = false;        
                        
                            
                           break  ;
                      default:  
                               cout << endl << "ZŁY WYBÓR!!!" << endl;
                               j--;
                               Sleep(1000);
                               break;
                                      
                               }//koniec switch wybór
                  }//koniec i != j
             else
             {
                 g[i][j] = false;
                 }
            
              }//koniec for j
            
           }//koniec for i
    
     }// koniec TWÓRZ
    
    
    
    
    
    
    
    
    
    
    
    
    
     void graf::Pokaz()
{
     system("CLS");
      cout <<"0 - brak krawedzi \t 1 - krawedz" << endl;
          cout << "   " ;
          for(int i=0 ; i < n+1 ; i++)
          {
           for(int j=1 ; j < n+1 ; j++)
          {
          if(i == 0)
          {
      
          cout <<"|"<< j << "|" ;
          }//wyjątek tworzenie liczb
          else
          {
          if(j == 1)
          {
               cout << endl << "|" << i  << "|";//nowa linijka
               }
      
                      if(g[i][j] == true )
             {
                              cout << "  " << "1";
                              }                    
                        if(g[i][j] == false )
             {
                              cout << "  " << "0";
                              }    
                              }//else
          }//koniec for j
            }//koniec for i
            cout << endl;
            system("PAUSE");
          
    
    
     }//koniec pokaz

void graf::sprWglab(int start)// sprawdzanie spójności w głąb :)
{
      
              for(int i = 1 ; i < n+1 ; i++)
      {
               v[i] = 0;
              
              }//for i dla v
               v[start] = 2;
     bool all= false;//bool na to czy wszystkie były sprawdzone
         for(int i = 1 ; i < n+1 ; i++)
      {
              if(g[start][i] == true) v[i] = 1;//szukamy jakie punkty sa od punktu zaczęcia
      
              }//for i dla punktu zaczęcia
              vector<int> tab;//tablica z ostatnimi punktami
              tab.push_back(start);
              int pkt;
                    for(int i = 1 ; i < n+1 ; i++)//szukamy najbliszego punktu
      {
            
       if(v[i] == 1)
       {
        pkt = i;
        i = n+2;
        }
              }//koniec szukania
                  while(!all)
    {
// spr czy da się przejść dalej od punktu

  
            
      for(int i = 1 ; i < n+1 ; i++)//szukamy najbliszego punktu
      {
            
       if(v[i] == 0 && g[pkt][i])
       {
        pkt = i;
        v[i] =1;
        i = n+2;
        }
        if(i == n)
        {
             v[pkt]=2;
            
             tab.pop_back();
             pkt = tab.back();
             }
              }//koniec szukania
              
                int ilosc = 0;// do spr czy są pkt bez krawędzi
        for(int i = 1 ; i < n+1 ; i++)
      {
              
              if(v[i] != 2 && v[i] != 1) ilosc++;
      if(i == n & ilosc == 0)
      {
      all = true;
      cout << "jest spojnosc" << endl;
      }
              }
              if(ilosc != 0)
              {
                       all = true;
                       cout << "NIE MA SPOJNOSCI" << endl;
                       }
    
     }//while
    
              
              
              }//koniec funkcji
              
              
              
              
              
              
              
              
              
              
              
              
              
              
              
              
              
              
              void graf::stopien()
              {
                  
      
              for(int i = 1 ; i < n+1 ; i++)
      {
               v[i] = 0;
              
              }//for i dla v
               v[1] = 2;
     bool all= false;//bool na to czy wszystkie były sprawdzone
         for(int i = 1 ; i < n+1 ; i++)
      {
              if(g[1][i] == true) v[i] = 1;//szukamy jakie punkty są od punktu zaczęcia
      
              }//for i dla punktu zaczęcia
              
                 vector<int> tab;//tablica z ostatnimi punktami
               int jeden = 1;
              tab.push_back(jeden);
              int pkt ;
              int szer = 2;
              int calosc = 1;
                for(int i = 1 ; i < n+1 ; i++)//szukamy najbliższego punktu
      {
            
       if(v[i] == 1)
       {
        pkt = i;
        i = n+2;
        }
        }
     while(!all)
     {
  
                      
      for(int i = 1 ; i < n+1 ; i++)//szukamy najbliższego punktu
      {
            
       if(v[i] == 0 && g[pkt][i])
       {
        pkt = i;
        v[i] =1;
        szer++;
        if(calosc < szer) calosc = szer;
        i = n+2;
        }
        if(i == n)
        {
             v[pkt]=2;
             szer--;
             tab.pop_back();
             pkt = tab.back();
             }
              }//koniec szukania
              
                int ilosc = 0;// do spr czy są pkt bez krawędzi
        for(int i = 1 ; i < n+1 ; i++)
      {
              
              if(v[i] != 2 && v[i] != 1) ilosc++;
      if(i == n & ilosc == 0)
      {
      all = true;
      cout << "najszerzej :" << calosc << endl;
      }
              }
          
                    
                       }//while !all
                      
                   }//koniec stopień
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                  
                   void graf::dodajKR()
                   {
                       system("CLS");
                        int a,b;
                   cout << "Wierzcholek A : " ;
                   cin >> a;
                   cout << endl << "Wierzcholek B : ";
                   cin>>b;
                   if(g[a][b] == true) cout << endl << "Krawedz już istnieje";
                   else
                   {
                       g[a][b] = true;
                       cout << endl << "Dodano krawedz" <<endl;
                       }
                       }
                        
                   void graf::dodajWI()
                   {
                       system("CLS");
                    
                  
                           n++;
                           cout << endl <<"Dodano wierzcholek" << endl;
                      
                       }
                      
                      
                      
                       void graf::usunKR()
                       {
                            system("CLS");
                        int a,b;
                   cout << "Wierzcholek A : " ;
                   cin >> a;
                   cout << endl << "Wierzcholek B : ";
                   cin>>b;
                   if(g[a][b] ==false) cout << endl << "Krawedz nie istnieje";
                   else
                   {
                       g[a][b] = false;
                       cout << endl << "usunieto krawedz" <<endl;
                       }
                            
                            }//koniec usuń kr
                            
                            
                            
                            void graf::rysuj()
                            {
                                 bool koniec = false;
                                 for(int i = 1 ; i <n+1 ;i++)
                                 {
                                              
                                cout << "wierzcholek  " << i << " ma krawedzi z :" <<endl;
                                for(int j = 1 ; j <n+1 ;j++)
                                 {
                                if(g[i][j] == true) cout <<"-"<< j << "- " ;
                                }//koniec for
                                cout << endl << endl;
                                 }//koniec for i
                                 }//koniec funkcji
89% graczy uważa że najważniejsza jest grafika jeśli należysz do tych 11% wklej to do podpisu.
 System operacyjny: windows_vista Przeglądarka: firefox
 Reklamy Google
Programy: Polecane / Nowe / Inne



Wiadomości w tym wątku (Grafy w C++)
Grafy w C++ - Wilczyca89 - 11.08.2011, 12:07
RE: Grafy w C++ - wojtekwn - 12.08.2011, 16:59
RE: Grafy w C++ - Wilczyca89 - 16.08.2011, 11:15
RE: Grafy w C++ - izi - 16.08.2011, 14:47
RE: Grafy w C++ - Wilczyca89 - 23.08.2011, 14:53


Podobne wątki (Grafy w C++)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  C++ Builder 6 Grafy Wilczyca89 3 3164 27.05.2011, 17:05
Ostatni post: Szachista
  grafy assimar 3 1559 20.02.2007, 20:40
Ostatni post: assimar

Skocz do:


Wybrane wątki (Grafy w C++)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  VBA excel dmjs 6 7921 17.04.2019 10:20
Ostatni post: ptrick
  C++ - sens pogłębiania nauki gbr 5 7825 25.03.2019 12:53
Ostatni post: koneton
  Klasa wewnętrzna w C++ Physicist 4 7460 23.03.2019 18:28
Ostatni post: Physicist
  Ruby on Rails - tutoriale luciussulla 0 6614 23.03.2019 16:49
Ostatni post: luciussulla
Big Grin Czy dostane sie technikum informatycznego klaudiusz20046 6 9794 21.03.2019 01:28
Ostatni post: UnableToSee
  [C#] Program do moderacji czatów gier wiktrom12 0 7028 07.03.2019 15:33
Ostatni post: wiktrom12
  Mój pierwszy projekt - Pomoc rafal12999 1 7499 07.02.2019 22:01
Ostatni post: Szachista
  pomoc projekt scilab piesel18 2 8913 04.02.2019 09:03
Ostatni post: piesel18
  Szkoła Informatyczna Zikinan 1 7781 02.02.2019 17:59
Ostatni post: wojownikhaha
  [Java] Strona z zadaniami do rozwiązania i odpowiedziami rafal12999 2 8503 27.01.2019 13:44
Ostatni post: rafal12999
  kompilacja biblioteki Agui - cmake jurek2 0 7797 10.01.2019 13:12
Ostatni post: jurek2
  Zamiana całego zestawu znaków wg przyporządkowania BarHorab 5 8481 19.12.2018 16:45
Ostatni post: Szachista
  Sumowanie licz excel - problem OxyGenE 2 11205 19.12.2018 16:29
Ostatni post: Szachista
  Jaki kod pod pewne zdarzenia visualbasic 2010 aktywny27 4 8989 07.11.2018 13:41
Ostatni post: Ajgor
Scared Ipad Pro programowanie? NissmoOne 4 9990 06.10.2018 12:22
Ostatni post: NissmoOne