Lý thuyết đồ thị c++

Trong tân oán học tập cùng tin học, thiết bị thị là đối tượng người tiêu dùng nghiên cứu và phân tích cơ bạn dạng của triết lý đồ vật thị. Một phương pháp ko chấp nhận, đồ vật thị là 1 trong tập các đối tượng hotline là đỉnh nối cùng nhau vì chưng các cạnh. Thông thường, đồ vật thị được vẽ dưới dạng một tập các điểm (đỉnh, nút) nối cùng nhau vày các đoạn thẳng (cạnh). Tùy theo ứng dụng nhưng một vài cạnh rất có thể được bố trí theo hướng.

You watching: Lý thuyết đồ thị c++

Sơ lược những quan niệm cơ bản về đồ dùng thị

Một bí quyết ko chấp thuận, đồ gia dụng thị là 1 tập những đối tượng người tiêu dùng được Call là các đỉnh nối cùng nhau vì những cạnh.

Một đồ thị kí hiệu là

Trong đó:

( V ) là tập các đỉnh của đồ vật thị. Đặt ( mid V mid = n ) (số đỉnh).

( E ) là tập các cạnh của vật thị. Đặt ( mid E mid = m ) (số cạnh).

*

Đỉnh:

Đỉnh màn biểu diễn các đối tượng người dùng trong đồ thị, thường xuyên được ghi lại bởi những số hoặc kí hiệu bằng các vần âm in thường u,v,…

Cạnh:

Cạnh nối đỉnh x với đỉnh y là một trong những tập gồm hai thành phần ( x, y ), thường xuyên được vẽ dưới dạng một đoạn thẳng nối hai đỉnh.

Cạnh được đặt theo hướng (cung):

Là một cặp đỉnh bao gồm máy từ bỏ. Trong mỗi cặp bao gồm sản phẩm trường đoản cú đó, đỉnh trước tiên được Gọi là đỉnh đầu, đỉnh thiết bị nhị là đỉnh cuối.

Cạnh vô hướng:

Không quan tâm đến phía cùng coi hai đỉnh đồng nhất.

Khuyên:

Là một cạnh nối một đỉnh với chính nó.

Hai cạnh song song:

Là nhị cạnh cùng nối nhì đỉnh u, v.

Đồ thị bao gồm hướng:

Là đồ dùng thị mà tất cả những cạnh trong vật thị đều sở hữu hướng.

Đồ thị vô hướng:

Là đồ gia dụng thị mà tất cả các cạnh trong vật thị đông đảo vô hướng.

Đơn đồ gia dụng thị:

Là thứ thị không tồn tại khulặng với không có cạnh song tuy nhiên.

Đa vật dụng thị:

Là đồ thị không phải là đối kháng trang bị thị.

See more: Hướng Dẫn Crack Teamviewer 11 12 13 14 Full Crack Mới Nhất, Các Phiên Bản Trước Của Teamviewer

Bậc:

Trong đồ vật thị vô hướng, bậc của đỉnh v vào đồ vật thị G, ký kết hiệu ( d_G(u) ), là số cạnh liên nằm trong với v, trong các số đó, khulặng được xem nhị lần.

Ta có định lí:

Giả sử ( G=(V, E) ) là vật thị vô hướng, lúc đó tổng các bậc đỉnh vào V vẫn bởi gấp đôi số cạnh.

Hệ quả: Trong thiết bị thị vô phía, số đỉnh bậc lẻ là chẵn.

Trong đồ gia dụng thị có hướng, ta khái niệm chào bán bậc ra của u là số cung đi thoát khỏi nó, kí hiệu ( d^+_G(u) ), chào bán bậc vào của u là số cung đi thoát ra khỏi nó, kí hiệu ( d^-_G(u) ).

Giả sử ( G=(V, E) ) là vật thị có hướng, lúc ấy tổng những phân phối bậc vào bằng tổng các bán bậc ra cùng thông qua số cung của đồ gia dụng thị.

Đường đi cùng chu trình:

