Topological sort | Cài đặt trên C++ như thế nào?

[meo_beo]

Mình học môn cấu trúc dữ liệu và giải thuật ở trường có đụng đến vấn đề Topological sort ở trong phần đồ thị. Thực ra thì tư tưởng của nó không có gì quá phức tạp nhưng cái khó là làm thế nào viết được một chương trình C để demo cái kiểu sort này. Có anh em nào đã từng làm qua cái này hoặc có ý kiến gì thì làm ơn đóng góp (nếu có source code thì càng hay),

[kidkid]

Ý cậu là thế nào nhỉ ? Có phải là viết 1 chương trình giúp người học về mạng topo ko ?

[huydaibang]

Mình mới "săn" được đoạn code Topo Logical sorting này,share cho bạn:
Để chạy được file này cần có file note pad để trong thư mục Visual C của bạn với input như sau:
1 2
2 4
2 10
4 8
6 3
1 3
3 5
5 8
7 5
7 9
9 4
9 10

#include "iostream"
#include "fstream"
#include "sstream"
#include "conio.h"
using namespace std;

typedef struct leader* lref;
typedef struct trailer* tref;
struct leader{
int key;
int count;
lref next;
tref trail;
};
struct trailer{
lref id;
tref next;
};

//prototypes
int readData(lref&, lref&, int&);
void topoSort(lref&, lref&, int&);

int main(){
lref head = NULL, tail = NULL;
int z;
if(readData(head, tail, z))
topoSort(head, tail, z);
else
cout << "Ko doc duoc file topo.inp!" << endl;
_getch();
}

lref addList(lref head, lref &tail, int w, int &z){
lref h = head;
tail->key = w;
while(h->key != w) h = h->next;
if(h==tail){
tail = new leader;
z++;
h->count = 0;
h->trail = NULL;
h->next = tail;
}
return h;
}

int readData(lref &head, lref &tail, int &z){
ifstream f;
int x, y;
lref p, q;
tref t;

head = new leader;
tail = head;
z = 0;
f.open("topo.inp");
if(f.is_open()){
f >> x;
while(!(f.eof())){
f >> y;

// tạo 2 leader
p = addList(head, tail, x, z);
q = addList(head, tail, y, z);

// thêm trailer cho p
t = new trailer;
t->id = q;
t->next = p->trail;
p->trail = t;
q->count ++;
f >> x;
}
return 1;
}
return 0;
}

void topoSort(lref &head, lref &tail, int &z){
lref p, q;
tref t;

p = head;
head = NULL;
while(p!=tail){
q = p;
p = p->next;
if(q->count == 0){
q->next = head;
head = q;
}
}

q = head;
while(q){
cout << q->key << endl;
--z;
t = q->trail;
q = q->next;
while(t){
p = t->id;
p->count --;
if(p->count == 0){
p->next = q;
q = p;
}
t = t->next;
}
}
if(z) cout << "\n Khong the sap topo tren day nay!\n";
getch();
}
Giải thích:VD:1 2 tức là 1 liên thông với 2(nhưng chưa chắc có đường đi từ 2 đến 1).Nhớ kĩ đây là ma trận kề của đồ thị liên thông không có trọng số có hướng Còn của đồ thị có trọng số thì tui chưa tìm ra.Có bác nào cao tay thì viết nốt code cho đồ thị có trọng số nhé( nhớ giải thích ma trận trọng số nhé
Kết quả sẽ là 7 ->9->1->2->4->6->3->5->8->10.