การพิมพ์ 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 แบบเล็กซิโคกราฟิกที่น้อยที่สุด

อัลกอริทึม

Start
Step 1 -> Declare Function void lexo(vector* arr, int n)
  Declare bool check[n + 1] = { 0 }
  Loop For int i=0; i declare Function void edge(int u, int v, vector* arr)
  Call ar[u].push_back(v)
  Call ar[v].push_back(u)
Step 3 -> Declare function void graph(vector* arr, int src, int n,bool* check)
  print src
  Set check[src] = true
  Loop for int i = 0; i < arr[src].size(); 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 arr[n + 1]
  Call edges(1,4, arr)
  Call edges(3,4, arr)....
  Call lexo(arr, n)
Stop

ตัวอย่างโค้ด C++

#include 
using namespace std;
// สำหรับเพิ่มเส้นขอบ
void edge(int u, int v, vector* arr){
    arr[u].push_back(v);
    arr[v].push_back(u);
}
// ฟังก์ชัน DFS สำหรับการเดินทางกราฟ
void graph(vector* 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* 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 arr[n + 1];
    // เพิ่มเส้นขอบ
    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);
    // เรียกฟังก์ชัน lexo
    lexo(arr, n);
    return 0;
}

ผลลัพธ์

การรันโปรแกรมจะได้ผลลัพธ์ดังนี้:

1 2 3 4 5