Kommivoyajer masalasi reja: Algoritmlarini o'rganish, chuqurlik va eni bo'yicha aylanib o'tuvchi graflar

Turlar nazariyasida shaharlar ruyhati bir shahardan boshlab va o’sha shaharga barcha qolgan shaharlarni bir martadan o’tib qaytib kelish jarayonini belgilaydi. Bunday o’tishni marshrut deb ta’riflaymiz. Marshrut narxi chiziqlar ustidagi qiymatlar yig’indisi bilan aniqlanadi.

• 
  Turlar nazariyasida shaharlar ruyhati bir shahardan boshlab va o’sha shaharga barcha qolgan shaharlarni bir martadan o’tib qaytib kelish jarayonini belgilaydi. Bunday o’tishni marshrut deb ta’riflaymiz. Marshrut narxi chiziqlar ustidagi qiymatlar yig’indisi bilan aniqlanadi.
  
• 
  Rasm 2 algoritm GTS bo’yicha K marshrutni shahar1 dan boshlab tuzishni aks ettiradi.
  

rasm 2 algaritm qadamlari

Masalaning quyilishi: berilgan n = 4, e = 6 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3 grafning 2 uchidan boshlab chuqurligini aniqlash;

• 
  Masalaning quyilishi: berilgan n = 4, e = 6 2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3 grafning 2 uchidan boshlab chuqurligini aniqlash;
  
• 
  Dastur kodi:#include
  
• 
  using namespace std;
  
• 
  class Graph
  
• 
  {
  
• 
  int V; list *adj;
  
• 
  void DFSUtil(int v, bool visited[]);
  
• 
  public:
  
• 
  Graph(int V); // Constructor
  
• 
  // function to add an edge to graph
  
• 
  void addEdge(int v, int w);
  
• 
  void DFS(int v);
  
• 
  };
  
• 
  Graph::Graph(int V){ this->V = V;
  
• 
  adj = new list[V];
  
• 
  } void Graph::addEdge(int v, int w){ adj[v].push_back(w);} void Graph::DFSUtil(int v, bool visited[]){ visited[v] = true;cout << v << " ";
  
• 
  list::iterator i;
  
• 
  for (i = adj[v].begin(); i != adj[v].end(); ++i)
  
• 
  if (!visited[*i])
  
• 
  DFSUtil(*i, visited);
  
• 
  }