1

Тема: Списки суміжності для графів

Готуюся до олімпіади (цієї суботи). Зараз згадую вивчаю графи і все, що з ними пов'язане.
З матрицею суміжності вроді розібрався, та й до цього нормально знав.
https://cloclo27.cloud.mail.ru/weblink/thumb/xw1/02570550fa12/%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D1%8F.JPG?x-email=havdyak_misha1998%40mail.ru

А от чи правильно я розумію як зберегти список суміжності у масиві?
https://cloclo26.cloud.mail.ru/weblink/thumb/xw1/2e64ff928c25/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA.JPG?x-email=havdyak_misha1998%40mail.ru

Я правильно намалював?

2

Re: Списки суміжності для графів

Залежить від того, як ви цю матрицю збираєтеся використовувати. Ви зменшуєте (можливо) обсяг пам'яті, але збільшуєте час роботи з матрицею.

3

Re: Списки суміжності для графів

Залежить від того, як ви цю матрицю збираєтеся використовувати. Ви зменшуєте (можливо) обсяг пам'яті, але збільшуєте час роботи з матрицею.

Ну я знаю:
1) списки краще використовувати, коли невелика к-сть ребер.
2) кращі при пошуку у глибину або ширину

Але матриця краще працює, коли треба визначити чи є ребро між двома даними вершинами.


Заки я все правильно розумію і роблю?

4

Re: Списки суміжності для графів

Розумієте ніби більш-менш правильно, а от як робите - не знаю, коду не бачу.
Ну і з пошуком... бувають різні нюанси.
Так, а ще матриці можна множити, на відміну від списків. Іноді це дуже корисно.

Подякували: Joker1

5

Re: Списки суміжності для графів

koala написав:

Розумієте ніби більш-менш правильно, а от як робите - не знаю, коду не бачу.
Ну і з пошуком... бувають різні нюанси.
Так, а ще матриці можна множити, на відміну від списків. Іноді це дуже корисно.

Добре, дякую. Але це ще не кінець теми. Зараз почнеться код, задачі і звісно ж проблеми. З проблемами я прийду до вас :)

6

Re: Списки суміжності для графів

В C++ вам буде дуже незручно працювати з масивом, що складається з масивів нерівної довжини. Це залежить від задачі, але мені більше подобається булевий масив 6x6, в якому елемент з індексом i,j позначає наявність переходу від i до j.

7 Востаннє редагувалося Joker (05.02.2015 14:12:13)

Re: Списки суміжності для графів

quez написав:

В C++ вам буде дуже незручно працювати з масивом, що складається з масивів нерівної довжини. Це залежить від задачі, але мені більше подобається булевий масив 6x6, в якому елемент з індексом i,j позначає наявність переходу від i до j.

Тобто на вашу думку, простіше працювати з матрицею суміжності?

8

Re: Списки суміжності для графів

Joker написав:
quez написав:

В C++ вам буде дуже незручно працювати з масивом, що складається з масивів нерівної довжини. Це залежить від задачі, але мені більше подобається булевий масив 6x6, в якому елемент з індексом i,j позначає наявність переходу від i до j.

Тобто на вашу думку, простіше працювати з матрицею суміжності?

Поки ви мовчите про задачу, але вже обрали C++ - так.

Подякували: Joker1

9

Re: Списки суміжності для графів

Я дійшов до висновку, що працювати з матрицею простіше. І якось обійдуся без переваг списків, чим простіше тим краще.

Тепер згадую dfs і планую розв'язати декілька задач.

10 Востаннє редагувалося Joker (05.02.2015 18:02:12)

Re: Списки суміжності для графів

http://www.e-olimp.com/ua/problems/122
Зараз почав думати над цією задачею. У моїй голові граф повинен бути неорєнтованим, але чому на малюнку стрілки мають напрямок?

11 Востаннє редагувалося koala (05.02.2015 18:11:30)

Re: Списки суміжності для графів

Орієнтований маршрут в горах:

Прихований текст

http://sfw.so/uploads/posts/2011-06/1307429910_35060_1600x1200-wallpaper-cb1304088950.jpg

12 Востаннє редагувалося Joker (05.02.2015 18:07:01)

Re: Списки суміжності для графів

