Графика Traversal използва DFS - алгоритъм, дълбочина-първо търсене

Аз учих траверса на графики от Ръководството за проектиране на алгоритмите от Стивън С. Скиена. В своята книга той е предоставил кода за преминаване на графиката с помощта на dfs. По-долу е кодът.

dfs(graph *g, int v)
{
edgenode *p;
int y;
if (finished) return;
discovered[v] = TRUE;
time = time + 1;
entry_time[v] = time;
process_vertex_early(v);
p = g->edges[v];
while (p != NULL) {
/* temporary pointer */
/* successor vertex */
/* allow for search termination */
y = p->y;
if (discovered[y] == FALSE) {
parent[y] = v;
process_edge(v,y);
dfs(g,y);
}
else if ((!processed[y]) || (g->directed))
process_edge(v,y);
}
if (finished) return;
p = p->next;
}
process_vertex_late(v);
time = time + 1;
exit_time[v] = time;
processed[v] = TRUE;
}

В неразрешена графика изглежда, че по-долу кодът обработва ръба два пъти (извиквайки метода process_edge (v, y). Едно, докато преминаваме през върха v и друг при обработката на връх y).
Така че съм добавил условието parent[v]!=y в else if ((!processed[y]) || (g->directed)).
Той обработва ръба само веднъж. Все пак, не съм сигурен как да променя този код, за да работи с паралелния ръб и ръба на самочувствието. Кодът трябва да обработва паралелния ръб и самобръсначката.

Отговори:

2 за отговор № 1

Кратък отговор:

заместител Вашият (parent[v]!=y) за (!processed[y]) вместо да го добавите към състоянието.

Подробен отговор:

По мое мнение има грешка визпълнение, написано в книгата, която сте открили и фиксирали (с изключение на паралелни ръбове. Предполага се, че изпълнението е правилно както за насочените, така и за нерегламентираните графики, като разликата между тях се записва в g->directed булева собственост.

В книгата, точно преди изпълнението, авторът пише:

Другото важно свойство на дълбочина - първотърсене е, че тя разделя ръбовете на неподходяща графика в точно два класа: ръбовете на дървото и задните ръбове. Най- ръбовете на дървото откриват нови върхове и са кодирани в родителската връзка. обратно краищата са онези, чиято друга крайна точка е предшественик на върха, който се разширява, така че те посочват обратно в дървото.

Така че състоянието (!processed[y]) се очаква да се справя с нерегламентирани графики (като условие (g->directed) е да се обработват насочени графики), като се позволи наалгоритъм за обработка на краищата, които са задните ръбове, и предотвратяване на повторното обработване на онези, които са дървени ръбове (в обратната посока). Както сте забелязали, обаче, краищата на дърветата се третират като задни ръбове, когато се прочетат през детето с това състояние, така че трябва просто да замените това състояние с предложеното (parent[v]!=y).

Условието (!processed[y]) винаги ще бъде вярно за нерегламентирана графика, когатоалгоритъмът го чете толкова дълго, колкото няма паралелни ръбове (повече подробности защо това е вярно - *). Ако има паралелни ръбове - онези паралелни ръбове, които се четат след първото "копие" от тях, ще добият false и ръбът няма да бъде обработен, когато тойби трябвало. Предложеното ви състояние обаче ще прави разлика между ръбовете на дърветата и останалите (задни ръбове, успоредни ръбове и самопроводници) и ще позволи на алгоритъма да обработва само онези, които не са дървени ръбове в обратната посока.

За да се отнасят само до краищата, те трябва да бъдат добре както с новите, така и с старите условия: те са с ръбове y==v, Как да стигнем до тях, y е открита (защото v е открит преди да премине през ръбовете му), не е преработен (v се обработва само като последната линия - след преминаване през краищата й) и не е така vродител (v не е негов собствен родител).

---

*Преживява v"ръбовете, алгоритъмът чете това условие за y (така че не отива в първия условен блок) Както е посочено по-горе (в книгата има полу-доказателство и за това, което ще включа в края на тази бележка под линия), p е ръб на дървото или гърба. Като y е открит, той не може да бъде край на дървото v да се y, Това може да бъде задния край на предшественика, койтоозначава, че обаждането е в повторно обаждане, което в някакъв момент е започнало да обработва този предшественик, така че обаждането на предшественика все още не е достигнало до последната линия, маркирайки го като обработено (така че все още е маркирано като непроцесорно) и може да бъде край на дървото y да се v, в който случай съществува същата ситуация - и y все още е означена като непроменена.

Полупроводниковият за всеки ръб е дърво-ръб или обратно-край:

Защо не може да се стигне до брат или братовчедвместо предшественик? Всички възли, достижими от даден връх v, се разширяват, преди да завършим с traversal от v, така че такива топологии са невъзможни за неопределени графики.

---

1 за отговор № 2

Прав си.

Цитирайки книга "(2-ро издание) errata:

(*) Страница 171, ред -2 - Кодът на dfs има грешка, при която всеки дървен ръб се обработва два пъти в неразрешени графики. Тестът трябва да бъде укрепена да бъде:

else if (((!processed[y]) && (parent[v]!=y)) || (g->directed))

Що се отнася до цикъла - вижте тук

---