Phân loại cạnh trong quá trình tìm kiếm theo chiều rộng đầu tiên trên đồ thị có hướng

Question

Tôi đang gặp khó khăn khi tìm cách phân loại chính xác các cạnh trong khi tìm kiếm theo chiều rộng trên biểu đồ được chỉ dẫn.

Trong một tìm kiếm theo chiều rộng hoặc chiều sâu-đầu tiên, bạn có thể phân loại các cạnh gặp với 4 lớp:

• TREE
• LẠI
• CHÉO
• HƯỚNG

Skiena [1] đưa ra một triển khai. Nếu bạn di chuyển dọc theo một cạnh từ v1 đến v2, đây là một cách để trả về lớp trong một DFS trong java, để tham khảo. Bản đồ cha mẹ trả về đỉnh mẹ cho tìm kiếm hiện tại và phương thức timeOf(), thời gian mà đỉnh đã được phát hiện.

if (v1.equals(parents.get(v2))) { return EdgeClass.TREE; } 
    if (discovered.contains(v2) && !processed.contains(v2)) { return EdgeClass.BACK; } 
    if (processed.contains(v2)) 
    { 
     if (timeOf(v1) < timeOf(v2)) 
     { 
      return EdgeClass.FORWARD; 
     } 
     else 
     { 
      return EdgeClass.CROSS; 
     } 
    } 
    return EdgeClass.UNCLASSIFIED; 

Vấn đề của tôi là tôi không thể làm cho nó phù hợp với một Chiều rộng tìm kiếm đầu tiên trên một đồ thị có hướng. Ví dụ:

sau Đồ thị - đó là một vòng lặp - là ok:

A -> B 
A -> C 
B -> C 

BFSing từ A, B sẽ được phát hiện, sau đó C. cạnh EAB và EAC là cạnh TREE, và khi EBC vượt qua cuối cùng, B và C được xử lý và phát hiện, và cạnh này được phân loại đúng là CROSS.

Nhưng một vòng lặp đơn giản không hoạt động:

A -> B 
B -> C 
C -> A 

Khi mép ECA được vượt qua, A được xử lý và khám phá. Vì vậy, cạnh này được gắn nhãn không chính xác là CROSS, cho dù nó có phải là một cạnh BACK hay không.

Không có sự khác biệt nào về cách xử lý hai trường hợp, ngay cả khi hai cạnh có các lớp khác nhau.

Làm cách nào để bạn triển khai phân loại cạnh thích hợp cho BFS trên biểu đồ được chỉ dẫn?

[1] http://www.algorist.com/

---

EDIT

đây một thực hiện bắt nguồn từ @redtuna câu trả lời. Tôi vừa thêm một kiểm tra không tìm nạp phụ huynh gốc. Tôi có JUnits xét nghiệm cho thấy nó hoạt động cho đồ thị có hướng và vô hướng, trong trường hợp của một vòng lặp, một đường thẳng, một ngã ba, một ví dụ tiêu chuẩn, một lợi thế cạnh duy nhất, vv ....

@Override 
public EdgeClass edgeClass(final V from, final V to) 
{ 
    if (!discovered.contains(to)) { return EdgeClass.TREE; } 

    int toDepth = depths.get(to); 
    int fromDepth = depths.get(from); 

    V b = to; 
    while (toDepth > 0 && fromDepth < toDepth) 
    { 
     b = parents.get(b); 
     toDepth = depths.get(b); 
    } 

    V a = from; 
    while (fromDepth > 0 && toDepth < fromDepth) 
    { 
     a = parents.get(a); 
     fromDepth = depths.get(a); 
    } 

    if (a.equals(b)) 
    { 
     return EdgeClass.BACK; 
    } 
    else 
    { 
     return EdgeClass.CROSS; 
    } 

} 

Answer 1

Làm cách nào để bạn triển khai phân loại cạnh thích hợp cho BFS trên biểu đồ hướng dẫn ?

Khi bạn đã thiết lập, nhìn thấy một nút lần đầu tiên tạo ra cạnh cây. Vấn đề với BFS thay vì DFS, như David Eisenstat đã nói trước tôi, là các cạnh sau không thể được phân biệt với các đường chéo chỉ dựa trên thứ tự truyền tải.

