====== سوال ۴ ======

گراف همبند و ساده‌ی $G$ با $n$ راس و یک زیردرخت پوشا از آن با نام $T$ به ما داده شده است. الگوریتمی از $O(n^2)$ ارائه دهید که مشخص کند آیا زیردرخت $T$ می تواند، یک درخت BFS از گراف $G$ باشد یا خیر.

درخت BFS درختی است که قابل تولید توسط الگوریتم BFS (با استفاده از لیست مجاورت) باشد. یعنی ترتیبی از رئوس در لیست همسایگان هر راس وجود داشته باشد که پس اجرای الگوریتم BFS درخت مورد نظر تولید شود.

  * [[سوال ۵|سوال بعد]]
  * [[سوال ۳|سوال قبل]]