| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Object Pascal: кроссплатформенные технологии > как проверить двудольность графа? |
| Автор: freeda 27.12.2004, 21:14 |
| Нужно проверить граф на двудольность поиском в ширину. Если кто-нибудь может помочь, напишите plzz в чем идея, ну или код, а то не видать мне зачета... |
| Автор: Fedor 28.12.2004, 10:00 |
| я бы делал так: Берешь первую вершину и "запоминаешь" ее первую долю.От нее идешь поиском в ширину и смотришь: если вершина еще не принадлежит ни одной доле, то добавляешь ее в долю, противоположную родительской. Если же она уже принадлежит какой то доле, то смотришь, какой: если той же, где и родитель, то не двудольный. Если вдруг цепочка оборвалась, а есть еще непройденные вершины, опять берешь любую и добавляешь ее в любую долю. |