Thay vào đó, bạn cần thực hiện thêm một chút công việc để phân biệt chúng. Chìa khóa, như bạn sẽ thấy, là sử dụng định nghĩa của một cạnh chéo.

Cách đơn giản nhất (nhưng tốn nhiều bộ nhớ) là kết hợp mọi nút với tập hợp các phiên bản trước đó. Điều này có thể được thực hiện tầm thường khi bạn truy cập các nút. Khi tìm một cạnh không phải cây giữa các nút a và b, hãy xem xét các tập tiền thân của chúng. Nếu một là một tập hợp con thích hợp của phần còn lại, thì bạn có một cạnh sau. Nếu không, đó là một cạnh chéo. Điều này xuất phát trực tiếp từ định nghĩa của một cạnh chéo: đó là một cạnh giữa các nút không phải là tổ tiên cũng như hậu duệ của cái kia trên cây.

Cách tốt hơn là chỉ liên kết số "chiều sâu" với mỗi nút thay vì một tập hợp. Một lần nữa, điều này dễ dàng thực hiện khi bạn truy cập các nút. Bây giờ khi bạn tìm thấy một cạnh phi cây giữa a và b, bắt đầu từ sâu hơn của hai nút và làm theo các cạnh cây ngược lại cho đến khi bạn quay trở lại độ sâu tương tự như cái kia. Vì vậy, ví dụ giả sử là một sâu hơn. Sau đó, bạn lặp lại tính toán a = parent (a) cho đến độ sâu (a) = depth (b).

Nếu tại thời điểm này a = b thì bạn có thể phân loại cạnh là cạnh sau vì, theo định nghĩa, một trong các nút là tổ tiên của cây kia trên cây. Nếu không, bạn có thể phân loại nó như là một cạnh chéo bởi vì chúng ta biết rằng không phải nút nào là tổ tiên hoặc hậu duệ của người khác.

giả:

foreach edge(a,b) in BFS order: 
    if !b.known then: 
     b.known = true 
     b.depth = a.depth+1 
     edge type is TREE 
     continue to next edge 
    while (b.depth > a.depth): b=parent(b) 
    while (a.depth > b.depth): a=parent(a) 
    if a==b then: 
     edge type is BACK 
    else: 
     edge type is CROSS 

Answer 2

Các thuộc tính khóa của DFS ở đây là, với hai nút u và v, khoảng thời gian [u.discovered, u.processed] là một khoảng con của [v.discovered, v.processed] nếu và chỉ khi u là hậu duệ của v. Thời gian trong BFS không có tài sản này; bạn phải làm điều gì đó khác, ví dụ: tính toán các khoảng thời gian thông qua DFS trên cây mà BFS tạo ra. Sau đó, mã giả phân loại là 1. kiểm tra thành viên trong cây (cạnh cây) 2. kiểm tra khoảng thời gian của đầu chứa đuôi (cạnh sau) 3. kiểm tra khoảng thời gian đuôi chứa đầu (cạnh tiến) 4. nếu không, khai báo một cạnh chéo.

Answer 3

Thay vì timeof(), bạn cần một tài sản đỉnh khác, trong đó có khoảng cách từ gốc. Hãy đặt tên là distance.

Bạn cần phải xử lý một đỉnh v theo cách sau:

for (v0 in v.neighbours) { 
    if (!v0.discovered) { 
     v0.discovered = true; 
     v0.parent = v; 
     v0.distance = v.distance + 1; 
    } 
} 
v.processed = true; 

Sau khi bạn xử lý một đỉnh một đỉnh v, bạn có thể chạy các thuật toán sau đây cho mỗi cạnh (v1-v2) của v :

if (!v1.discovered) return EdgeClass.BACK; 
else if (!v2.discovered) return EdgeClass.FORWARD; 
else if (v1.distance == v2.distance) return EdgeClass.CROSS; 
else if (v1.distance > v2.distance) return EdgeClass.BACK; 
else { 
    if (v2.parent == v1) return EdgeClass.TREE; 
    else return EdgeClass.FORWARD; 
}