Cung giai de thi thuc hanh nao cac ban ^^

_ Bữa nay mình không được vào thi nên không rõ có bao nhiêu đề, bạn nào nhớ đề mình đã làm thì vào đây post lên để mọi người cùng giải nha, tuy thi xong rồi nhưng cũng nên từ đó rút ra những kinh nghiệm bổ ích.
_ Mình nghe nói là bữa nay có đề "Tìm đường đi ngắn nhất giữa 2 đỉnh (dùng BFS)", bài này thì đã có nhiều bạn đưa code lên diễn đàn rồi & hầu như đều sử dụng Danh sách liên kết để giải quyết. Với bài toán này chúng ta có thể viết toàn bộ giải thuật BFS mà thầy đã cho, sau đó chỉ việc sử dụng mảng d[] trong mã để lấy ra đường đi ngắn nhất giữa 2 đỉnh. Tuy nhiên mình có một ý kiến rằng chúng ta có thể sửa lại mã thầy cho để tạo thành một hàm BFS() trả về đường đi ngắn nhất giữa 2 đỉnh.
_ Mã giả như sau :

Code:

int BFS(G,v1,v2)
{
   for each vertex u ε V[G] - {v1}
      do color[u] <- WHITE
         d[u]   <- ∞
         П[u] <- NIL
   color[v1] <- GRAY
   d[v1] <- 0
   П[v1] <- NIL
   Q <- Ø
   ENQUEUE(Q,v1)
   Do u <- DEQUEUE(Q)
      for each v ε Adj[u]
         do if color[v] <- WHITE
            then color[v] <- GRAY
               d[v] <- d[u] + 1
               П[v] <- u
               ENQUEUE(Q,v)
      color[u] <- BLACK
   while (v != v2)
   return d[v2]
}


_ Ta có thể sử dụng mảng một chiều để tạo hàng đợi dùng cho giải thuật BFS, khi đó các bạn sẽ không phải đụng đến con trỏ hay danh sách liên kết làm gì cho rắc rối

Đề số 2 đó bạn. dùng BFS để tìm đường đi ngắn nhất nhưng kết quả là khoảng cách giữa 2 đỉnh của đồ thị. Ví dụ từ đỉnh 2 đến đỉnh 5 là bằng 2. Theo bài của thầy thì chúng ta in ra đường đi nghĩa là đường đi ngắn nhất trường hợp đề cho là 2 -> 1-> 5. Mình làm tới đây chưa kịp làm tính khoảng cách không biết có được điểm hok nữa.
hi vọng là thầy bỏ qua cho thiếu sót

Phần tính đường đi từ đỉnh s đến đỉnh t cực kỳ đơn giản.
Trong giải thuật ta có lưu mảng đường đi d[i]. Chỉ cần xuất cái d[t] ra là ok.

Đề 2 tương đối đơn giản.
Đề 1 thì hơi cay tí xíu nhưng cũng ko quá khó, cách dễ làm nhất là lưu đồ thị kq (cây khung sau khi áp dụng Prim) sang 1 ma trận kề tạm, rồi tính tổng các a[i][j]!=0 thuộc tam giác trên đường chéo chinh (ma trận ban đầu) = tổng trọng số của đồ thị. Tương tự tính tổng các tam[i][j] thuộc tam giác trên đường chéo chinh (ma trận tạm)= tổng trọng số của cây khung.
Xong rùi chia % là ok.