Пређи на садржај

Алгоритми/Алгоритми код неусмерених графова

Извор: Викикњиге

Представљање графа

[уреди]

Суседство матрица

[уреди]

Суседство листи

[уреди]

Поређење

[уреди]

Прво-у-дубину

[уреди]

Псеудокод

[уреди]
 dfs(vertex w)
   if w has already been marked visited
     return
   mark w as visited
   for each adjacent vertex v
     dfs(v)

Особине

[уреди]

Класификација грана

[уреди]

Гране стабла

[уреди]

Гране које иду уназад

[уреди]

Гране које иду унапред

[уреди]

Унакрсне гране

[уреди]

Постоје добре технике од: Yogesh Jakhar

Претраживање у ширину

[уреди]

Псеудокод

[уреди]

bfs ( x ):

 q insert x;
 while (q not empty )
    y = remove head  q
    visit y
    mark y
    for each z adjacent y 
      q add tail z

Пример

[уреди]

Тачност

[уреди]

Анализе

[уреди]

Употреба

[уреди]

Претраживање у ширину се може користити у истраживању шема база података, са намером да се претвори у xml шему. Ово се остварује тако што именујемо корену табелу и онда урадимо референтно претраживање у ширину. Претраживање је обављено и референтним крајевима, тако да ако нека друга табела понуди тренутном чвору да се претражи,онда та табела има један-до-много односа у xml шеми, иначе је много-до-једног.

Класични проблеми код графа

[уреди]

Тополошко сортирање

[уреди]

A topological sort is an ordering of vertices in a directed acyclic graph such that if there is a path from vi to vj, then vj appears after vi in the ordering.

Тополошко сортирање је одређивање редоследа чворова у директном ацикличном графу тако да ако постоји пут од чвора vi до чвора vj, онда се чвор vj појављује после чвора vi у редоследу.

Дат је граф G. Тополошко сортирање може бити представљено са следећим корацима.

  1. Пронаћи било који чвор без улазних грана и убацити га у листу
  2. Уклонити га заједно са својим гранама (Све гране би требало да буду излазне)
  3. Поновити корак 1 док нема више чворова
  4. Алтернатива је да користите прво-у-дубину обрнутим каснијим редоследом. Ово значи дарекурзивно убаците чвор након посећивања његове деце у листи и обрнути листу. Ово ради индуктивно, јер најдубље дете нема своје дете и биће прво убачено у листу. Онда његови родитељи, па родитељи његових родитеља итд.

Тополошко сортирање је корисно када je рачунање особина деце, која зависе од истих особина родитеља, као растојање од почетног чвора. Ово дозвољава тражење најкраће путање до циљног чвора.

Јако повезане компоненте

[уреди]

Артикулација чвора

[уреди]

Мост

[уреди]

Пречник

[уреди]