Thuật Toán Bfs Là Gì

Bởi

Nơi tổng hợp và chia sẻ kiến ​​thức liên quan đến thuật toán nói chung và lý thuyết tin học nói riêng.

Đang xem: Bfs là gì

Đồ thị — Giới thiệu về Lý thuyết đồ thị thuật toán

Tháng Chín 26, 2015 in Chưa được phân loại | Miễn bình luận

Trong loạt bài này và các bài tiếp theo chúng ta sẽ làm quen với đồ thị và các thuật toán với đồ thị. Graph là một đối tượng tổ hợp đã được nghiên cứu và ứng dụng rất nhiều trong thực tế (có lẽ viết cái này hơi thừa). Trong phần này chúng ta sẽ:

Làm quen với các khái niệm cơ bản liên quan đến đồ thị Cách biểu diễn đồ thị trong máy tính để chúng ta có thể thao tác với nó.

Độc giả có thể bỏ qua những phần đã quen thuộc. Ghi chú của Jeff Erickson vẫn là tài liệu tham khảo chính cho bài viết này.

Khái niệm

Một đồ thịký hiệu là $G(V,E)$, gồm 2 thành phần:

Tập hợp $V$, bao gồm các đối tượng, được gọi là tập hợp các đỉnh (đỉnh) của đồ thị Tập hợp $E subseteq V^2$, bao gồm một cặp đỉnh, được gọi là tập hợp các cạnh (đỉnh). ) của đồ thị

Chúng ta sẽ ký hiệu $n,m$ là số đỉnh và số cạnh của đồ thị, nghĩa là $|V| = n, |E|= m$. Số đỉnh trong một đồ thị đôi khi còn được gọi là . bậc của đồ thị (thứ tự của đồ thị).

Các đỉnh chúng ta sẽ biểu thị bằng các chữ thường như $u,v,x,y,z$. Cạnh giữa hai đỉnh $u,v$ có thể là không phương hướng hoặc có hướng. Trong trường hợp đầu tiên, chúng ta sẽ biểu thị cạnh là $uv$, và trong trường hợp sau, chúng ta sẽ biểu thị nó là $u
ightarrow v$ để chỉ định hướng của cạnh từ $u$ đến $v$. Thông thường khi chúng ta nói cạnh, chúng ta muốn nói đến cạnh vô hướng và đối với cạnh có hướng, chúng ta sẽ gọi nó là cạnh cây cung (cung). Hình $(1,2)$ của hình bên dưới biểu thị một đồ thị vô hướng (các cạnh là vô hướng) và hình $(3)$ của hình bên dưới biểu thị một đồ thị có hướng.

Một đồ thị vô hướng được gọi là liên thông nếu tồn tại đường đi giữa mọi cặp điểm. Một đồ thị có hướng được liên thông (yếu) nếu đồ thị vô hướng thu được từ đồ thị bằng cách bỏ qua hướng của cạnh được kết nối. Đồ thị có hướng được gọi là kết nối mạnh mẽ (liên thông mạnh) nếu tồn tại một đường đi có hướng giữa mọi cặp điểm. Rõ ràng, nếu một đồ thị có hướng liên thông mạnh thì nó cũng liên thông yếu. Tuy nhiên, điều ngược lại chưa chắc đã đúng (ví dụ?). Ví dụ: đồ thị $(1)$ bên dưới không liên thông, đồ thị $(2)$ liên thông, đồ thị $(3)$ liên thông yếu (nhưng không mạnh) và đồ thị $(4)$ liên thông . giao tiếp mạnh mẽ.

*

Bạn cũng có thể kết hợp biểu diễn danh sách kề với một số cấu trúc dữ liệu khác. Cụ thể, thay vì sử dụng danh sách liên kết để biểu diễn các đỉnh liền kề với đỉnh $u$, chúng ta cũng có thể sử dụng bảng băm hoặc cấu trúc cây để biểu diễn nó. Trong khuôn khổ các bài viết ở đây, chúng tôi ít sử dụng (hoặc không sử dụng) các cấu trúc như vậy.

Xem thêm bài viết hay:  Biệt Nữu Là Gì - Thuật Ngữ Viết Tắt Trong Đam