koala написав:

Орієнтований маршрут в горах:

Прихований текст

http://sfw.so/uploads/posts/2011-06/1307429910_35060_1600x1200-wallpaper-cb1304088950.jpg

хах, картинка все пояснює  :)

13

Re: Списки суміжності для графів

Вчуся я робити ті dfs, але весь час заходжу у тупік
Мій код до тої задачі

Прихований текст
#include <iostream>
#include <conio.h>
using namespace std;

bool g[51][51];
bool used[51];
int n, d;

void DFS(int b);

int main()
{
    int k, a, b;
    cin >> n >> k >> a >> b >> d;

    for (int i = 0; i < k; ++i)
    {
        int z, x;
        cin >> z >> x;
        g[z][x] = true;
    }

    for (int i = 1; i <= n; ++i)
    {
        DFS(i);
    }

    _getch();
    return 0;
}

void DFS(int b)
{
    int count = 0;
    used[b] = true;

    for (int i = 1; i <= n; ++i)
    {
        if (g[i][b] && !used[i] && count <= d) {
            DFS(i);
            count++;
        }
    }
}

Я навіть знаю, що він робить :) . Але незнаю, як заставити робити те, що хочу я. Мій DFS проходить весь граф, коли мені потрібно тільки від вершини a до вершини b. І при цьому мені потрібно рахувати кількість моїх ходів (днів), порівнювати цю к-сть з d і в залежності від результату порівняння додавати 1 до res.

Я незнаю як це зробити, але дуже хочу зрозуміти. Дайте мені, будь ласка, копняка в правельне русло

14 Востаннє редагувалося koala (05.02.2015 20:36:11)

Re: Списки суміжності для графів

Хтось з нас двох неправильно розуміє, що має робити функція DFS. Можете описати словами, чого хочете від неї домогтися, на рівні ввід-вивід ("приймає номер вершини і...")?

Ну і якщо ви вже реалізуєте це все матрицею, то їх, нагадую, можна множити...

15

Re: Списки суміжності для графів

Хтось з нас двох неправильно розуміє, що має робити функція DFS. Можете описати словами, чого хочете від неї домогтися, на рівні ввід-вивід ("приймає номер вершини і...")?

Потрібно бути довбнем, щоб дійти до такого висновку: koala щось неправильно розуміє

Я розумію:
Звичайний ДФС робить обхід графа і позначає відвідані вершини.
А щоб розв'язати задачу потрібен ДФС який обходить від вершини а до вершини В .

А як зробити такий ДФС я незнаю :(

16

Re: Списки суміжності для графів

Ну тоді напишіть такий DFS, який отримує номери вершин - початку і кінця і кількість кроків, що лишилися, і коли закінчує перебір, "звільняє" свою початкову вершину, як вже перевірену.

17

Re: Списки суміжності для графів

Я щось не зрозумів з цією частиною.

"звільняє" свою початкову вершину, як вже перевірену.

хоча впевнений, що звільняє це велика підказка для мене.

18

Re: Списки суміжності для графів

тепер я запутався ще більше.

19 Востаннє редагувалося Joker (05.02.2015 21:21:49)

Re: Списки суміжності для графів

koala написав:

Ну тоді напишіть такий DFS, який отримує номери вершин - початку і кінця і кількість кроків, що лишилися, і коли закінчує перебір, "звільняє" свою початкову вершину, як вже перевірену.

Початок зрозумів. Потрібно замінити

void DFS(int a)

на

void DFS(int a,int b)

і k я напевно винесу в перед main

Але тепер я незнаю як мені перевіряти всі можливі випадки обходу і де їх перевіряти.

20

Re: Списки суміжності для графів

Ціль не обов'язково має бути параметром функції - її, як і кількість знайдених шляхів, з точки зору функціонального програмування бажано передавати параметром, але можна тримати і глобальною змінною.
Щось таке:
- якщо ми досягли цілі, то ура;
- якщо це останній день (d == 0), то ой;
- інакше  позначити вершину як відвідану, для всіх сусідів (список тут був би в нагоді) викликати DFS(сусід, d-1), зняти позначку про відвідини цієї вершини (бо в цій гілці ми сюди більше не зайдемо).

Подякували: quez1