tailieunhanh - bài giảng các chuyên đề phần 7

Lý thuyết đồ thị procedure Enter; {Nhập dữ liệu từ thiết bị nhập chuẩn (Input)} var i, u, v, m: Integer; begin FillChar(a, SizeOf(a), False); {Khởi tạo đồ thị chưa có cạnh nào} ReadLn(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(u, v); a[u, v] := True; a[v, u] := True; end; end; procedure DFS(u: Integer); var v: {Vào dòng | Lý thuyết đồ thị 12 procedure Enter Nhập dữ liệu từ thiết bị n hập chuẩn Input var i u v m Integer begin FillChar a SizeOf a False Khởi tạo đồ thị chưa có cạnh nào ReadLn n m S F Đọc dòng 1 ra 4 số n m S và F for i 1 to m do begin ReadLn u v Đọc m dòng tiếp ra danh sách cạnh a u v True a v u True end 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 u Free u False Thông báo tới được u Đánh dấu u đã thăm for v 1 to n do if Free v and a u v then begin Trace v u DFS v Với mỗi đỉnh v chưa thăm kề với u Lưu vết đường đi Đỉnh liền trước v trong đường đi từ S tới v là u 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 Vào dòng thứ hai của Output file if Free F then Nếu F chưa đánh dấu thăm tức là không có đường WriteLn Path from S to F not found else Truy vết đường đi bắt đầu từ F begin while F S do begin Write F - F Trace F end WriteLn S end end begin Định nghĩa lại thiết bị nhập xuất chuẩn thành Input Output file Assign Input Reset Input Assign Output Rewrite Output Enter FillChar Free n True DFS S Result Đóng Input Output file thực ra không cần vì BP tự động đóng thiết bị nhập xuất chuẩn trước khi kết thúc chương trình Close Input Close Output end. Chú ý a 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 b Đườ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. Lê Minh Hoàng Lý thuyết đồ thị 13 c 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 Write u for v 1 to n do if Trace v 0 and A u v then Trace v 0 thay vì Free v True begin .