thiet ke website

[Lập trình C++] Bài toán tô màu các đỉnh của đồ thị

Bài toán tô màu là bài toán kinh điển của dạng đồ thị trong lập trình. Yêu cầu của bài toán là tô màu các đỉnh sao cho những đỉnh được nối với nhau không có màu trùng nhau, số màu tô là ít nhất. Đây là một bài toán được phát triển ra rất nhiều các trường hợp khác nhau, trong những lĩnh vực khác nhau.

tô màu đồ thị c++Các đỉnh được nối với nhau, số màu được tô sao cho ít nhất!

bài toán tô màu đồ thị c++Đây là nội dung file dothi.txt, dòng đầu tiên là số đỉnh, các dòng tiếp theo là những đỉnh được nối với nhau, ghi theo chiều nào cũng được.

tô màu các đỉnh của đồ thị c++Đây là console sau khi chạy chương trình.

Và dưới đây là source code của bài toán tô màu cá đỉnh đồ thị

#include <iostream>
#include <cstring>
#include <fstream>

using namespace std;

int n, a[10][10],sm=0,m[10];

void docfile(){ //Dung de doc file, sau do gan vao mang a[][]
	int q,p;
	ifstream dothi ("dothi.txt");
	if (dothi.is_open())
	{
		dothi >> n;
		while (!dothi.eof()) //Doc file cho den cuoi file
		{
			dothi >> q;
			dothi >> p;
			a[q][p]=1;
			a[p][q]=1;
		}
		dothi.close();
	}
	else cout << "Khong mo duoc file";
}

void xuly(){ //Xu ly de cho ra ket qua vao mang m[]
	int kt;
	for(int i=1;i<=n;i++)
		if(!m[i]) {
			sm++; //Dem so mau
			m[i]=sm;
			for(int j=i+1;j<=n;j++) //Kiem tra xem nhung dinh nao co the gan bang mau sm nua khong
				if((a[i][j]==0)&&(m[j]==0)){
					kt=1;
					for(int k=i+1;k<j;k++)
						if((a[k][j]==1)&&(m[i]==m[k])){
							kt=0;
							break;
						}
					if(kt==1) m[j]=sm;
				}					
		}
}
void xuatkq(){ //In ket qua ra man hinh
	for(int i=1;i<=sm;i++){
		cout << "Mau " << i << ": ";
		for(int j=1;j<=n;j++) if(m[j]==i) cout << j << " ";
		cout << endl;
	}
}
int main(){
	docfile();
	cout << n << endl;
	for(int i=1;i<=n;i++){ //In mang ra man hinh de theo doi
		for(int j=1;j<=n;j++) cout << a[i][j] << "  ";
		cout << endl;
	}cout << endl;
	xuly();
	xuatkq();
	return 0;
}

Bài toán trên do mình tự code, test trên vài trường hợp cơ bản, nếu các bạn phát hiện ra lỗi gì thì bình luận phía dưới để mình chỉnh sửa. Chúc các bạn học tập và làm việc vui vẻ 😀

Thiet ke logo

Bài viết liên quan

Tải DevExpress 16.1.2 full mới nhất, hướng dẫn cài đặt

Tải DevExpress 16.1.2 full mới nhất, hướng dẫn cài đặt

Ban đầu, DevExpress phát triển UI Controls cho Borland Delphi/C++ Builder, ActiveX Controls cho Microsoft Visual Studio. Hiện nay, DevExpress hướng tới lập trình viên sử dụng Delphi/c++ Builder, Visual Studio và HTML5/Javascript. DevExpress là bộ công cụ hữu ích hỗ trợ các lập trình…

Những website viết code trực tuyến cho dân lập trình

Những website viết code trực tuyến cho dân lập trình

Ngoài cách viết code bằng các phần mềm soạn thảo thông thường, bạn có thể sử dụng các công cụ trực tuyến. Lúc đó, bạn sẽ dễ dàng có thể chia sẻ code cho bạn bè mình thông qua các URL. Jsbin.com JS Bin là…

[C++] SPOJ.COM – Problem Bonus – VOI 2011 Phần thưởng

[C++] SPOJ.COM – Problem Bonus – VOI 2011 Phần thưởng

Để bài: (Nguồn: SPOJ) Tuấn là người chiến thắng trong một cuộc thi “tìm hiểu kiến thức vũ trụ” và được nhận các phần thưởng do công ty XYZ tài trợ. Các phần thưởng được bố trí trên một bảng hình vuông nxn có dạng…

[Java cơ bản] Bài 34: Overload (Phần 2)

[Java cơ bản] Bài 34: Overload (Phần 2)

Video ngày hôm nay sẽ tiếp tục phần 2 của overload, có thắc mắc các bạn có thể để lại bình luận, mình sẽ giải đáp thắc mắc nếu biết, hehe.

Bình luận ()