Алгоритми/Алгоритми код неусмерених графова
Представљање графа
уредиСуседство матрица
уредиСуседство листи
уредиПоређење
уредиПрво-у-дубину
уредиПсеудокод
уреди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 док нема више чворова
- Алтернатива је да користите прво-у-дубину обрнутим каснијим редоследом. Ово значи дарекурзивно убаците чвор након посећивања његове деце у листи и обрнути листу. Ово ради индуктивно, јер најдубље дете нема своје дете и биће прво убачено у листу. Онда његови родитељи, па родитељи његових родитеља итд.
Тополошко сортирање је корисно када je рачунање особина деце, која зависе од истих особина родитеља, као растојање од почетног чвора. Ово дозвољава тражење најкраће путање до циљног чвора.