tailieunhanh - Algorithms Programming - Thuật Toán Số phần 7

Các thuật toán trên đồ thị OutputFile = ''; max = 100; var a: array[1max, 1max] of Boolean; {Ma trận kề của đồ thị} Free: array[1max] of Boolean; {Free[v] = True ⇔ v chưa được thăm đến} Trace: array[1max] of Integer; {Trace[v] = đỉnh liền trước v trên đường đi từ S tới v} n, S | Các thuật toán trên đồ thị 179 OutputFile max 100 var a array of Boolean Ma trận kề của đồ thị Free array of Boolean Free v True o v chưa được thăm đến Trace array of Integer Trace v đỉnh liền trước v trên đường đi từ S tói v n S F Integer fo Text procedure Enter Nhập dữ liệu var i u v m Integer fi Text begin Assign fi InputFile Reset fi FillChar a SizeOf a False Khởi tạo đồ thị chưa có cạnh nào ReadLn fi n m S F Đọc dòng 1 ra 4 số n m S và F for i 1 to m do Đọc m dòng tiếp ra danh sách cạnh begin ReadLn fi u v a u v True a v u True end Close fi end procedure DFS u Integer Thuật toán tìm kiếm theo chiều sâu bắt đầu từ đỉnh u var v Integer begin Write fo u Thông báo tới được u Free u False Đánh dấu u đã thăm for v 1 to n do if Free v and a u v then Với mỗi đỉnh v chưa thăm kề với u begin Trace v u Lưu vết đường đi Đỉnh liền trước v trong đường đi từ S tới v là u DFS v Tiếp tục tìm kiếm theo chiều sâu bắt đầu từ v end end procedure Result In đường đi từ S tới F begin WriteLn fo Vào dòng thứ hai của Output file WriteLn fo Path from S to F if Free F then Nếu F chưa đánh dấu thăm tức là không có đường WriteLn fo not found else Truy vết đường đi bắt đầu từ F begin while F S do begin Write fo F - F Trace F end WriteLn fo S end end begin Enter Assign fo OutputFile Rewrite fo WriteLn fo From S you can visit FillChar Free n True DFS S Result Lê Minh Hoàng 180 Chuyên đề Close fo end. Chú ý Vì có kỹ thuật đánh dấu nên thủ tục DFS sẽ được gọi n lần n là số đỉnh Đường đi từ S tới F có thể có nhiều ở trên chỉ là một trong số các đường đi. Cụ thể là đường đi có thứ tự từ điển nhỏ nhất. Có thể chẳng cần dùng mảng đánh dấu Free ta khởi tạo mảng lưu vết Trace ban đầu toàn 0 mỗi lần từ đỉnh u thăm đỉnh v ta có thao tác gán vết Trace v u khi đó Trace v sẽ khác 0. Vậy việc kiểm tra một đỉnh v là chưa được thăm ta có thể kiểm tra Trace v 0. Chú ý ban đầu khởi tạo Trace S -1 Chỉ là để cho khác 0 thôi . procedure DFS u Integer Cải tiến var v Integer begin .