graph - Làm thế nào để tránh tái xử lý cùng một cạnh hai lần trong Depth First Search?

Question

Các Algorithm Design Manual mô tả BFS và DFS khá tốt. Mã cho dfs trong sách có vấn đề khi quyết định có nên tránh các cạnh xử lý kép hay không. Tôi tìm thấy các Errata và áp dụng các errata để mã, nhưng tôi vẫn nghĩ rằng mã tinh chế có một vấn đề kiểm tra các cạnh xử lý kép.

tôi dán mã tinh tế như sau:

dfs(graph *g, int v) { 
     edgenode *p; 
     int y; 
     if (finished) return; 
     discovered[v] = TRUE; 
     time = time + 1; 
     entry_time[v] = time; 
     process_vertex_early(v); 
     p = g->edges[v]; 
     while (p != NULL) { 
      /* temporary pointer */ 
      /* successor vertex */ 
      /* allow for search termination */ 
      y = p->y; 
      if (discovered[y] == FALSE) { 
        parent[y] = v; 
        process_edge(v,y); 
        dfs(g,y); 
      } 
      else if (**(!processed[y] && parent[v] != y)** || (g->directed)) 
        process_edge(v,y); 
      if (finished) return; 
      p = p->next; 
     } 
     process_vertex_late(v); 
     time = time + 1; 
     exit_time[v] = time; 
     processed[v] = TRUE; 
} 

Nơi Tôi nghĩ có một vấn đề được đánh dấu qua ** **.

Vì vậy, nơi đáng ngờ là một trong những điều kiện. Giả sử nó là đồ thị vô hướng, vì vậy chúng ta chỉ có thể bỏ qua điều kiện của (g->directed).

Ok, trước tiên hãy tập trung vào parent[v] != y. nếu parent[v] == y, tất nhiên, chúng ta không cần xử lý cạnh v-> y một lần nữa vì y-> v đã được xử lý một lần khi xử lý đỉnh y.

Và nếu parent[v] != y, câu hỏi của tôi là liệu !processed[y] && là cần thiết hay không. Vì vậy, nếu y không phải là cha mẹ của v, và processed[y] == false có nghĩa là y đã được tìm thấy (nếu không thực hiện không thể đạt được else if một phần) nhưng không được xử lý, vì vậy y phải là một bà hoặc cao hơn của v. một cạnh sau, nhưng không có vấn đề gì, chúng tôi có thể xử lý nó vì nó chưa được xử lý.

Bây giờ nếu processed[y] == true thì sao? Tôi nghĩ rằng "nếu" sẽ không bao giờ xảy ra và điều kiện này sẽ không bao giờ đúng.

Tại sao? Ok, giả sử processed[y] có thể đúng. Điều này có nghĩa rằng tất cả các đường dẫn bao gồm y đã được xử lý và tất cả các đỉnh trong các đường dẫn đó đã được xử lý, phải không? Vì vậy, nếu đây là một trường hợp, làm thế nào có thể một "chưa hoàn thành chế biến" vertex v cách tiếp cận y?

Tôi nghĩ rằng trong dfs, không có đỉnh nào sẽ tiếp cận một đỉnh được xử lý, tôi có đúng không?

Vì vậy, nếu chúng ta không bao giờ thịt một đỉnh được xử lý, chúng tôi chỉ có thể xóa !processed[y] vì nó sẽ luôn đúng.

Answer 1

Không, processed[y] == true có thể mang lại giá trị đúng.

Nhìn vào đồ thị dưới đây, và giả định sau đây [khả thi] DFS traversal:

v0,v1,v2 

v0 bắt đầu, và sau đó đệ quy gọi dfs(v1) sau khi xử lý (v0,v1). Bây giờ, v1 quy trình (v1,v2) và đệ quy gọi dfs(v2). v2 thấy rằng v0 được phát hiện và chuyển đến câu lệnh else if và thấy rằng (v0,v2) không được xử lý và parent[v2] != v0 [v2 được phát hiện qua v1].

Bây giờ, khi chúng tôi quay trở lại từ đệ quy, chúng tôi quay lại v0 và khi chúng tôi kiểm tra "con trai" tiếp theo - đó là v2. v2 đã được phát hiện, vì vậy chúng tôi truy cập else if và v2 không phải là phụ huynh của v0, vì vậy mà không có phần !processed[y], chúng tôi đã xử lý (v0,v2) hai lần.

Điều duy nhất mà ngăn chặn điều đó từ hapenning là một thực tế rằng processed[y] == true