kburnik

C++ - Zadatak Graf - rjesenje

Jan 8th, 2013
72
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3. Pripreme 2013 - C++ radionica
  4.  
  5. TEMA : Obilazak grafa (najkraci putevi izmedju dva cvora)
  6.  
  7. Zadatak: Graf
  8.  
  9. Autor zadatka: Kristijan Burnik
  10.  
  11. Autor rjesenja: Kristijan Burnik
  12.  
  13. Datum rjesavanja: 2013-01-08
  14.  
  15. */
  16. #include <iostream>
  17. #include <cstdlib>
  18. #include <vector>
  19. #include <map>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. // koliko je najdulja putanja?
  25. const int MAX_PATH_LENGTH = 1000;
  26.  
  27. typedef string node;
  28. typedef vector< node > nodelist;
  29. typedef set< node > nodeset;
  30. typedef map< node,bool >::iterator IT;
  31.  
  32.  
  33. // struktura za pohranu grafa (korisna za listu susjeda od nekog cvora)
  34. map <node, map< node,bool> > graph;
  35.  
  36. // putanja do cvora
  37. nodelist path;
  38.  
  39. // popis vidjenih cvorova
  40. set <node> seen;
  41.  
  42. // minimalna izracunata duljina putanje
  43. int minPathLength = MAX_PATH_LENGTH;
  44.  
  45. // popis svih putanja (rezultati pretrage)
  46. // rezultate puni DFS
  47. vector < nodelist > results;
  48.  
  49. // pomocna procedura za prikaz pojedinog rezultata (jedne putanje)
  50. void display( nodelist v ) {    
  51.     cout << v[0];
  52.     for (int i = 1; i < v.size(); i++) {
  53.         cout << " -> " << v[i];
  54.     }
  55.     cout << endl;    
  56. }
  57.  
  58. // obilazak grafa
  59. // ( koristimo reference za ustedu vremena kopiranja i funkcijskog stoga )
  60. void traverse( node current , node end ) {
  61.    
  62.     // postavi trenutni cvor u listu (putanju)
  63.     path.push_back( current );
  64.    
  65.     // oznaci da je trenutni cvor vidjen
  66.     seen.insert( current );
  67.    
  68.     // provjeri jesmo li dosli do odredisnog cvora
  69.     if (current == end) {
  70.         // ako je izracunata putanja manja, isprazni rezultate
  71.         if ( path.size() < minPathLength ) {
  72.             minPathLength = path.size();  
  73.             results.clear();  
  74.         }
  75.         // puni rezultate samo za jednake duljine putanje
  76.         if ( path.size() == minPathLength) {
  77.             results.push_back( path );
  78.         }
  79.        
  80.     } else {
  81.         // uzmi susjede od zadanog cvora
  82.         map<node,bool> adjacents = graph[ current ];
  83.    
  84.         // prodji sve susjedne cvorove od trenutnog
  85.         for (IT it = adjacents.begin(); it != adjacents.end(); it++ ) {
  86.             node nextnode = it->first;
  87.             // samo jos nevidjene cvorove obradjujemo
  88.             if (!seen.count(nextnode)) {
  89.                
  90.                 // oznaci da je cvor vidjen
  91.                 seen.insert( nextnode );
  92.  
  93.                 // nastavi obilazak na iducem cvoru,
  94.                 // proslijedi trenutnu putanju i popis vidjenih
  95.                 traverse( nextnode , end );
  96.                
  97.                 // makni iz popisa vidjenih
  98.                 seen.erase( nextnode );
  99.             }
  100.         }
  101.     }
  102.    
  103.     // makni trenutni cvor sa putanje
  104.     path.pop_back();
  105.    
  106.     // makni trenutni cvor iz popisa vidjenih
  107.     seen.erase( current );
  108.    
  109. }
  110.  
  111. // procedura za pripremu i poziv obilaska (traverse)
  112. void findpaths( node a, node b ) {
  113.     // ocisti rezultate pretrage
  114.     results.clear();
  115.    
  116.     // postavi minimalnu putanju na maksimalnu mogucu
  117.     minPathLength = MAX_PATH_LENGTH;
  118.    
  119.     // isprazni putanju i popis vidjenih
  120.     nodelist path;
  121.     nodeset seen;
  122.    
  123.     // pozovi dfs za pretragu putanje a -> ... -> b
  124.     // sa praznom putanjom i praznim skupom vidjenih cvorova
  125.     traverse( a , b );  
  126. }
  127.  
  128. int main() {
  129.     int n ,k;
  130.    
  131.     // koliko imamo bridova?
  132.     cin >> n;
  133.    
  134.     // unesi i konstruiraj graf
  135.     node a,b;
  136.     for (int i = 0 ; i < n; i++) {
  137.         cin >> a >> b;
  138.         graph[a][b] = graph[b][a] = true;
  139.     }
  140.    
  141.     // koliko imamo upita za pretragu?
  142.     cin >> k;
  143.  
  144.     // obradi sve upite
  145.     for (int i = 0; i < k; i++) {
  146.        
  147.         // unesi par cvorova (ciju putanju trazimo ?)
  148.         cin >> a >> b;
  149.  
  150.         // pronadji sve najkrace puteve
  151.         // rezulti spremljeni globalno u "results"
  152.         findpaths(a,b);
  153.        
  154.         // ako nema rezultata ispisi da nema puta
  155.         if (results.size() > 0) {
  156.             // ispisi sve rezultate koje je generirao DFS
  157.             for (int i = 0 ; i < results.size(); i++)  {    
  158.                 display( results[i] );
  159.             }
  160.         } else {
  161.             cout << "Nema puta" << endl ;
  162.         }
  163.        
  164.     }
  165.  
  166.     system("pause");
  167.     return 0;
  168. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×