Разница между краями деревьев и передними краями

Question

Я читал книгу, когда натолкнулся на вопрос: как вы можете отличить прямые ребра и ребра дерева от времени обнаружения и окончания этой конкретной вершины в графе, когда на нем выполняется DFS?

То, что я пытался до сих пор, так это: главное отличие Fwd. Tree Edges - если между A и B существует ребро дерева, то A является прямым соседом B, длина пути которого равна 1, но если Fwd. край, то длина пути должна быть больше 1 или около того. Таким образом, при анализе времени обнаружения и окончания, которое может быть сохранено в массиве, мы можем проверить, отличаются ли их время окончания / начала на 1. Потому что, если это так, то это край дерева, в противном случае - передний край.

Но я не могу разработать алгоритм, а также сомневаюсь, что этот подход ошибочный. Пожалуйста, помогите мне. Спасибо.

Answer 1

Выполняя поиск в глубину на ориентированном графе,

1. Если посещение нового узла v (v не было обнаружено ранее) от вас
   чем (u,v) ребро дерева.

2. иначе, если мы посетим узел V, уже посещенный ранее

   • Если мы еще не покинули / не закончили с этим узлом (v), то, безусловно, v является предком u и (u,v) задним краем.

   • Еще есть две возможности - поперечная кромка или передняя кромка. В обоих этих случаях мы посещаем узел (v), из которого мы уже вышли. Итак, здесь мы можем различить их по времени прибытия.

     • Это передний край (переход от предка к потомку, u -> v), если время прибытия u будет меньше v

     • Это перекрестный край, если время прибытия u будет больше, чем v.

Для справки:

void dfsEdges(struct graph*G, int v, int *visited, int *arrTime, int *depTime)
{
 static int time=0;


visited[v]=1;
arrTime[v]=time++;

struct node *temp = G->array[v];
while(temp!=NULL)
{
    if(visited[temp->val] != 1)
    {
        dfsEdges(G,temp->val,visited,arrTime,depTime);
    }
    else
    {
        if(depTime[temp->val] ==-1)
        printf("\n%d - %d is back edge\n",v,temp->val);
        else
        {
            if(arrTime[v]<arrTime[temp->val])
            printf("\n%d - %d is forward edge\n",v,temp->val);
            else
            printf("\n%d - %d is cross edge\n",v,temp->val);
        }

    }
    temp=temp->next;

}
depTime[v]=time++;

}

Answer 2

Край (u, v) классифицируется как передний фронт, если discoveryTime(v) уже определен во время наблюдения v и discoveryTime(u) <= discoveryTime(v). Следовательно, ребро (u, u) также классифицируется как переднее ребро. Классификация основана на порядке, пройденном DFS по вершинам, то есть начало с другой вершины может привести к другой классификации. Алгоритм в псевдокоде (с объяснением и доказательством) можно найти в книге Курта Мелхорна: структуры данных и эффективные алгоритмы, том 2, Springer Verlag, EATCS Monographs, 1984. (из печати, но доступной автором в Интернете), глава 4 "Алгоритмы на графиках", стр. 21, как показано ниже. Я включил фрагмент на странице 25 с классификацией ребер (строки (8) - (10), как предложено автором).