Toan Roi Rac Tim Duong Di

 Tìm đuờng đi giữa 2 đỉnh trên đồ thị

Khi đó, DFS(int v){

Chuaxet[v]:=false;

For(u Є ke(v)) { // thuộc

If (chuaxet[u]) {

Truoc[u]=v;

DFS(u);

}

}

Đối với BFS thì ta thay đổi như sau:

Void BFS(int u){

Queue =”rỗng”;

U <- queue; // nạp u vào hàng đợi

Chuaxet[u]=false; // đổi trang thái của u

While(queue ≠”rỗng”){//duyệt tới khi nào hàng đợi rỗng

Queue <- p; //lấy p ra khỏi hàng đợi

For(v Є ke(p) ) {  //đưa các đỉnh v kề với p nhưng chưa đuợc xét vào hàng đợi

If(chuaxet[v] ) {

V<- queue; //đưa v vào hàng đợi

Chuaxet[v]=false;//đổi trạng thái của v;

Truoc[v]=p;

}

}

}//end while

}//end bfs 

Kết quả đuờng đi đọc ngược lại

Void result(void){

If(truoc[t]=0){

<không có đường đi từ s đến t>;

Return;

}

J=t;

While(truoc[j]≠s){

<thăm đỉnh j>;

J=truoc[j];

}

<thẳm đỉnh s>;

loading...