Ktl-icon-tai-lieu

Bài thảo luận môn toán rời rạc

Được đăng lên bởi Cô Út
Số trang: 16 trang   |   Lượt xem: 899 lần   |   Lượt tải: 0 lần
BÀI THẢO LUẬN
MÔN TOÁN RỜI RẠC

LỚP ĐHTIN6A
GVHD:TrầnThịHương
NHÓM 6

1.
2.
3.
4.
5.
6.

NguyễnVânYến
NguyễnThịHiền
LưVănAn
NguyễnTrungHiếu
ĐỗDanhHoàng
DươngThịPhượng

Nộidungthảoluận.

1.
2.
3.
4.
5.

Thuậttoánduyệttheochiềusâu
Thuậttoánduyệttheochềurộng
ThuậttoánKruskal
ThuậttoánPrim
ThuậttoánDijkstra

1.Thuậttoántìmkiếmduyệttheochiềusâu

Ýtưởng

DFS trên đồthịvôhướng
cũnggiốngnhưkhámphámêcungvớimộtcuộnchỉvàmộtthùngsơnđỏđểđánhdấu,tránhbịlạc.Trongđómỗi đỉnh
s trongđồthịtượngtrưngchomộtcửatrongmêcung.

Tabắtđầutừ đỉnh s,buộcđầucuộnchỉvào s vàđánhđấu đỉnh này "đãthăm".Sauđótađánhdấu s là đỉnh hiệnhành u.
Bâygiờ,nếutađitheo cạnh (u,v) bấtkỳ.
Nếu cạnh (u,v) dẫnchúngtađến đỉnh "đãthăm" v,taquaytrởvề u.
Nếu đỉnh v là đỉnh mới,tadichuyểnđến v vàlăncuộnchỉtheo.Đánhdấu v là "đãthăm".Đặt v thành đỉnh
hiệnhànhvàlặplạicácbước.

1.Thuậttoántìmkiếmduyệttheochiềusâu

Cuốicùng,tacóthểđiđếnmột đỉnh màtạiđótấtcảcáccạnhkềvớinóđềudẫnchúngtađếncác đỉnh
"đãthăm".Khiđó,tasẽquayluibằngcáchcuộnngượccuộnchỉvàquaylạichođếnkhitrởlạimột đỉnhkề vớimột
cạnh cònchưađượckhámphá.Lạitiếptụcquytrìnhkhámphánhưtrên.

Khichúngtatrởvề s vàkhôngcòn cạnh nàokềvớinóchưabịkhámphálàlúc DFS dừng.

1.Thuậttoántìmkiếmduyệttheochiềusâu

Giảithuật
void DFS(intv)
{
intu;
for(u=0;u<n;u++)
if(chuaxet[u]==0&&(a[u][v]==1))
{
chuaxet[u]=1;
DFS(u);
 

2.Thuậttoánduyệttheochiềurộng

Ýtưởng
•Sửdụng1hàngđợiđểlưutrữcácđỉnhsẽđượcduyệt.
•Banđầuđưađỉnhbắtđầuduyệtuvàohàngđợi.
•Thựchiệnquátrìnhlặpchođếnkhihàngđợirỗng.Mỗibướclặplàmnhưsau:
-Lấy1đỉnhvrakhỏihàngđợi.Thựchiệncáccôngviệccầnthiếtvớiđỉnhđó.
-Xácđịnhcácđỉnhwkềvớiđỉnhvmàchưaduyệt.
-Đưacácđỉnhwnàyvàohàngđợi.

2.Thuậttoánduyệttheochiềurộng
ThủtụcBFS(u);

DuyệttoànbộđồthịtheothuậttoánBFS:

(*Timkiemtheochieurongbatdautudinhu,cacbienChuaxet,Kela biencucbo*)
Bắtđầu

Bắtđầu

QUEUE:= Ø;

(*khởitạobanđầu*)

QUEUEu; (* nap uvaoQUEUE*)

formọikthuộcV do

Chuaxet[v]:=false;

Chuaxet[k]:=true;

While QUEUE ≠ Ø do

for uthuộV do

Begin

ifChuaxet[u] then BFS(v);

vQUEUE:; (*layp tu QUEUE:*)

Kếtthúc

Tham_dinh(v);
For wlàKe(v) do
IfChuaxet[w] them
Begin
QUEUEw;
Chuaxet[w]:=false;
End;
End;
Kếtthúc

ThuậttoánBFScóđộphứctạp: O(n+m)

3.ThuậttoánKruskal
a.Ýtưởng

-Nạpdầncáccạnhngắnnhấtvàocâykhungnếucạnhấykotạothànhchutrìnhvớicáccạnhđãnạp.
b.Cácbướcthựchiện
Cho G=(X,E)làđồthịliênthông,cótrọngsốnđỉnh
Bước1:Trướchếtchọncạnhnhỏnhấte1trongcáccạnhcủaG.
Bước2:khiđãchọnkcạnhe1,e2,
…,ekthìchọntiếpcanhek+1nhỏnhấttrongcáccạnhcònlạicủaGsaochokhôngtạothànhchutrìnhvớicáccạn...
BÀI THẢO LUẬN
MÔN TOÁN RỜI RẠC
BÀI THẢO LUẬN
MÔN TOÁN RỜI RẠC
Bài thảo luận môn toán rời rạc - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Bài thảo luận môn toán rời rạc - Người đăng: Cô Út
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
16 Vietnamese
Bài thảo luận môn toán rời rạc 9 10 556