25. Работа с графами
25.1. Транзитивное замыкание на графе.
Дано: граф с направленными дугами:
DVG(V1,V3/D13)
DVG(V2,V3/D23)
DVG(V3,V4/D34)
DVG(V3,V5/D35)
DVG(V2,V6/D26)
DVG(V4,V6/D46)
Даны исходная и конечная вершины: MET1(V2) MET2(V6)
Требуется найти все дуги через которые есть путь от исходной вершины к конечной.
Волновой метод:
1) Отмечаем все вершины и дуги, к которым есть путь от V2.
2) Ищем вершины и дуги из которых идет путь к V6.
3) Ищем дуги, которые удовлетворяют 1-му и 2-му условию.
START:IF THEN T:UR1() T:UR2() T!:UR3() B:IN() B:HALT();
{== Метятся вершины MET1(X1) и дуги MD1(X13), к которым есть путь от исходной вершине ==}
UR1():IF MET1(X1) DUG(X1,X2/X13) N:MD1(X13) THEN MD1(X13) MET1(X2);
{== Метятся вершины MET2(X1) и дуги (X13), из которых идет путь к конечной вершине ==}
UR2():IF MET2(X1) DUG(X2,X1/X13) N:MD2(X13) THEN MD2(X13) MET2(X2);
{== Поиск дуг с метками MD1(X13) и MD2(X13) ==}
UR3():IF MD1(X13) MD2(X13) THEN B:BK() B: A(" дуга - ",X13);
Продукция T:UR1() по MET1(V2) последовательно сформирует:
MD1(D23) MET1(V3) -> MD2(D34) MET1(V4) -> MD1(D35) MET1(V5) -> MET1(V6) -> MD1(D46) MET1(V6)
Продукция T:UR2() по MET2(V6) последовательно сформирует:
MD2(D26) MET2(V2) -> MD2(D46) MET2(V4) -> MD2(D34) MET1(V3) -> MD2(D13) MET2(V1) -> MD2(D23) MET2(V2)
Продукция T:UR3() найдет пересечение и выдаст на экран:
дуга - D23
дуга - D26
дуга - D34
дуга - D46
Это и есть транзитивное замыкание.
25.2. Поиск пути на графе:
Дано: граф с направленными дугами:
DUG(V1,V2)
DUG(V2,V3)
DUG(V1,V3)
DUG(V3,V4)
Указаны начальная и конечная вершины: PATH(V1,V4)
Требуется: найти путь от V1 к V4.
Программа основана на рекурсивном обращении: если от V1 идет дуга к V2, то делается попытка поиска пути от V2 к V4 и т.д. Когда путь найден, то за счет хвостовой рекурсии выдаются дуги:
START:IF PATH(X1,X2) THEN T!:SEEK_P(X1,X2);
{== поиск пути от X1 к X2 ==}
SEEK_P(X1,X2):IF DUG(X1,X2/X11) N:MT() THEN
MT() {= MT() - метка, что путь найден =}
T1:OUT_DUG(X11);
SEEK_P(X1,X2):IF DUG(X1,X3/X11) N:MT() THEN
Т!:SEEK_P(X3,X2) {= поиск пути от X3 к X2 =}
T1:OUT_DUG(X11);
OUT_DUG(X11):IF MT() THEN B:BK()B:A(" дуга - ",X11);
Предыдущий раздел|Следующий раздел