Псевдокод для посещения конечного автомата

Question

Я хочу написать псевдокод для посещения конечного автомата с использованием DFS. Государственная машина может рассматриваться как ориентированный граф. Следующий алгоритм из книги Cormen использует алгоритм DFS для посещения графика.

DFS-VISIT(G, u)   //G= graph, u=root vertex 
    u.color = GRAY 
    for each v from G.Adjacents(u) //edge (u, v) 
     if v.color == WHITE 
      DFS-VISIT(G, v) 

Государственная машина, однако, может иметь несколько ребер между двумя вершинами. И выше алгоритм хранит ребра в списке смежности. Я реализовал алгоритм в Java со следующими классами,

class Node{ 
    String name; 
    .... 
    ArrayList<Transition> transitions; 

    void addTransition(Transition tr); 
} 

class Transition 
{ 
    String src; 
    String dest; 
} 

С приведенной выше информацией, я построил государственный аппарат с узлом и переходными объектами. Я хочу изменить приведенный выше алгоритм, где у меня нет объекта графа G. Я просто имею доступ к корневому объекту.

Могу ли я изменить приведенный выше алгоритм, как показано ниже?

DFS-VISIT(root)    //root node 
    root.color = GRAY 
    for each t from root.getTransitions() //t=transition 
     v = t.getDestination()  //v=destination of t 
     if v.color == WHITE 
      DFS-VISIT(v) 

Answer 1

Алгоритм не зависит от реализации. На самом деле, это наоборот. Вопрос, который вы должны задать, заключается в следующем: «ли ваша собственная реализация имеет все точные свойства, которые требуются по алгоритму?» «

Алгоритм имеет очень мало строгих требований. Вам нужен набор узлов и набор ребер, где каждый ребро соединяет 2 узла. Это общее определение графика. То, как вы приобретаете, храните и обрабатываете эти множества, не имеет никакого отношения к алгоритму. Для шага алгоритма все, что вам нужно - это доступ к данному узлу из набора и доступ к набору его соседей. То, что вы представили, кажется прекрасным (конечно, для следующего шага вам нужно перейти к следующему узлу после корня).