Archive | Ngôn ngữ C++
RSS for this section
[C++] Tìm chu trình Euler
Tác giả:
- Trần Hán Huy – tranhanhuy.wordpress.com
Đề bài
- Cho G=(X,E) là một đồ thị liên thông vô hướng gồm n đỉnh. Hãy tìm chu trình Euler
Lý thuyết
- CHU TRÌNH Euler: dây chuyền đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần và đỉnh bắt đầu đi trùng với đỉnh kết thúc
Code chỉ giải quyết
- Dùng tham số dòng lệnh với tập tin input
- Đầu vào input : là ma trận kề
- Do là ma trận kề nên ko thể hiện được cạnh song song và khuyên : mặt hạn chế
- yêu cầu đưa vào là 1 đồ thị Euler
- Chỉ giải quyết 1 đồ thị Euler
- Đầu vào là file input, đầu xuất là màn hình
- Sử dụng stack để giải quyết vấn đề
- Chỉ xuất ra 1 chu trình Euler
- vào ma trận kề nhưng được chuyển qua thành danh sách cạnh đầy đủ: tức 1 cạnh được lặp 2 lần. UV và VU
Code tìm chu trình Euler
void Euler::TimChuTrinh()
{
//tao 1 stack
vector<Canh> stack;
//Cạnh tạm bằng cạnh đầu tiên trong dscanh
Canh tam = m_DsCanh[0];
//Xóa cạnh bắt đầu
m_DsCanh.erase(m_DsCanh.begin() + 0);
//đưa cạnh đầu tiên vào stack
stack.push_back(tam);
//Kiểm tra số lượng stack
while (stack.size()>0)
{
//lấy cạnh cuối cùng trong stack
tam = stack[stack.size()-1];
//xóa cạnh giống với tam: tam là UV thì xóa đi VU
for (int i = 0; i < (signed)m_DsCanh.size(); i++)
{
if (m_DsCanh[i].SoSanhDinh1(tam.getDinh2()) && m_DsCanh[i].SoSanhDinh2(tam.getDinh1()))
//xoa cạnh VU
m_DsCanh.erase(m_DsCanh.begin() + i);
}
//cờ để đánh dấu có cạnh kề với đỉnh 2 của cạnh tạm ko?
bool flag = false;
//Tìm cạnh kề đầu tiên với đỉnh 2 của cạnh tạm
for (int i = 0; i < (signed)m_DsCanh.size(); i++)
{
//tìm cạnh tiếp theo có đỉnh đầu là đỉnh 2 của cạnh tạm
if (m_DsCanh[i].SoSanhDinh1(tam.getDinh2()))
{
//lấy cạnh i ra
tam = m_DsCanh[i];
//đưa vào stack
stack.push_back(tam);
//xóa cạnh i ra dsCanh
m_DsCanh.erase(m_DsCanh.begin() + i);
//bật cờ
flag = true;
//thoát ra vòng for
break;
}
}
//không có cạnh kề
if (!flag)
{
//tiến hành lấy cạnh tạm nhưng đảo ngược đỉnh đầu cuối
Canh t(tam.getDinh2(), tam.getDinh1());
//đưa vào chu trinh euler
m_ChuTrinh.push_back(t);
//xóa cạnh tam ra khỏi stack
stack.pop_back();//vì tam là cạnh cuối của stack nên chỉ popback đc rồi
}
}
}
Link source:
[C++] Tìm tất cả đồ thị con của các thành phần liên thông trong đồ thị G
Tác giả:
- Trần Hán Huy – tranhanhuy.wordpress.com
Đề bài
- Cho G=(X,E) là một đồ thị gồm n đỉnh. Hãy tìm tất cả đồ thị con của đồ thị G liên thông
Code áp dụng
- đối tượng
- Giải quyết nhiều liên thông
- Main sử dụng tham số dòng lệnh
- Nhập từ tập tin và chỉ xuất ra màn hình để xem kết quả (ko xuất ra tập tin)
- Xuất theo thứ tự từ liên thông nhỏ đến lớn , đồ thị con nhỏ nhất đến đồ thị con lớn nhất 🙂
Input trong source kèm theo là hình sau:
Ý tượng trong code
void DoThiCon :: XuatDoThiCon()
{
//Tim chieu dai theo thu tu tang dan
for (int L=1; L<=(signed) m_DinhLienThong.size(); L++)
{
//duyet tung dinh cua DinhLienThong
for (int j=0; j<(signed) m_DinhLienThong.size(); j++)
{
vector<int> DsDinh ;
DsDinh.push_back(m_DinhLienThong[j]);
XuatDoThiConTheoL(m_DinhLienThong[j], L, DsDinh);
}
}
}
void DoThiCon::XuatDoThiConTheoL(int DinhX, int L, vector<int> DsDinh)
{
if (DsDinh.size()==L)
{
XuatDoThiConTimDuoc(DsDinh);
return;
}
//duyet tung dinh ke co gia tri lon hon dinh X
for (int i=DinhX + 1; i<(signed)m_MaTranKe.size(); i++)
{
if (m_MaTranKe[DinhX][i] != 0)
{
DsDinh.push_back(i); //dua vao Ds Dinh
XuatDoThiConTheoL(i, L, DsDinh);
DsDinh.pop_back(); //Lay ra khoi Ds Dinh
}
}
}
Link source:
[C++] Tìm đỉnh gốc của đồ thị G có hướng
Tác giả:
- Trần Hán Huy – tranhanhuy.wordpress.com
Đề bài
- Cho G=(X,E) là một đồ thị có hướng có trọng số gồm n đỉnh. Hãy tìm Gốc của đồ thị G có hướng
Lý thuyết
- Đồ thị có hướng: có thể có nhiều đỉnh gốc
- Cây có hướng: chỉ tồn tại duy nhất 1 đỉnh gốc
- Đỉnh gốc là từ đỉnh đó có thể đi hết tất cả các đỉnh trong đồ thị có hướng và liên thông
Code áp dụng
- đối tượng
- Giải quyết nhiều đồ thị có hướng và liên thông
- Main sử dụng tham số dòng lệnh
- Có thể sửa lại ở main cách nhập ma trận kề từ bàn phím hay tập tin
- Tìm ra nhiều gốc của đồ thị G có hướng
Input1 trong source kèm theo là hình sau:
Ý tượng trong code
void Goc::TimGoc()
{
//duyet qua tat ca cac dinh cua do thi lien thong
for (int i=0; i<(signed)m_DinhLienThong.size(); i++)
{
m_DinhGoc = m_DinhLienThong[i];
vector<int> DsDinh;
DsDinh.push_back(m_DinhGoc);
if (TimGocTuX(m_DinhGoc, DsDinh))
{
cout << m_DinhGoc << endl;
}
}
}
bool Goc::TimGocTuX(int x, vector<int> &DsDinh)
{
//kiem tra dieu kien dung
if (DsDinh.size() == m_DinhLienThong.size())
return true;
//duyet qua tung dinh noi voi X
for (int i=0; i<(signed)m_MaTranKe[x].size(); i++)
{
//Canh XI ton tai va chua di qua
if (m_MaTranKe[x][i] != 0 && !KiemTraXDiChua(i, DsDinh))
{
//Dua I vao DSDinh
DsDinh.push_back(i);
//tu I di tim duong di cac dinh khac
if (TimGocTuX(i,DsDinh))
return true;
}
}
return false;
}
Link source:
[C++] Tìm tất cả chu trình Hamilton
Tác giả:
- Trần Hán Huy – tranhanhuy.wordpress.com
Đề bài
- Cho G=(X,E) là một đồ thị liên thông có trọng số gồm n đỉnh. Hãy tìm Tất cả chu trình Hamilton
Lý thuyết
- CHU TRÌNH HAMILTON: dây chuyền đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần và một cạnh trong đồ thị nối đỉnh đầu của dây chuyền với đỉnh cuối của nó
Thuật toán
- Tới thời điểm này thì vẫn chư có 1 thuật toán tối ưu nào để áp dụng.
- Đoạn code dưới sử dụng thuật toán đệ qui quay lùi
Ý tượng tìm 1 chu trình Hamilton
Thuật toán đệ quy quay lùi thực hiện các bước sau:
- B1: đưa đỉnh x vào đường đi
- B2: kiểm tra chu trình đủ chiều dài chưa? (tức là đã đi hết tất cả các đỉnh chưa?) và đồng thời kiểm tra đình đầu và đỉnh cuối của chu trình có cạnh nối hay ko? Nếu true hết cả 2 điều kiện thì kết luận có chu trình Hamilton. Ngược lại gọi B3
- B3: Duyệt hết tất cả các đỉnh kề với x
- B4: Kiểm tra đỉnh kề đã đi qua chưa? Nếu true gọi lại hàm đệ qui tìm chu trình Hamilton
- B5: Xóa đỉnh kề ra khỏi chu trình
Link source:
[C++] Tìm 1 chu trình Hamilton
Tác giả:
- Trần Hán Huy – tranhanhuy.wordpress.com
Đề bài
- Cho G=(X,E) là một đồ thị liên thông có trọng số gồm n đỉnh. Hãy tìm Một chu trình Hamilton
Lý thuyết
- CHU TRÌNH HAMILTON: dây chuyền đi qua tất cả các đỉnh của đồ thị mỗi đỉnh đúng một lần và một cạnh trong đồ thị nối đỉnh đầu của dây chuyền với đỉnh cuối của nó
Thuật toán
- Tới thời điểm này thì vẫn chư có 1 thuật toán tối ưu nào để áp dụng.
- Đoạn code dưới sử dụng thuật toán đệ qui quay lùi
Ý tượng tìm 1 chu trình Hamilton
Thuật toán đệ quy quay lùi thực hiện các bước sau:
- B1: đưa đỉnh x vào đường đi
- B2: kiểm tra chu trình đủ chiều dài chưa? (tức là đã đi hết tất cả các đỉnh chưa?) và đồng thời kiểm tra đình đầu và đỉnh cuối của chu trình có cạnh nối hay ko? Nếu true hết cả 2 điều kiện thì kết luận có chu trình Hamilton. Ngược lại gọi B3
- B3: Duyệt hết tất cả các đỉnh kề với x
- B4: Kiểm tra đỉnh kề đã đi qua chưa? Nếu true gọi lại hàm đệ qui tìm chu trình Hamilton
- B5: Xóa đỉnh kề ra khỏi chu trình
Link source:
朱漢輝 （Trần Hán Huy) 