BG Development


  Reply to this topicStart new topicStart Poll

> Задача за граф
easypeasy
Публикувано на: 06-05-2019, 16:14
Quote Post



Име:
Група: Потребител
Ранг: Новопостъпил

Мнения: 1
Регистриран на: 06.05.19



Здравейте!
Имам нужда от помощ за задача свързана с графове(C++).
Условието:
Да се състави функция, която съобщава, дали в даден ориентиран граф има върхове от вида: ->O<-
Общо взето съм до създаването на граф(инициализиране, функции за създаване на връх, създаване на дъги между върхове, функция за търсене на връх, функция за търсене на дъга).Четох в най-различни презентации , учебници и т.н., но така и не придобих ясна представа какво трябва да се направи.Предполагам ми трябва обхождане на всеки един от върховете, за да се провери има ли изходяща дъга от него, но си нямам да представа как може да се случи това.Ако някой може да ми състави тази функция, ще съм много благодарен. icon_smile.gif icon_smile.gif
П.С.
Това са ми функциите:
Функции
PMEmail Poster
Top
Barnabas
Публикувано на: 06-05-2019, 20:24
Quote Post



Име:
Група: Потребител
Ранг: Редовен член

Мнения: 434
Регистриран на: 02.03.15



Здравей!

Опитай да направиш имплементация, в която за всеки връх в списъци пазиш върховете от който се стига да този връх (входящи) и върховете към които се отива от него (изходящи) към други.

Или като компромисен вариант дефинирай InDegree(n) -- брой върхове от коитo се стига до n и OutDegree(n) -- брой върхове от които от n се стига до. По този начин задачата ти се свежда до просто обхождане (в дълбочина или ширина) и отсяване на върховете за които InDegree(n)=OutDegree(n)=1

П.С. не си кръщавай функциите на шльокави имена -- вебаджииско е!

Това мнение е било редактирано от Barnabas на 06-05-2019, 20:27
PMEmail Poster
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2019 | BG Development | All Rights Reserved
RSS 2.0