116. Графи и представяне на съседство
Графът има върхове и ребра. Ребрата могат да са насочени или ненасочени. Списъкът на съседство пази съседите на всеки връх, а матрицата отбелязва съседството за всяка двойка.
Раздел в разширената разработка.
Самостоятелна задача
Условие
Четири спирки A, B, C и D са свързани с двупосочни отсечки A–B, A–C и C–D. Други отсечки няма. В матрицата редовете и колоните са в ред A, B, C, D. Пишем 1 за пряка отсечка, иначе 0.
- Какви са списъците на съседство на A и C?
- Как изглежда редът за C в матрицата?
- Дай път от B до D и броя на ребрата му.
- Ако отсечката A–C стане еднопосочна от A към C, кои клетки за тази двойка са 1 и 0?
Отговори за самопроверка
Отговор 1
A има B, C. C има A, D.
Отговор 2
1 0 0 1.
Отговор 3
B–A–C–D, три ребра.
Отговор 4
В ред A, колона C остава 1. В ред C, колона A става 0.
Изпълним пример
Булевата матрица представя двупосочните отсечки 0–1 и 1–2. Индексът е номерът на спирката. Програмата извежда съседите на спирка 1.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
using namespace std; // Така можем да пишем cout вместо std::cout.
int main() { // Оттук започва изпълнението на програмата.
bool adjacent[3][3] = { // Започваме таблица с по един ред и колона за всяка от трите спирки.
{false, true, false}, // Редът за спирка 0 отбелязва пряка връзка само със спирка 1.
{true, false, true}, // Редът за спирка 1 отбелязва пряка връзка със спирки 0 и 2.
{false, true, false} // Редът за спирка 2 отбелязва пряка връзка само със спирка 1.
}; // Край на началните данни.
int stop = 1; // Задаваме номера на спирката, чиито съседи търсим.
for (int other = 0; other < 3; other++) { // Проверяваме последователно колоните с номера 0, 1 и 2.
if (adjacent[stop][other]) // Гледаме дали в реда за stop е отбелязана връзка с other.
cout << other << '\n'; // Ако има пряка връзка, печатаме номера на другата спирка.
} // Край на цикъла.
} // Край на програмата.
В речника Граф · Съседство в граф · Път в граф.