Vì biểu đồ là tuần hoàn (tức là có thể chứa chu kỳ), trước tiên tôi sẽ chia nhỏ nó thành các thành phần được kết nối mạnh. Một strongly connected component của đồ thị được chỉ dẫn là một đồ thị con nơi mỗi nút có thể truy cập từ mọi nút khác trong cùng một đồ thị con. Điều này sẽ mang lại một tập hợp các đồ thị con. Lưu ý rằng một thành phần được kết nối mạnh mẽ của nhiều hơn một nút là một chu kỳ có hiệu quả.
Bây giờ, trong mỗi thành phần, bất kỳ thông tin nào trong một nút cuối cùng sẽ kết thúc ở mọi nút khác của biểu đồ (vì tất cả chúng đều có thể truy cập được). Vì vậy, đối với mỗi đồ thị con, chúng ta chỉ có thể lấy tất cả dữ liệu từ tất cả các nút trong đó và làm cho mọi nút có cùng một tập hợp dữ liệu. Không cần phải đi qua các chu kỳ. Ngoài ra, ở cuối bước này, tất cả các nút trong cùng một thành phần chứa chính xác cùng một dữ liệu.
Bước tiếp theo sẽ là thu gọn từng thành phần được kết nối mạnh vào một nút duy nhất. Vì các nút trong cùng một thành phần đều có cùng dữ liệu và do đó về cơ bản giống nhau, thao tác này không thực sự thay đổi biểu đồ. "Super node" mới được tạo sẽ kế thừa tất cả các cạnh đi ra ngoài hoặc đi vào các nút của thành phần từ các nút bên ngoài thành phần.
Kể từ khi chúng tôi đã sụp đổ linh kiện tất cả các kết nối mạnh mẽ, sẽ không có chu kỳ trong đồ thị kết quả (tại sao? Vì đã có được một chu kỳ hình thành bởi các nút kết quả, họ sẽ tất cả đã được đặt trong cùng một thành phần ở nơi đầu tiên). Biểu đồ kết quả hiện là Directed Acyclic Graph. Không có chu kỳ và độ sâu đơn giản đầu tiên từ tất cả các nút với indegree = 0 (tức là các nút không có các cạnh đến), truyền dữ liệu từ mỗi nút đến các nút liền kề của nó (tức là "con"). .
Đây có thể là một số loại tất cả cho tất cả phát sóng (hoặc tất cả để phân tán) vấn đề giao tiếp. Có thể hữu ích nếu bạn tìm kiếm với những từ khóa này. – PeterK
Có thể những điều này rõ ràng với mọi người khác, nhưng ý bạn là gì khi bắt đầu từ lá và truyền dữ liệu ở hạ lưu? Sẽ không phải là một lá là một nút không có nút hạ lưu từ nó? Ngoài ra, chu kỳ ổn định có nghĩa là gì? – ESRogs
Tôi nghĩ những gì tôi gọi là 'lá' có thể được mô tả rõ ràng hơn là 'rễ', mặc dù đã cho nó là một thuật ngữ đồ thị cyclic neather là đặc biệt trực quan --- tôi có nghĩa là một nút không có cha mẹ. Downstream là theo hướng của trẻ em. Vì quá trình truyền tải của một chu kỳ có thể tiết lộ nhiều thông tin có thể cần được truyền cho các nút đã truy cập, một số nút có thể cần được truy cập nhiều lần, có nghĩa là quyết định khi nào chấm dứt có thể phức tạp; do đó ổn định. Trong thực tế, nó quay ra có một cách dễ dàng hơn nhiều để làm điều này --- xem câu trả lời. –