Ngoài ra, chúng ta có thể biểu diễn đồ thị bằng cách liệt kê tất cả các cặp $(u,v)$ thỏa mãn $uv trong E$. Biểu diễn này có bộ nhớ $O(m)$. Tuy nhiên, việc thực hiện các thao tác cơ bản trong biểu diễn này sẽ rất tốn kém. Đôi khi có thể kết hợp biểu diễn này với biểu diễn danh sách kề để tận dụng lợi thế của cả hai biểu diễn trong khi bộ nhớ vẫn tuyến tính.

Duyệt đồ thị

Vấn đề 1: Cho một đồ thị $G(V,E)$ và một đỉnh $s trong V$, in các đỉnh $v$ sao cho tồn tại một đường đi từ $s$ đến $v$.

Chúng ta gọi bài toán trên là bài toán duyệt đồ thị từ một đỉnh $s$. Để đơn giản, chúng ta sẽ giả sử rằng đồ thị là liên thông. Trường hợp đồ thị không liên thông sẽ được mở rộng ở cuối phần này. Cách chung để duyệt đồ thị như sau: Chúng ta sẽ sử dụng hai loại nhãn để gán cho các đỉnh của đồ thị: chưa đến thăm (chưa ghé thăm) và đã đến thăm (đã viếng thăm). Ban đầu tất cả các đỉnh được đánh dấu là chưa được thăm. Chúng ta sẽ duy trì một set $C$ (cách triển khai set $C$ chúng ta sẽ tìm hiểu sau), ban đầu rỗng. Chúng ta sẽ lặp lại 2 bước sau:

Nhận một đỉnh $u$ trong $C$ (thủ tục Remove$(C)$ bên dưới). Đánh dấu $u$ là đã truy cập. Đặt các lân cận của $u$ với các nhãn chưa được thăm trong $C$. Thủ tục Add$(C,v)$ dưới đây sẽ đưa đỉnh $v$ vào tập hợp $C$.

Thuật toán dừng khi $C = emptyset$. Mã giả như sau:

GenericGraphTraverse($G(V,E),s$): đánh dấu tất cả các đỉnh không được viếng thăm Thêm$(C,s)$ trong khi $C
ot= tập rỗng$ $u leftarrow$ Xóa$(C)$ $ll gg$ nếu $u$ là không được viếng thăm đánh dấu $u$ đã truy cập cho tất cả $uv trong E$ và $v$ không được truy cập $ll(**)gg$

Thêm$(C,v)$ Nhận xét: Một đỉnh có thể được bao gồm nhiều lần trong tập hợp $C$ (vì vậy $C$ không nhất thiết phải là một tập hợp vì nó có nhiều phần tử giống nhau). Ví dụ, xét ba đỉnh kề nhau $u,v,w$. Đỉnh $u$ được lấy ra từ đỉnh $C$ đầu tiên; đánh dấu $u$ là đã truy cập. Chẳng bao lâu nữa, $v$ và $w$ sẽ được đưa vào $C$. Tiếp theo, lấy $v$ ra khỏi $C$ và đánh dấu $v$ là đã truy cập. Bây giờ chúng ta tiếp tục đặt $w$ vào $C$ một lần nữa vì theo mã giả trên, $w$ là hàng xóm của $v$ và có nhãn không được thăm. Ở đây, tôi sẽ không

kiểm tra xem một đỉnh đã có trong $C$ chưa trước khi đưa nó vào $C$.

Từ mã giả trên, chúng ta thấy rằng tập hợp $C$ lưu trữ các đỉnh liền kề với ít nhất một đỉnh được thăm.

Xem thêm: “tất cả các cách” Về Phong Thủy Phòng Khách, 14 Lưu Ý Phong Thủy Phòng Khách Ít Người Biết Phân tích thuật toán:

Xem thêm bài viết hay:  Định luật Murphy là gì? Trong cái rủi có cái xui

Giả sử rằng chúng ta sử dụng một cấu trúc để triển khai $C$ sao cho việc thêm hoặc lấy bất kỳ đỉnh nào (dòng $

$ và dòng cuối cùng) được thực hiện trong thời gian $O(1)$ (ví dụ: nếu $C$ được triển khai với danh sách liên kết, việc thêm hoặc xóa đỉnh ở đầu danh sách có thể được thực hiện trong thời gian ngắn. thời gian $O(1)$). Chúng tôi có một vài quan sát:

