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

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

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

Псеудокод

 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 рачунање особина деце, која зависе од истих особина родитеља, као растојање од почетног чвора. Ово дозвољава тражење најкраће путање до циљног чвора.