Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Thuật toán BFS

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    3

    Mặc định Thuật toán BFS

    Mình chưa hiểu về thuật toán tìm kiếm theo chiều rộng Breadth First Search.Bạn nào rành thì giúp mình với.

    - VISITED(v):=1
    - Khởi tạo queue với v đã được nạp vào
    - while Q không rỗng do begin
    call CQDELETE(v,Q); {lấy đỉnh v ra khỏi Q}
    for mỗi đỉnh w lân cận với v do
    if VISITED(w):=0 then begin
    call CQINSERRT (w,Q);
    end;
    end;
    - return
    Đã được chỉnh sửa lần cuối bởi johansen : 12-11-2007 lúc 10:47 PM.

  2. #2
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Á à. Cái này thì cậu phải hiểu nó đã, còn chuyện code thì bàn sau:

    Đầu tiên cậu đưa 1 thèng vào Queue (Q).
    Trong khi Q không rỗng.
    Lấy Trong Q ra 1 thèng k.hiệu v.
    Tìm tất cả các phần tử có thể có từ v. Đưa vào queue

    Khi Q rỗng thì cũng là lúc BFS hoàn thành.

    Về nguyên tắc thì cậu coi BFS như 1 cây. Đầu tiên đưa ROOT vào, lấy tất cả các phần tử liên thông với ROOT. Trong mỗi phần tử đó lại xem nó như ROOT và tiếp tục.

    Code thì xem sách hoặc tớ sẽ gởi sau.

  3. #3
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bạn coi bằng hình thì sẽ dễ hiểu hơn :

    Đầu tiên từ đỉnh gốc có mày đen, nó sẽ bắt đầu xét lên đến các đỉnh con, cứ thế cho đến khi không còn đỉnh nào để xét nữa. Và vì sao nó liên hệ đến hàng đợi thì bạn xem hình sau :

    Nó để dỉnh đầu vào queue rồi đấy.

    Để ý cái màu đen là đỉnh của đồ thị mà nó đã đi qua.

    Đế ý cái queue bên phải.

    Cứ qua một level sẽ có lượt được đưa vào queue

    Chắc bạn thấy nó vận hành thế nào rồi chứ gì ^^!




    lúc này bạn thấy không, các đĩnh đã được xét hết, queue cũng sạch ^^ ! xong rùi đó.
    Chú ý hình trên, các số là đánh dấu từng level của nó, cứ hình dung như cái cây có cắt nhánh con thế, và chữ cái chính là tên của mỗi đỉnh con đó thôi.
    Các cạnh chính là có đường liên thông giữa 2 đỉnh đó, nếu không có cạnh tức là không có đường !
    Bạn tham khảo cái này, mình copy từ chuyên đề đồ thị của tác giả Lê Minh Hoàn đó, rất dễ hiểu.
    Cơ sở của phương pháp cài đặt này là lập lịch duyệt các đỉnh. Việc thăm 1 đỉnh sẽ lên lịch duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng.( Đỉnh nào gần S hơn sẽ được duyệt trước ) ví dụ : bắt đầu ta thăm đỉnh S. Việc thăm đỉnh S sẽ phát sinh ra thứ tự duyệt các đỉnh kề sách ( ở hình trên là r, w ) –những đỉnh gần S nhất. Khi thăm đỉnh r hoặc w lại phát sinh ra các đỉnh con của chúng nữa…Nhưng thứ tự là từ trái qua phải.
    Giả sử ta có 1 danh sách chứa những đỉnh đang chờ thăm. Tại mỗi bước, ta thăm đỉnh đầu danh sách và cho những đỉnh chưa xếp hàng kề với nó xếp hàng thêm vào cuối danh sách. Chính cũng vì nguyên tắc này nên danh sách chưa các đỉnh đang chờ sẽ được tổ chức dưới dạng hành đợi ( Queue )
    Nếu ta có Queue là 1 hàng đợi với thủ tục Push ( v) để đẩy 1 đỉnh v vào hàng đợi và hàm Pop trả về 1 đỉnh lấy ra từ hàng đợi thì mã giả có thể viết như sau :
    Với mọi đỉnh v thuộc đồ thị Free[v] = true;
    Free[S] = False; /*Khởi tao ban đầu chỉ có 1 đỉnh S bị đánh dấu*/
    Queue = rỗng; Push(S); /* Khởi tạo hàng đợi ban đầu chỉ có 1 đỉnh S*/
    Do ( lập cho tới khi hàng đợi rỗng )
    u = Pop ( Lấy hàng đợi ra 1 đỉnh u )
    for ( với mọi v thuộc V )
    if ( Free[v] = true và (u,v) thuộc đồ thị )
    Trace[v] = u; /*lưu vết đường đi*/
    Free[v] = False; /*Đánh dấu đã thăm đỉnh v*/
    Push(v); /*Đẩy v vào hàng đợi*/
    While ( Queue = rỗng )

  4. #4
    Ngày gia nhập
    11 2007
    Bài viết
    3

    C++ Code:
    1. #include "stdafx.h"
    2. #include "stdio.h"
    3. #include "memory.h"
    4. #include "conio.h"
    5. #define MaxV 20 //Define su dung cho so dinh cuc dai cua do thi
    6. int A[MaxV][MaxV]; //Ma tran ke
    7. int V = 0; //So dinh cua do thi
    8. int ChuaXet[MaxV];
    9.  
    10. //Thu tuc nhap matran ke bang ban phim.
    11. void NhapMTKe(int A[][MaxV], int &V)
    12. {
    13. printf("Nhap V:");
    14. scanf("%d", &V);
    15. for (int i=0; i<V; i++)
    16. {
    17. for (int j=0; j<V; j++)
    18. {
    19. printf("A[%d,%d] = ", i+1, j+1);
    20. scanf("%d", &(A[i][j]));
    21. }
    22. }
    23. }
    24. void XuatMTKe(int A[][MaxV], int V)
    25. {
    26. printf("\nMa tran ke:\n");
    27. for (int i=0; i<V; i++)
    28. {
    29. for (int j=0; j<V; j++)
    30. printf("%3d ", A[i][j]);
    31. printf("\n");
    32. }
    33. }
    34. int DocMTKe(char *fileName, int A[][MaxV], int &V)
    35. {
    36. FILE *f = fopen(fileName, "rt");
    37. if (f == NULL)
    38. {
    39. printf("Doc file loi !!!");
    40. return 0;
    41. }
    42.  
    43. fscanf(f, "%d", &V);
    44. for (int i=0; i<V; i++)
    45. {
    46. for (int j=0; j<V; j++)
    47. {
    48. fscanf(f, "%d", &(A[i][j]));
    49. }
    50. }
    51. return 1;
    52. }
    53.  
    54. /*Thu tuc duyet BFS, duyet theo chieu rong su dung QUEUE de chay khong de quy.*/
    55. void BFS0DeQuy(int v)
    56. {
    57. int QUEUE[MaxV], topQ=0, bottomQ=0; //Khoi dau voi mot QUEUE rong
    58. QUEUE[topQ++] = v; //Dua dinh v vao QUEUE, xem no nhu la da xet
    59. ChuaXet[v] = 1;
    60. while ( bottomQ < topQ ) //Lap trong khi QUEUE khac rong
    61. {
    62. v = QUEUE[bottomQ++]; //Lay dinh v tu day cua QUEUE
    63. for (int u=0; u<V; u++)
    64. if ( A[v][u] != 0 ) //The hien u ke voi dinh v
    65. if ( ChuaXet[u]==0 )
    66. {
    67. QUEUE[topQ++] = u; // Dua u vao dinh cua QUEUE
    68. ChuaXet[u] = 1;
    69. }
    70. }
    71. }
    72. */
    73.  
    74. int main(int argc, char* argv[])
    75. {
    76. int j;
    77. NhapMTKe(A, V);
    78. //DocMTKe("D:\\Dothi_1.txt", A, V);
    79.  
    80. XuatMTKe(A,V);
    81. memset(ChuaXet, 0, sizeof(ChuaXet) );
    82. DFS0DeQuy(0);
    83. printf( "Cac dinh da duyet: " );
    84. for(j=0;j<V;j++)
    85. if (ChuaXet[j] == 1)
    86. printf( "%d ", j+1 );
    87. getch ( );
    88. return 1;
    89. }

    Ai giúp mình với. Sao mình dùng code này mà chương trình ko chạy vậy??
    Đã được chỉnh sửa lần cuối bởi johansen : 14-11-2007 lúc 10:06 AM.

  5. #5
    Ngày gia nhập
    11 2007
    Bài viết
    1

    ai giúp mình nhé.Mình đang cần code để vẽ cây nhi phân ra man hình

Các đề tài tương tự

  1. Dịch thuật, công ty dịch thuật, dịch vụ dịch thuật chuyên nghiệp
    Gửi bởi vecvn trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 4
    Bài viết cuối: 18-11-2012, 10:44 PM
  2. Dịch vụ kế toán: Báo cáo thuế, dịch vụ tư vấn thuế, báo cáo thuế tncn vnnp
    Gửi bởi ecomvnnp01 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 1
    Bài viết cuối: 16-02-2012, 11:07 AM
  3. Bài tập C++ Viết chương trình nhập số lượng hàng hóa, giá cả, thuế, xuất ra tổng giá, thuế, tổng cộng
    Gửi bởi seit trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 04-03-2011, 09:04 AM
  4. Hướng dẫn kê khai thuế thu nhập cá nhân, thuế doanh nghiệp 0903034381
    Gửi bởi thngxanhcty trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 19-05-2010, 02:33 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn