พิมพ์ DFS ที่เล็กที่สุดในพจนานุกรมศัพท์ของกราฟเริ่มต้นจาก 1 ในโปรแกรม C

เราจะได้กราฟที่เชื่อมต่อกับจุดยอด N และขอบ M ดังนั้นเราจึงต้องพิมพ์ DFS ที่เล็กที่สุดของกราฟโดยเริ่มจาก 1

จุดยอดควรมีหมายเลขตั้งแต่ 1 ถึง N

ตัวอย่าง

Input: N = 5 M =5
   edge(1, 4, arr)
   edge(3, 4, arr)
   edge(5, 4, arr)
   edge(3, 2, arr)
   edge(1, 5, arr)
   edge(1, 2, arr)
   edge(3, 5, arr)
   edge(1, 3, arr)
output: 1 2 3 4 5

แทนที่จะทำ DFS ปกติ อันดับแรก เราจะจัดเรียงขอบที่เกี่ยวข้องกับจุดยอดแต่ละจุด เพื่อให้ในแต่ละรอบเลือกเฉพาะขอบที่เล็กที่สุดก่อน หลังจากการจัดเรียง ให้ดำเนินการ DFS ปกติซึ่งจะทำให้การข้ามผ่าน DFS ที่เล็กที่สุดตามพจนานุกรมศัพท์

รับด้านล่างคือการใช้ C ++ ของอัลกอริทึมที่ระบุด้านล่าง

อัลกอริทึม

Start
Step 1 -> Declare Function void lexo(vector<int>* arr, int n)
   Declare bool check[n + 1] = { 0 }
   Loop For int i=0 and i<n and i++
      Call sort(arr[i].begin(), arr[i].end())
      Loop For int i = 1 and i < n and i++
         IF !check[i]
            Call graph(arr, i, n, check)
      End
   End
Step 2 -> declare Function void edge(int u, int v, vector<int>* arr)
   Call ar[u].push_back(v)
   Call ar[v].push_back(u)
Step 3 -> Declare function void graph(vector<int>* arr, int src, int n,bool* check) print src
   Set check[src] = true
   Loop for int i = 0 and i < arr[src].size() and i++
      IF !check[arr[src][i]]
         Call graph(arr, arr[src][i], n, check)
      End
   End
Step 4- > In main()
   Declare int n = 5, m = 5
   Use STL vector<int> arr[n + 1]
   Call edges(1,4, arr)
   Call edges(3,4, arr)....
   Call lexo(arr, n)
Stop

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
//for inserting an edge
void edge(int u, int v, vector<int>* arr){
   arr[u].push_back(v);
   arr[v].push_back(u);
}
// Function for dfs graph traversal
void graph(vector<int>* arr, int src, int n,bool* check){
   cout << src << " ";
   check[src] = true;
   for (int i = 0; i < arr[src].size(); i++){
      if (!check[arr[src][i]])
         graph(arr, arr[src][i], n, check);
   }
}
void lexo(vector<int>* arr, int n){
   bool check[n + 1] = { 0 };
   for (int i = 0; i < n; i++)
      sort(arr[i].begin(), arr[i].end());
   for (int i = 1; i < n; i++){
      if (!check[i])
      graph(arr, i, n, check);
   }
}
int main(){
   int n = 5, m = 5;
   vector<int> arr[n + 1];
   // for inserting an edge
   edge(1, 4, arr);
   edge(3, 4, arr);
   edge(5, 4, arr);
   edge(3, 2, arr);
   edge(1, 5, arr);
   edge(1, 2, arr);
   edge(3, 5, arr);
   edge(1, 3, arr);
   //call lexo function
   lexo(arr, n);
   return 0;
}

ผลลัพธ์

หากเรารันโปรแกรมด้านบน มันจะสร้างผลลัพธ์ดังต่อไปนี้

1 2 3 4 5