Giải thuật sắp xếp Topo

[iumomo]

Help me!!!!!!!!!!!!!!!!!!
Ai đã từng cài đặt giải thuật sắp xếp Topo cho mình code nhé. Cám ơn nhiều
lắm.
Cài đặt giải thuật sắp xếp Topo :
-Dữ liệu vào : Tệp văn bản chứa dữ liệu
-Dữ liệu ra :Tệp văn bản

[Đoàn Dự]

Help me!!!!!!!!!!!!!!!!!!
Ai đã từng cài đặt giải thuật sắp xếp Topo cho mình code nhé. Cám ơn nhiều
lắm.
Cài đặt giải thuật sắp xếp Topo :
-Dữ liệu vào : Tệp văn bản chứa dữ liệu
-Dữ liệu ra :Tệp văn bản

Chưa nghe đến giải thuật Topo bao giờ, bạn nói qua về nó xem nào, ý tưởng, giải thuật.

[Ada]

Sắp xếp topo là sắp xếp tập hợp trên đó quan hệ "nhỏ hơn hoặc bằng" là một quan hệ không toàn phần.

Thí dụ, trên tập 52 quân bài trong một bộ bài Tây có thể xác định phép so sánh như sau:

2 < 3 < 4 <...< 10 < J < Q < K < A để so sánh 2 lá bài cùng chất,
bích < chuồn < rô < cơ để so sánh 2 lá bài cùng điểm, và
2 lá bài khác chất và khác điểm không so sánh được với nhau.

Khi đó, sắp xếp topo của bộ bài là sắp xếp các quân bài thành một dãy a[1],...,a[52] sao cho nếu a[i] so sánh được với a[j] thì a[i] < a[j] với i<j.

[mushu]

Mình gợi ý bạn cách sau nhé.
Mình thấy bài này có vẻ là phải xắp sếp củng điển trước rồi mới đến chất.
2 bích <2 chuồn < 2 rô < 2 cơ < 3 bích...
Thì mình có ý tưởng như sau.
2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A
Thì bạn gán giá trị tương ứng như sau:
0 4 8 ........
Cứ điểm tiếp thì tăng 4 đơn vị.
bích < chuồn < rô < cơ
thì bạn cho nhận giá trị:
0 1 2 3
Giá trị của một quân bài sẽ bẳng điểm nó cộng với chất.
Ví dụ quân
3 bich=4+0=4
4 rô=8+2=10

Sau đó bạn thực hiện xắp sếp dãy giá trị đó bình thường.

[iumomo]

Cám ơn nha. Mình cũng hiểu được một ít rồi nhưng không cài đặt được , mình dốt lập trình lắm .Giúp mình với

[Ada]

Mình google và tìm được thuật toán này:

-------------------- Nguồn: http://en.wikipedia.org/wiki/Topological_sorting --------------------
The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges (Θ(|V|+|E|)).

One of these algorithms works by choosing vertices in the same order as the eventual topological sort. First, find a list of "start nodes" which have no incoming edges and insert them into a queue Q (at least one such node must exist if graph is acyclic). L is the list that will contain the nodes in topological sorted order after the end of the algorithm. Then,

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)

If the graph was a DAG, a solution is contained in the list L (the solution is not unique). Otherwise, the graph has at least one cycle and therefore a topological sorting is impossible.

Note that, reflecting the non-uniqueness of the resulting sort, the structure Q need not be a queue; it may be a stack or simply a set. Depending on the order that nodes n are removed from set Q, a different solution is created.

An alternative algorithm for topological sorting is based on depth-first search. Loop through the vertices of the graph, in any order, initiating a depth-first search for any vertex that has not already been visited by a previous search. The desired topological sorting is the reverse postorder of these searches. That is, we can construct the ordering as a list of vertices, by adding each vertex to the start of the list at the time when the depth-first search is processing that vertex and has returned from processing all children of that vertex. Since each edge and vertex is visited once, the algorithm runs in linear time.
-------------------- Nguồn: http://en.wikipedia.org/wiki/Topological_sorting --------------------

Ghi chú: thuật toán trên sắp xếp các đỉnh của một đồ thị có hướng không chu trình (acyclic directed graph), vốn dĩ đẳng cấu với tập hợp trang bị quan hệ so sánh không toàn phần. (Trong đồ thị, tồn tại 1 cạnh dẫn từ đỉnh x đến đỉnh y nếu và chỉ nếu trong tập hợp, phần tử x có thể so sánh với phần tử y và x < y.)

[iumomo]

Bạn cho đoạn code này mình xem mà như là ko xem ý , chả hiểu gì cả.Dù sao cũng thanks !!!!!!

[Ada]

Thôi để mình dịch tạm ra cho bạn vậy.

----------------------------------------------------------------------
Các thuật toán sắp xếp topo thường có thời gian thực hiện là tỷ lệ thuận với tổng số đỉnh và số cạnh, Θ(|V|+|E|).

Một trong các thuật toán này hoạt động bằng cách lần lượt chọn ra các đỉnh theo đúng thứ tự sắp xếp mà ta sẽ thu được. Trước hết, tìm một danh sách các "đỉnh bắt đầu" tức là các đỉnh không có cạnh dẫn vào, và đưa chúng vào một hàng đợi (queue) Q. (Nếu đồ thị không chu trình, chắc chắn tồn tại ít nhất một đỉnh như thế.) L sẽ là danh sách các đỉnh theo thứ tự sắp xếp topo sau khi thuật toán kết thúc. Ta có

L ← Danh sách rỗng. 
Q ← Tập hơp các đỉnh không có cạnh nào dẫn vào chúng.
while Q không rỗng do
    lấy một đỉnh n ra khỏi Q
    cho n vào L
    for each đỉnh m có cạnh e dẫn từ n vào m do
        xóa cạnh e khỏi đồ thị
        if m không còn cạnh nào dẫn vào nữa then
            cho m vào Q
if đồ thị có cạnh then
    báo lỗi: đồ thị có chu trình
else 
    báo kết quả: danh sách L.

Nếu đồ thị là không chu trình, L sẽ chứa một nghiệm (nghiệm này không phải là duy nhất). Nếu ngược lại thì đồ thị là có chu trình và thứ tự sắp xếp topo không tồn tại.

Chú ý rằng do tính chất không duy nhất của nghiệm, cấu trúc Q không nhất thiết phải là hàng đợi; nó có thể là một ngăn xếp (stack) hay chỉ đơn giản là một tập hợp. Tùy theo thứ tự lấy các đỉnh n ra khỏi tập Q, ta có thể tạo được một nghiệm khác.

Một thuật toán khác cho việc sắp xếp topo được dựa trên việc duyệt theo chiều sâu (depth-first search). (...Bỏ một đoạn...)

[iumomo]

Cảm ơn nhiều nhiều....