116. Графи и представяне на съседство

Графът има върхове и ребра. Ребрата могат да са насочени или ненасочени. Списъкът на съседство пази съседите на всеки връх, а матрицата отбелязва съседството за всяка двойка.

Раздел в разширената разработка.

Самостоятелна задача

Условие

Четири спирки A, B, C и D са свързани с двупосочни отсечки A–B, A–C и C–D. Други отсечки няма. В матрицата редовете и колоните са в ред A, B, C, D. Пишем 1 за пряка отсечка, иначе 0.

  1. Какви са списъците на съседство на A и C?
  2. Как изглежда редът за C в матрицата?
  3. Дай път от B до D и броя на ребрата му.
  4. Ако отсечката 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';             // Ако има пряка връзка, печатаме номера на другата спирка.
    }                                          // Край на цикъла.
}                                              // Край на програмата.

Изтегли main.cpp.

В речника Граф · Съседство в граф · Път в граф.