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
#2
RE: Grafy w C++
Stopień grafu to maksyalny stopień wierzchołka w grafie.
Możesz zatem to zrobić tak.

Kod:
void graf::stopien() {
    int * r = new int[n];
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            r[i] += g[j][i] || g[i][j];

    int deg = 0;
    for (int i=0;i<n;i++)
        deg = ( r[i] > deg ? r[i] : deg );

    delete r;    
    std::cout << deg << std::endl;
}

Co do reszty, to nie wiem w czym tkwi problem. Nie chciało mi się przedzierać przez kod ;)

Czy zadaniem Twoim było wykorzystywanie macierzy sąsiedztwa? Do takiego zadania nie byłby to mój pierwszy wybór. Wszystkie metody byłyby łatwiejsze do zaimplementowania gdybyś osobno trzymała krawędzie i wierzchołki w wektorach/listach.
 System operacyjny: macos Przeglądarka: safari
#3
RE: Grafy w C++
Szczerzę mówiąc znalazłam tylko listowe i macierzowe. Nie wiem jakie inne jeszcze są. Po prostu nie udało mi się znaleźć tych metod przedtem i znalazłam niezbyt dobre i muszę te metody przerobić. Po za tym pokazuje mi, że jest spójność choć nie powinno.
http://docs7.chomikuj.pl/316405106,0,1,1...wania..doc
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
#4
RE: Grafy w C++
Sposoby reprezentacji grafów masz tu: http://www.algorytm.org/klasyczne/grafy-...tacje.html
Dyskusja o FAQ i propozycje zmian w dziale "Programowanie": http://forum.pcformat.pl/Przeczytaj-zani...emat-FAQ-t
 System operacyjny: windows_vista Przeglądarka: firefox
#5
RE: Grafy w C++
Potrzebuje kogoś kto mi w tych metodach pomoże, bo nie wiem jak mam przerobić te metody by działały. Jeśli uznam za stosowne to zmienię reprezentacje grafu, ale ta reprezentacja nie jest taka ważna co te metody. A wracając do stopnia grafu co napisałeś w przestrzeni nazw std. Nie wiadomo dlaczego, gdy piszę właśnie w ten sposób, program mi nic nie wyświetla. Kompiluje się poprawnie, nie ma błędów, ale okienko otwiera się na kilka sekund i nie nadążam ni zobaczyć. Nie powinno czegoś takiego być.
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
Programy: Polecane / Nowe / Inne



Użytkownicy forum szukali:
grafy c++graf c++c++ grafyc++ jak utworzyc grafgraf w cgraf w postaci macierzy sąsiedztwa c++

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

Skocz do:


Wybrane wątki (Grafy w C++)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
  Proszę o pomoc w uzupełnieniu ankiety dt. Zawodu Programisty MaleMonki 0 505 17.11.2019 12:47
Ostatni post: MaleMonki
  Spring framework – jakie strony polecacie do nauki? olek23 5 2450 15.11.2019 15:57
Ostatni post: Alsenas
  Programowanie windy (problem) w C++ mysza2323 2 1106 06.11.2019 23:04
Ostatni post: mysza2323
  Programy w C ~Anonim 1 1587 22.10.2019 17:48
Ostatni post: Szachista
  Książki do nauki C# olek23 14 7764 17.10.2019 13:06
Ostatni post: Ajgor
  Wyświetlanie informacji z bazy danych na stronie www PitPlay 1 2546 16.09.2019 11:18
Ostatni post: Ajgor
  Błąd przy uruchamianiu programu w Java z wiersza poleceń Physicist 3 1950 30.08.2019 14:16
Ostatni post: Physicist
  Python z wiersza poleceń Physicist 15 9888 21.08.2019 20:14
Ostatni post: Physicist
  Transfer plików via FTP Visual Basic FireBytes 3 4991 15.08.2019 07:41
Ostatni post: Szachista
  Menu wysuwane z boku patryk67 1 3370 07.08.2019 12:43
Ostatni post: aht
  Visual Basic Excel l.całkowitą przedstawić w postaci szesnastkowej fugaz 4 4952 18.06.2019 21:36
Ostatni post: fugaz
  Nauka do Olimpiady Informatycznej? piotr0905 1 4909 08.06.2019 16:50
Ostatni post: wlisik
Ściana Prosta gra w Builder C++ Kiranek1 1 4847 31.05.2019 15:20
Ostatni post: Szachista
  Menu (Nie widoczne długie opisy) wanhelsing 5 6627 28.04.2019 19:31
Ostatni post: koneton
  Skrypt usuwający pliki sylwiaa1 2 2927 28.04.2019 15:20
Ostatni post: sylwiaa1