Các đỉnh đã bị xóa khỏi $C$ và được đánh dấu là đã truy cập sẽ không bao giờ được trả về tập hợp $C$. Mỗi khi đỉnh $v$ được chèn vào $C$, một đỉnh lân cận của nó sẽ được đánh dấu là đã thăm. Do đó, đỉnh $v$ sẽ được chèn vào $C$ không quá $d(v)$ lần. Mỗi khi chúng ta lấy một đỉnh $u$ ra khỏi $C$, chúng ta sẽ đi qua tất cả các lân cận của $u $. Thao tác này mất $O(d(u))$ thời gian. Theo nhận xét 1, việc truyền tải này chỉ có thể được thực hiện nhiều nhất một lần.

Từ nhận xét trên, ta suy ra tổng thời gian tính toán của thuật toán là $O(sum_{u in V}d(u)) = O(m)$. Trong trường hợp đồ thị không liên thông, ta phải duyệt lần lượt các thành phần liên thông. Vì đồ thị có tối đa $n$ thành phần liên thông nên ta có: Nếu chúng ta triển khai $C$ với danh sách liên kết thì chắc chẳng có gì thú vị. Tuy nhiên, nếu chúng ta triển khai $C$ với hàng đợi hoặc ngăn xếp, chúng ta sẽ nhận được một số thuộc tính thú vị từ biểu đồ. Trong trường hợp chúng tôi thực thi $C$ bằng hàng đợi, chúng tôi gọi thuật toán duyệt theo chiều rộng (Tìm kiếm hơi thở đầu tiên – BFS). Trong trường hợp chúng tôi thực thi $C$ trên ngăn xếp, chúng tôi gọi thuật toán

duyệt theo chiều sâu

(Tìm kiếm theo chiều sâu – DFS). Sau đây chúng ta sẽ thảo luận về cả hai thuật toán.Thuật toán duyệt theo chiều rộng đầu tiên BFSNhư đã đề cập ở trên, thuật toán BFS sẽ thực thi $C$ bằng cách sử dụng hàng đợi. Chúng ta sẽ thay thủ tục Add$(C,v)$ bằng thủ tục Enqueue$(C,v)$ và thủ tục Remove$(C)$ bằng thủ tục Dequeue$(C)$. Ngoài khung cơ bản như thuật toán trên, ta sẽ gán cho mỗi đỉnh $v$ một nhãn $d

$. Giá trị của $d $, như chúng tôi sẽ chỉ ra bên dưới, là khoảng cách ngắn nhất từ ​​$s$ đến $v$. Mã giả như sau: BFS($G(V,E),s$): cho mỗi $v bằng V$ $d leftarrow +infty$ $Cleftarrow$ một Hàng đợi trống Enqueue$(C,s)$ $d
mũi tên trái 0$ trong khi $C ot= tập rỗng$ $u leftarrow$ Dequeue$(C)$ nếu $u$ là không được viếng thăm đánh dấu $u$ đã truy cập cho tất cả $uv trong E$ và $v$ không được truy cập $ll(**)gg$Enqueue$(C,v)$ $d

mũi tên trái d

+1$
Mã giả mã trong C: #define UNVISITED 0#define VISITED 1#define TRUE 1#define FALSE 0#define INFTY 1000000 // cấu trúc dữ liệu danh sách đỉnh, nó là một listtypedef struct vlist được liên kết{int v; // đỉnh v kề với chỉ số của liststruct vlist *next;}vlist;vlist **G;int n; // số veritcesint m; // số lượng edgeint *D; // khoảng cách các đỉnh từ dấu BFSint*; // một mảng để đánh dấu các đỉnh đã truy cậptypedef struct Queue{int *storage;int back, front;}Queue;void bfs(int s){printf(“executing bfs….. “;D = (int *)(malloc(n*sizeof(int)));int i = 0;for(; iv;if(mark)== CHƯA ĐƯỢC THAM QUAN){ DỄ DÀNG
= DỄ DÀNG+1;enqueue(Q,v);}runner = runner->next;}}}printf(“xong bfs
“);}////////////////////////////////////////////// ///////////////////////////////////////////////// / /////////////////////////////////////////////// HÀNG ĐỢI GIAO DIỆN//////////////////////////////////////////////// ///////////////////////////////////////////////// ///////////////////////////////Queue *init_queue(int size){Queue *Q = malloc(sizeof(Queue)); Q ->storage = (int *)malloc(size*sizeof(int));Q->front = 0;Q->back = -1;return Q;}void enqueue(Queue *Q, int elem){Q -> quay lại ++;Q->lưu trữback> = elem;}int dequeue(Queue *Q){if(is_queue_empty(Q)) { printf(“không có gì để dequeue

