tìm kiếm thuật toán đồ thị nếu đồ thị được kết nối, lưỡng cực, có chu kỳ và là một cây

Question

Tôi gặp vấn đề khi cố gắng làm việc với biểu đồ và viết mã cho nó nhưng không may mắn:/!!

tôi muốn tạo ra cái gì đó sẽ lấy dữ liệu của đồ thị và kiểm tra xem nó là: 1- kết nối 2- song phương 3 có chu kỳ 4 là một cây

vì vậy tôi đã tự hỏi ví dụ, nếu điều này có thể được viết để đọc một dữ liệu đồ thị từ một tập tin .txt mà sẽ làm các xét nghiệm trên?

sử dụng định dạng danh sách cạnh đơn giản là cách tiếp cận chính xác cho nó?

trợ giúp của bạn được đánh giá cao nếu bạn có thể cung cấp cho tôi liên kết để đọc về cách thực hiện tác vụ này hoặc bắt đầu một cú đá cho mã !!

nhờ: D

Answer 1

kiểm tra nếu nó là:

1. kết nối

Đối với cái này, bạn cố gắng đi qua toàn bộ đồ thị từ một thời điểm, và xem nếu bạn thành công. Cả hai chiều ngang đầu tiên và chiều ngang đầu tiên đều được chấp nhận ở đây. Thuật toán này sẽ chia các nút thành các thành phần:

• đánh dấu tất cả các nút như unvisited
• cho mỗi nút c, nếu nút này là unvisited
  • tạo ra một bộ trống mới của nút, các thành phần hiện tại
  • enqueue nút này cho traversal
  • trong khi có bất kỳ nút t enqueued
    • loại bỏ cái gật đầu này e khỏi hàng đợi
    • dấu mỗi người hàng xóm unvisited như mở và enqueue nó cho traversal
    • dấu ấn nút này như đi qua
    • thêm nút này để các thành phần hiện tại
  • đóng thành phần hiện tại, và thêm nó vào tập hợp các thành phần

Nếu chỉ có một thành phần, biểu đồ được kết nối.

Nếu hàng đợi được sử dụng, thuật toán là tìm kiếm theo chiều rộng. Nếu một ngăn xếp được sử dụng, thuật toán là tìm kiếm theo chiều sâu. Bất kỳ bộ sưu tập nào khác với thao tác push và pop-any sẽ thực hiện. Quan tâm đặc biệt là ngăn xếp cuộc gọi: thay thế "enqueue for traversal" với "đi qua đệ quy"

Đối với đồ thị được chỉ dẫn, có hai khái niệm liên quan: Biểu đồ đạo trình được kết nối yếu và được kết nối bỏ qua tất cả các hướng cạnh. Một đồ thị trực tiếp được kết nối mạnh mẽ với mọi nút có thể truy cập từ mọi nút.Để kiểm tra kết nối mạnh, nó đủ để kiểm tra mọi nút có thể truy cập từ nút đầu tiên chỉ sử dụng các cạnh phía trước và mỗi nút có thể truy cập từ nút đầu tiên chỉ sử dụng các cạnh sau (nút đầu tiên có thể truy cập từ mọi nút).

1. song phương

Một đồ thị là song phương khi và chỉ khi nó là bicolorable. Hãy thử chỉ định một bicoloring, và nếu bạn thất bại, đồ thị không phải là bipartite. Điều này có thể được kết hợp vào thuật toán trước: Bất cứ khi nào bạn đánh dấu một nút là mở, gán màu cho nó, đối diện với màu được gán cho hàng xóm của nó t. Khi một người hàng xóm của t đã mở, hãy kiểm tra màu của nó. Nếu màu sắc của nó là giống như của t, không có bicoloring.

1. có chu kỳ

Cái này là đơn giản: Nếu bạn quan sát bất kỳ nút đó đã được mở, có một chu kỳ. Lưu ý rằng mọi biểu đồ không có chu kỳ là hai bên.

Trong đồ thị được chỉ dẫn, điều này sẽ phát hiện sự hiện diện của một chu trình không được hướng dẫn. Để phát hiện sự hiện diện của chu kỳ đạo, sử dụng sau đây (topo loại) thuật toán:

• trong khi có một nút với indegree của zero
  • thêm nút để sắp xếp topo (không thích hợp cho việc phát hiện chu kỳ)
  • loại bỏ các nút từ biểu đồ
• nếu vẫn còn có bất kỳ nút trong đồ thị dưới
  • đồ thị chứa một cycl đạo e. Không loại topo tồn tại trên đó đồ thị
• khác
  • đồ thị không chứa một chu kỳ đạo (là mạch hở). Phân loại tôpô được tạo là hợp lệ.

1. cây

Một đồ thị vô hướng là một cây khi và chỉ khi nó được kết nối và không chứa chu kỳ.

Đồ thị có hướng là một cây bắt nguồn từ iff nó không có chu trình không bị gạch dưới và chỉ có một đỉnh với số không bằng 0 (chỉ một gốc). Ngoài ra, một đồ thị được chỉ đạo là một cây bắt nguồn từ iff nó được kết nối, không có chu kỳ không bị gián đoạn và mỗi nút có độ lệch bằng 0 có một số ít nhất là một (mỗi cái chìm là một chiếc lá).