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 3260 27.05.2011, 17:05
Ostatni post: Szachista
  grafy assimar 3 1691 20.02.2007, 20:40
Ostatni post: assimar

Skocz do:


Wybrane wątki (Grafy w C++)
Wątek: Autor Odpowiedzi: Wyświetleń: Ostatni post
Ściana Klika pytań plz pomóżcie Samek2222 1 4951 22.03.2020 18:59
Ostatni post: Ajgor
  Pytanie - programowanie batch [cmd] Max23 0 4902 20.03.2020 01:03
Ostatni post: Max23
  Oczekiwanie na Akcje przycisku wanhelsing 8 7011 01.03.2020 19:44
Ostatni post: Szachista
Toungue Wybór szkoły średniej przez potencjalnego programistę Zikinan 1 6677 09.02.2020 15:58
Ostatni post: dzikuu86
  Poszukuję pomysłu na prosty program ;) janciu96 5 16163 13.12.2019 23:32
Ostatni post: Ajgor
  Programowanie Batch (CMD) Informatyk2019 0 7420 11.12.2019 18:30
Ostatni post: Informatyk2019
  [JavaScript] Znajdowanie przedziału czasu rafal12999 0 3410 10.12.2019 17:58
Ostatni post: rafal12999
  Przekazywanie wskaźnika przez referencję w Qt Trojan3000 3 15483 10.12.2019 13:16
Ostatni post: Ajgor
  Proszę o pomoc w uzupełnieniu ankiety dt. Zawodu Programisty MaleMonki 0 3883 17.11.2019 12:47
Ostatni post: MaleMonki
  Spring framework – jakie strony polecacie do nauki? olek23 5 9258 15.11.2019 15:57
Ostatni post: Alsenas
  Programowanie windy (problem) w C++ mysza2323 2 8534 06.11.2019 23:04
Ostatni post: mysza2323
  Programy w C ~Anonim 1 8765 22.10.2019 17:48
Ostatni post: Szachista
  Wyświetlanie informacji z bazy danych na stronie www PitPlay 1 9274 16.09.2019 11:18
Ostatni post: Ajgor
  Błąd przy uruchamianiu programu w Java z wiersza poleceń Physicist 3 4719 30.08.2019 14:16
Ostatni post: Physicist
  Python z wiersza poleceń Physicist 15 24896 21.08.2019 20:14
Ostatni post: Physicist