Xem thêm bài viết hay:  Định Lí Sin Trong Tam Giác Là Gì? Định Lí Sin Vận Dụng Lúc Nào?

“);exit(0);}int elem = Q->storage” /></p> <p>front>;Q->front++;return elem;}int is_queue_empty(Queue* Q){return Q->back front? TRUE : FALSE;} Ví dụ chúng ta thực hiện thuật toán trên với đồ thị ở hình bên trái và kết quả ở hình bên phải. Các số tương ứng với các đỉnh tương ứng là nhãn của các đỉnh đó. Các cạnh màu đỏ đại diện cho các cạnh mà $v$ có nhãn chưa được truy cập trên dòng $(**)$ được BFS truy cập.</p> <p>*</p> <p>Ngoài thủ tục lặp DFS sử dụng ngăn xếp như trên, có lẽ ai trong chúng ta cũng khá quen thuộc với thủ tục thực hiện DFS đệ quy sau:<br />Mã giả với<s> void recursive_dfs(int s){printf(“đang truy cập %d</s></p> <p><strong>“,s);đánh dấu</strong></p> <p>= ĐÃ THAM QUAN; // lặp qua các láng giềng của sint v = 0;for(; v Ta thấy cách thứ hai đơn giản hơn vì không phải thực thi Stack. Tuy nhiên, cách này sẽ sử dụng nhiều Call Stack của máy tính và trong trường. Đệ quy lớn kết hợp độ sâu có thể gây ra Stack Overflow.</p> <p> Phát hiện các thành phần được kết nối<b> Một trong những ứng dụng đơn giản nhất để duyệt đồ thị là khám phá các thành phần được kết nối. Để khám phá các thành phần liên thông của đồ thị (vô hướng), ta lặp lại thao tác sau: chọn một đỉnh chưa thăm $u$ và thực hiện thăm các đỉnh trong thành phần liên thông chứa $u$. Quy trình sau đây trả về số lượng thành phần liên thông của đồ thị đầu vào $G(V,E)$.</b> ConnecteComponents($G(V,E)$): đánh dấu tất cả các đỉnh chưa được thăm $count leftarrow 0$ cho tất cả các đỉnh $sin V$</p> <p>nếu</p> <p>$s$ chưa được truy cập GraphTraversal($G(V,E),s$) > $countleftarrow count+1$ return $count$<strong>Mã C:</strong></p> <p> int connect_component(){memset(mark, UNVISITED, (n+1)*sizeof(int)); // đánh dấu tất cả các đỉnh unvisitedint s = 0;int count = 0;for(; s Mã đầy đủ: biểu diễn danh sách, biểu diễn ma trận.</p> <p>Tham khảo</p> <p> Jeff Erickson, Ghi chú bài giảng đồ thị, UIUC. Diesel, Reinhard. Lý thuyết đồ thị. 2005. Tốt nghiệp. Văn bản trong Toán học (2005).</p> <p>Xem thêm: Trường năng lượng vũ trụ là gì, Trường năng lượng vũ trụ là gì? Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (2nd ed.), Chương 23. MIT Press và McGraw-Hill (2001). ISBN 0-262-03293-7.</p> <p>Bạn thấy bài viết <b>Thuật Toán Bfs Là Gì</b> có khắc phục đươc vấn đề bạn tìm hiểu ko?, nếu ko hãy comment góp ý thêm về Thuật Toán Bfs Là Gì bên dưới để <a href=duhoc-o-canada.com có thể thay đổi & cải thiện nội dung tốt hơn cho các bạn nhé! Cám ơn bạn đã ghé thăm Website: duhoc-o-canada.com của duhoc-o-canada.com

Nhớ để nguồn bài viết này: Thuật Toán Bfs Là Gì của website duhoc-o-canada.com

Chuyên mục: Là gì?

Viết một bình luận