Упражнения върху представянето на граф чрез свързан списък
Следните задачи целят да упражнят работата с представяне на граф като списък от съседи. Графът е с естествени числа по върховете. Стремим се да ползваме максимално въведените на лекции представяне и операции, спазайки доколкото е възможно принципа за абстракция чрез структури от данни.
Избраното представяне е следното: поддържа се списък от списъци от числа. Първият елемент на всеки от тези списъци е номер на някой връх в графа, а следващите елементи - неговите съседи, точно по един елемент за съсед. Всеки връх на графа се преставя от точно един такъв списък.
Да се припомнят функциите от лекции за добавяне на връх и добавяне на ребро. Да се обясни, че информационната част на всяка двойна кутия на графа не е указател, а списък (тройка start, end, current).
Задача 1. Да се състави функция, която проверява дали в даден граф има връх с номер i.
Задача 2. Да се състави функция, която проверява дали в даен граф има дъга от даден връх i до даден връх j.
При тази задача е хубаво да се забележи, че ако функцията се състави по начин, при който винаги да връща истина ако двата върха съвпадат, то ние неявно поставяме примка на всеки връх в нашия граф. В този момент може също да се обсъдят по-подробно такива неща като примки, "посоки" на дъгите, цикли и свързаност.
Задачата се улеснява, ако предварително напишем функция, която по даден връх връща списъка на наследниците му в графа. Такава функция ще е полезна и за други манипулации с графа.
Задача 3. Да се състави функция, която изтрива реброто от връх i до връх j в графа, като връща false, ако такова ребро няма.
Използвайте функцията за намиране на списък от наследници. Припомнете си защо DeleteAfter е по-ефективна от DeleteElem.
Задача 4. Да се състави функция, която изтрива връх от графа, заедно с влизащите и излизащите от него ребра.
Функцията става кратка, ако използваме наготово предишната задача и функцията за намиране на списък от наследници.
Задача 5. Да се състави функция, която по два дадени графа проверява дали съвпадат, като за два графа казваме че съвпадат, ако върховете и дъгите им съвпадат.
Хубаво е да се стремим в циклите на нашите функции да позлваме колкото се може по-рядко оператори като break, continue, return, стремейки се да постигнем желаното поведение чрез "хитри" логически условия за край на циклите.