In DFS nhỏ nhất về mặt từ vựng của biểu đồ bắt đầu từ 1 trong C Chương trình.

Chúng ta sẽ được một đồ thị liên thông với N đỉnh và M cạnh. Vì vậy, chúng ta phải in DFS nhỏ nhất về mặt từ vựng của biểu đồ bắt đầu từ 1.

Các ngành dọc phải được đánh số từ 1 đến N

Ví dụ

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

Thay vì thực hiện DFS thông thường, trước tiên chúng ta sẽ sắp xếp các cạnh liên kết với mỗi đỉnh, sao cho trong mỗi lượt chỉ có cạnh nhỏ nhất được chọn trước. Sau khi sắp xếp, chỉ cần thực hiện một DFS bình thường sẽ cung cấp truyền tải DFS nhỏ nhất về mặt từ vựng.

Dưới đây là cách triển khai C ++ của thuật toán được đưa ra bên dưới.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau

1 2 3 4 5