списък на съседство

В алгоритмите за обхождане на дърво и граф се използва линейна структура от данни наречена списък на съседство. Съдържанието на такъв списък включва номер на връх с последващо изброяване на всички върхове, с които той е свързан (с ребра).

Ако се представя претеглен граф в списъка на съседство се съхранява информация и за дължината на ребрата.

Ако чрез списъка на съседство се представя ориентиран граф в съответния ред от списъка се посочват само номерата на върховете, към които има път от съответния връх. Така, при ориентирана и неориентиран граф, за един и същ брой върхове и същите пътища между тях редовете в списъка на съседство са с различна дължина.

Да се реализира проект, чрез който се представят вътрешнопредметни връзки в Информатиката.

Тема на проекта: граф, списък на съседство.

В примерния проект координатите на върховете на неориентирания граф се въвеждат чрез курсора на мишката. Не се допуска повторно въвеждане на връх с координати на вече съществуващ.

Информация за наличие на ребро се въвежда чрез посочване редове от списъчни полета, за номер на начален и краен връх. Програмно, чрез отсечка, се изчертава съответното ребро. Изградена е вътрешна защита при въвеждане информация за примка във връх на графа или за повтарящо се ребро - мултиграф.

Чрез събитие On-Click върху команден бутон се извежда информация за списък на съседство в конструирания граф. Всеки изолиран връх в графа се оцветява.

Прочетете допълнителен материал за матрица на съседство и алгоритми за обхождане на граф. Съберете информация за сложността на отделните алгоритми. При представяне на граф, чрез списък на съседство, сложността на намиране на всички съседи е линейна по отношения броя съседи, сложността за проверка наличие на ребро между два върха е също линейна.

Разгледайте други реализирани примерни проекти, за които е ползвана подобна логическа структура на графичните обекти и/или приложени сходни алгоритми:  свързаност в граф, матрица на съседство, цикъл в граф.