Граф гэж юу вэ? Ирмэг болон оройгоос бүтсэн бүтцийг граф гэнэ. Энэ хаяг дээр графын тухай тодорхойлолт байгаа. Мөн математикын зарим номондээр илүү дэлгэрэнгүй тодорхойлолтууд байгаа(байх). Харин одоо графыг хэрхэн унших талаар бичье. Оролтын хувьд хоёр хэлбэртэй. Оройн тоо өгөгдөнө. N гэе. Матриц буюу хүснэгтээр. Энэ тохиолдолд NxN харьцаатай матриц өгөгдөх ба i-р мөрийн j-р баганы утгаар i- аас j-ын хоорондох ирмэг тодорхойлогдоно гэсэн үг юм. Хэрэв a[i][j]- ын утга нь 0 бол i- аас j хүрэх шууд ирмэг байхгүй гэсэн үг юм. Хэрвээ жингүй граф бол a[i][j]- ын утга нь 0 эсвэл 1 байна. Хэрэв 1 бол i- аас j хүрэх шууд ирмэг байгаа гэсэн үг юм. Харин жинтэй графын хувьд a[i][j]-ы н утга нь 0- ээс ялгаатай бол i- аас j хүрэх шууд ирмэг байгаа бөгөөд түүний жин нь a[i][j]- ын утга байх юм. Ийм бүтцээр оролтод өгөгдөх нь тун ховор юм. Учир нь 10^5 ширхэг оройтой графын мэдээллийг уншихын тулд 10^10 зэрэг тоо уншина гэсэн үг юм. Оройн тоо N, ирмэгийн тоо M өгөгдөнө. Дараагаар н
Алгоритмын хичээл