Перемещение дерева, представленного его ребрами

Question

Мое дерево представлено его ребрами и корневым узлом. Список краев - неориентированный.

char[][] edges =new char[][]{ 
    new char[]{'D','B'}, 
    new char[]{'A','C'}, 
    new char[]{'B','A'}    
}; 

char root='A'; 

Дерево

A 
B C 
D 

Как сделать глубины первого обхода на этом дереве? Какова временная сложность?

Я знаю, что временная сложность первого пересечения глубины на связанных узлах равна O (n). Но если дерево представлено ребрами, то я считаю, что временная сложность O (n^2). Я ошибаюсь?

Предоставление кода ценится, хотя я знаю, что это выглядит как домашнее задание ..

Answer 1

Общий шаблон за ДФС выглядит примерно так:

function DFS(node) { 
    if (!node.visited) { 
     node.visited = true; 
     for (each edge {node, v}) { 
      DFS(v); 
     } 
    } 
} 

Если у вас есть ваши края представлены в виде списка все ребра в графе, тогда вы можете реализовать цикл for, итерации по всем краям графика и каждый раз, когда вы находите его с текущим узлом в качестве его источника, следуя за краем до его конечной точки и запуская DFS , Если вы это сделаете, то вы выполните O (m) работу на узел в графе (здесь m - количество ребер), поэтому время выполнения будет O (mn), так как вы сделаете это не чаще одного раза за узел на графике. В дереве число ребер всегда равно O (n), поэтому для дерева время выполнения равно O (n).

При этом, если у вас есть дерево, и есть только n ребер, вы можете ускорить это с помощью нескольких способов. Во-первых, вы можете рассмотреть возможность выполнения этапа предварительной обработки O (n log n) для сортировки массива ребер. Затем вы можете найти все ребра, покидающие данный узел, выполнив двоичный поиск, чтобы найти первое ребро, покидающее узел, а затем итерацию по краям, начинающимся там, чтобы найти только края, покидающие узел. Это немного улучшает время выполнения: вы выполняете O (log n) работу на узел для двоичного поиска, а затем каждый край посещается только один раз. Это означает, что время выполнения - O (n log n). Поскольку вы упоминали, что ребра неориентированы, вам действительно нужно создать две разные копии массива ребер - одну, которая является исходной, а одна с ребрами в обратном порядке - и должна сортировать каждую из них независимо. Тот факт, что метки DFS посещают узлы по пути, означает, что вам не нужно делать дополнительную бухгалтерию здесь, чтобы выяснить, в каком направлении вы должны идти на каждом шаге, и это не меняет общей сложности времени, хотя оно увеличивает использование пространства.

В качестве альтернативы вы можете использовать решение на основе хэширования. Перед выполнением DFS итерации по краям и преобразования их в хэш-таблицу, ключи которой являются узлами и значения которых являются списками ребер, покидающих этот узел. Это займет ожидаемое время O (n). Затем вы можете эффективно выполнить шаг «для каждого края», просто выполнив поиск в хэш-таблице, чтобы найти ребра, о которых идет речь. Это сокращает время до (ожидаемого) O (n), хотя использование пространства также увеличивается до O (n). Поскольку ваши края неориентированы, когда вы заполняете таблицу, просто обязательно вставьте край в каждом направлении.