Tìm đồ thị con to nhất trong đồ thị cho trước khi biết đỉnh đầu và đỉnh cuối

#1

Giả sử mình có 1 cái đồ thị có hướng. Giờ làm sao để tìm ra một đồ thị con khi có input là:

  • Một tập các đỉnh đầu
  • Một tập các đỉnh cuối
  • Đỉnh đầu là đỉnh không có cạnh nào đi tới nó.
  • Đỉnh cuối là đỉnh không có cạnh nào xuất phát từ nó.

Cái này mình nghĩ có thể làm theo kiểu quay lui. Mỗi đỉnh sẽ gán nhãn là UNVISITED, bắt đầu từ đỉnh đầu, đi tiếp đến các đỉnh tiếp theo, để thành VISITED, cứ thế đến khi nào gặp 1 đỉnh cuối. Nếu đỉnh cuối khác tập input thì đặt lại UNVISITED rồi quay ngược lên đỉnh trên nó. Nếu đỉnh trên nó không nối tới đỉnh nào VISITED thì đặt là UNVISITED rồi lại lên tiếp,… => Như thế tất cả các đỉnh có cạnh là VISITED sẽ tạo thành đồ thị mình muốn.

Nhưng mà cách này thì thời gian xử lí sẽ lâu vì phải duyệt trong đồ thị rất nhiều lần, có ai biết được phương pháp nào độ phức tạp thấp mà duyệt cây nhanh hơn có thể bày cho mình được không ạ. Cảm ơn nhiều hiuhiu!!!

#2

Cứ BFS/DFS từ các đỉnh đầu bình thường thôi.

#3
1 Like
#4

Mình không muốn tìm 1 đường duy nhất, mà muốn tìm tất cả các đỉnh trong quá trính đi từ đỉnh đầu -> đỉnh cuối, hay nói cách khác là tìm tất cả các đg đi có thể từ đầu -> cuối xong gộp lại thành 1 đồ thị con ấy

#5

Đồ thị con to nhất trong đồ thị… chẳng phải là loại đi các cạnh không hợp lệ thôi sao?

u thuộc tập nguồn, v thuộc tập đích.
Bỏ đi tất cả các cạnh (x -> u) và cạnh (v -> y) với x, y là các đỉnh bất kì.

#6

Nối tất cả điểm đầu vào 1 điểm mới, gọi là đỉnh đầu.
Nối tất cả điểm cuối vào 1 điểm mới, gọi là đỉnh cuối.

Bài toán đơn giản lại là tìm đồ thị liên thông từ đỉnh đầu mới đến đỉnh cuối mới

1 Like
#7

Vậy còn trường hợp u -> a mà a là lá không thuộc v thì sao.
Cái ý tưởng loại trừ cũng hay đó, xét thêm trường hợp loại hết tất cả các lá không thuộc v rồi loại hết từ lá đó trở ngược lại có lẽ ổn :+1: :+1: :+1:

#8

Ô cách này hay phết này. Nhưng mà có thể có trường hợp đỉnh đầu và cuối trùng nhau (kiểu từ 1 đỉnh đi lòng vòng sang các đỉnh khác rồi về chính nó ấy)

#9

Này là lý thuyết đồ thị à?

#10

Trùng nhau thì đỉnh đó không có cạnh nào liên kết, không có trường hợp đi lòng vòng.
Lý do vì trước đó đã định nghĩa đỉnh đầu và đỉnh cuối. Nếu 1 đỉnh thỏa cả 2 định nghĩa thì đỉnh không có cạnh vào cũng không có cạnh ra.

2 Likes
#11

Thì bỏ đi tiếp. DFS/BFS để bỏ.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?