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

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

Giải thuật tìm kiếm A*

Trong khoa học máy tính, A* (đọc là A sao) là một thuật toán tìm kiếm trong đồ thị. Thuật toán này tìm một đường đi từ một nút khởi đầu tới một nút đích cho trước (hoặc tới một nút thỏa mãn một điều kiện đích). Thuật toán này sử dụng một "đánh giá heuristic" để xếp loại từng nút theo ước lượng về tuyến đường tốt nhất đi qua nút đó. Thuật toán này duyệt các nút theo thứ tự của đánh giá heuristic này. Do đó, thuật toán A* là một ví dụ của tìm kiếm theo lựa chọn tốt nhất (best-first search). Thuật...

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

Đồ 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ì.

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

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

Ô 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)

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

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.

Vậy còn trường hợp u -> a mà a là lá không thuộc v thì sao.

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