นี่คือโปรแกรม C++ สำหรับแก้ปัญหา Dominating Set
อัลกอริทึม
เริ่มต้น รับจำนวนจุดและขอบเป็นอินพุต รวมถึงจุดปลายของขอบ ฟังก์ชัน dominant(): ประกาศ Vector Set เลือกขอบ e ใดๆ ในกราฟที่เชื่อมจุด X และ Y เพิ่มจุดหนึ่งระหว่าง X และ Y เข้าเซต s ลบขอบทั้งหมดที่เชื่อมกับ X จบ
ตัวอย่างโค้ด
#include<bits/stdc++.h> using namespace std; vector<vector<int> > g; bool visit[10001]; int i,j; vector<int> dominant(int v,int e) { vector<int> Set; //เลือกขอบ e ใดๆ ในกราฟที่เชื่อมจุด คือ X และ Y for(i=0;i<v;i++) { if(!visit[i]) { Set.push_back(i); //เพิ่มจุด visit[i]=true; for(j=0;j<(int)g[i].size();j++) { if(!visit[g[i][j]]) { visit[g[i][j]]=true; break; } } } } return Set; } int main() { int v,e,a,b; cout<<"Enter number of vertices:"; cin>>v; cout<<"Enter number of Edges:"; cin>>e; g.resize(v); memset(visit,0,sizeof(visit)); //ตั้งค่าอาร์เรย์ทั้งหมดเป็น 0 for(i=0;i<e;i++) { cout<<"Enter the end-points of edge "<<i+1<<" : "; cin>>a>>b; a--; b--; g[a].push_back(b); g[b].push_back(a); } vector<int> Set = dominant(v,e); cout<<"The Dominant Set is:\n"; for(i=0;i<(int)Set.size();i++) cout<<Set[i]+1<<" "; return 0; }
ผลลัพธ์
Enter number of vertices:7 Enter number of Edges:6 Enter the end-points of edge 1 : 1 2 Enter the end-points of edge 2 : 2 2 Enter the end-points of edge 3 : 3 4 Enter the end-points of edge 4 : 4 5 Enter the end-points of edge 5 : 6 7 Enter the end-points of edge 6 : 4 5 The Dominant Set is: 1 3 5 6
