Qo’llanilishi: Grafning komponentalarni aniqlash. Buning uchun navbatdagi hali ko’rilmagan uch orqali kenglik bo’yicha izlashni boshlaymiz. Bu o’tib chiqishda u unga bog’langan barcha uch orqali o’tib chiqadi, va ular bitta graf komponentasi deb aytiladi. Komponentalar soni bfs funksiyasiga necha marta murojaat qilganimiz soni. used massivida true qiymatni qabul qilgan barcha uchlar kenglik bo’yicha izlashni boshlagan uch orqali borib bo’ladi.
Grafdagi eng qisqa yo’l topish.Grafda yo’l bu – bir uchdan boshqa uchga boradigan uchlar va qirralar ketma-ketligiga aytiladi. Qirralar soni esa yo’l uzunligi deb ataladi. Eng qisqa yo’l qirralar soni eng kichik bo’ladiga yo’lga aytiladi. Chuqurlik bo’yicha izlash algoritmi aynan qirralar soni bo’ticha eng qisqa yo’lni topadi. Bunig uchun qo’shimcha d[] massivini kiritamiz. Dastlabki uch uchun d[v] = 0. Navbatdan olingan har bir v uchni oladigan bo’lsak, unga qo’shni bo’lgan hali ko’rilmagan u uchga yana bitta qirra orqali o’tib borish kerak. Shuning uchun d[u] = d[v]+1 qilib belgilab qo’yamiz.
Yuqoridagi graf uchun eng qisqa masofalar quyidagicha bo’ladi:
Masalalar. 1-topshiriq Undiriented graph is given. Find the shortest path from vertex a to vertex b.
Input The first line contains two integers n and m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 100000) - the number of vertices and edges. The second line contains two integers a and b - the starting and ending point correspondingly. The next m lines describe the edges.
Output If the path between a and b does not exist, print -1. Otherwise print in the first line thelength l of the shortest path between these two vertices in number of edges.
Samples
