โปรแกรม C++ สร้างรหัส Prufer สำหรับต้นไม้

รหัส Prufer (Prufer code) ระบุต้นไม้ได้อย่างเดียว ซึ่งกำหนดโดยผู้ใช้เป็นการแสดงกราฟกับป้ายกำกับ 1 ถึง p ต้นไม้นี้ประกอบด้วย p ป้ายกำกับของโหนด มีลำดับของค่า p-2

อัลกอริทึม

เริ่มต้น
  ประกาศ i, j, ver, edg, minimum, p เป็น integer
  พิมพ์ "Enter the number of vertexes: "
  รับค่า ver
  กำหนด edg = ver-1
  ประกาศ EDG[edg][2], DG[ver+1] เป็น integer
  กำหนด DG[ver+1] = {0}
  พิมพ์ "This tree has (edg) edges for (ver) vertexes"
  พิมพ์ "There are (edg) pairs of vertexes in the tree"
  สำหรับ i = 0 ถึง edg-1 ทำ
    พิมพ์ "Enter the value of vertex pair for edge "
    พิมพ์ "Enter the value of V(1) vertex: "
    รับค่า EDG[i][0]
    พิมพ์ "Enter the value of V(2) vertex: "
    รับค่า EDG[i][1]
    DG[EDG[i][0]]++
    DG[EDG[i][1]]++
  จบลูป
  พิมพ์ "The Prufer code for the tree is: { "
  สำหรับ i = 0 ถึง ver-3 ทำ
    minimum = 10000
    สำหรับ j = 0 ถึง edg-1 ทำ
      ถ้า DG[EDG[j][0]] == 1 แล้ว
        ถ้า minimum > EDG[j][0] แล้ว
          minimum = EDG[j][0]
          p = j
        จบถ้า
      จบถ้า
      ถ้า DG[EDG[j][1]] == 1 แล้ว
        ถ้า minimum > EDG[j][1] แล้ว
          minimum = EDG[j][1]
          p = j
        จบถ้า
      จบถ้า
    จบลูป
    DG[EDG[p][0]]--
    DG[EDG[p][1]]--
    ถ้า DG[EDG[p][0]] == 0 แล้ว
      พิมพ์ค่า EDG[p][1]
    มิฉะนั้น
      พิมพ์ค่า EDG[p][0]
    จบถ้า
  จบลูป
  พิมพ์ "}"
สิ้นสุด

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

#include <iostream>
using namespace std;

int main() {
    int i, j, ver, edg, minimum, p;
    cout << "Enter the number of vertexes: ";
    cin >> ver;
    cout << endl;
    edg = ver - 1;
    int EDG[edg][2], DG[ver+1] = {0};
    cout << "This tree has " << edg << " edges for " << ver << " vertexes.\n";
    cout << "There are " << edg << " pairs of vertexes in the three.\n";
    for (i = 0; i < edg; i++) {
        cout << "Enter the value of vertex pair for edge " << i+1 << ":\n";
        cout << "Enter the value of V(1) vertex: ";
        cin >> EDG[i][0];
        cout << "Enter the value of V(2) vertex: ";
        cin >> EDG[i][1];
        DG[EDG[i][0]]++;
        DG[EDG[i][1]]++;
    }
    cout << "\nThe Prufer code for the tree is: { ";
    for (i = 0; i < ver-2; i++) {
        minimum = 10000;
        for (j = 0; j < edg; j++) {
            if (DG[EDG[j][0]] == 1) {
                if (minimum > EDG[j][0]) {
                    minimum = EDG[j][0];
                    p = j;
                }
            }
            if (DG[EDG[j][1]] == 1) {
                if (minimum > EDG[j][1]) {
                    minimum = EDG[j][1];
                    p = j;
                }
            }
        }
        DG[EDG[p][0]]--; // ลบโหนดที่เลือกโดยลด degree เป็น 0
        DG[EDG[p][1]]--; // ลด degree ของอีกโหนดหนึ่ง เนื่องจากลบ EDG
        if (DG[EDG[p][0]] == 0)
            cout << EDG[p][1] << " ";
        else
            cout << EDG[p][0] << " ";
    }
    cout << "}";
    return 0;
}

ผลลัพธ์

Enter the number of vertexes: 5
This tree has 4 edges for 5 vertexes.
There are 4 pairs of vertexes in the three.
Enter the value of vertex pair for edge 1:
Enter the value of V(1) vertex: 2
Enter the value of V(2) vertex: 3
Enter the value of vertex pair for edge 2:
Enter the value of V(1) vertex: 5
Enter the value of V(2) vertex: 6
Enter the value of vertex pair for edge 3:
Enter the value of V(1) vertex: 7
Enter the value of V(2) vertex: 8
Enter the value of vertex pair for edge 4:
Enter the value of V(1) vertex: 9
Enter the value of V(2) vertex: 10
The Prufer code for the tree is: { 4 8 4 }