Một dãy các đỉnh P.. = (p0,p1,…,pk) sao cho (Pi-1, Pi) ∊ E, ∀i: 1Biểu diễn đồ dùng thị trên thiết bị tính:

Có những cách để biểu diễn thứ thị trên máy tính, tùy trực thuộc vào đặc thù của thứ thị hoặc thuật toán vận dụng với thứ thị… Ta cũng hoàn toàn có thể lưu giữ cố nhiên các công bố nhỏng trọng số, giá trị phù hợp cùng với từng cạnh. Dưới đây là một vài biện pháp thịnh hành.

Ma trận kề:

Tạo một ma trận A form size n*n trong những số ấy n là số đỉnh của đồ thị. Ta gán a = 0 nếu như tất cả cạnh cạnh nối nhị đỉnh u, v.

Nếu đồ dùng thị là đa thứ thị, ta hoàn toàn có thể gán a = số cạnh nối u và v.

Định nghĩa với gán tùy thuộc vào lập trình viên gọi là vô hướng hay được đặt theo hướng, solo thiết bị thị tốt đa thứ thị.

Ưu điểm: Để bình chọn hai đỉnh u, v tất cả kề nhau không, ta chỉ cần đánh giá trong độ phức tạp ( O(1) ). Nhược điểm: Dù đồ gia dụng thị có nhiều cạnh tuyệt ít cạnh thì cũng yêu cầu mất n*n ô lưu giữ nhằm lưu. Để chăm chút tất cả các đỉnh kề với u, ta bắt buộc thông qua toàn bộ những đỉnh v ∊ V mặc dù đỉnh u kề với ít hoặc ko kề với đỉnh như thế nào không giống.

Biểu diễn bằng ma trận kề thường được sử dụng lúc đồ gia dụng thị bao gồm không nhiều đỉnh, hoặc vật thị dày, các cạnh, hoặc thuật toán để làm việc bên trên vật thị những hiểu biết.

Danh sách cạnh:

Với đồ gia dụng thị ( G=(V, E) ) tất cả n đỉnh, m cạnh, ta hoàn toàn có thể liệt kê toàn bộ các cạnh của vật thị bằng một list tương xứng, mỗi phần tử của mảng tương xứng là 1 cặp (u,v) là một trong những cạnh nằm trong E, phụ thuộc vào fan xây dựng khái niệm là được bố trí theo hướng xuất xắc vô hướng.

See more: Hàm Sum Không Ra Kết Quả Trong Excel, Sửa Lỗi Hàm Sum Bằng 0 Trong Excel

Ưu điểm: Với vật thị thưa, ta chỉ việc mất m (con số cạnh) ô ghi nhớ để lưu lại vật thị. Nhược điểm: Khi đề xuất đánh giá nhị đỉnh u,v tất cả kề nhau hay không, ta bắt buộc khám nghiệm nhanh khô trong //( O(1) //) nhỏng giải pháp lưu giữ bởi ma trận kề, tuy vậy tùy theo phương pháp lưu giữ list cạnh mà lại ta có thể kiểm soát trong //( O(logn) //) hoặc ít hơn.

Danh sách kề:

Với mỗi đỉnh của đồ gia dụng thị, ta lưu một list các đỉnh kề cùng với đỉnh đó.

Ưu điểm: Với phương pháp này, việc phê duyệt tất cả những đỉnh kề với đỉnh u vô cùng tiện lợi. Nhược điểm: Lúc buộc phải soát sổ nhị đỉnh u,v bao gồm kề nhau hay là không, ta bắt buộc đánh giá nhanh hao trong ( O(1) ) nlỗi cách giữ bởi ma trận kề, mặc dù tùy theo phương pháp lưu list cạnh nhưng ta rất có thể bình chọn vào ( O(logn) ) hoặc thấp hơn.

Phần sau: Phần 2: Tìm tìm theo hướng rộng lớn bên trên vật thị - Breadth-First Search (BFS)


Chuyên mục: Chia sẻ