그래프의 노드들을 검색하는 방식으로 DFS (depth first search)와 BFS (breath first search)가 있는데, DFS의 경우 현재 노드(A)를 방문한 후, 이웃노드에 대해 다시 DFS 함수를 재귀 호출하는 방식을 취한다. 따라서 현재 노드의 첫번째 이웃노드(B)를 두 번째로 방문하고 다시 그 노드(B)의 첫번째 이웃노드를 세번째로 방문한다. 그래프의 경우 순환 루프가 있을 수 있으므로 어떤 노드를 이미 방문했는지를 표시하기 위해, GraphNode에 방문상태를 나태내는 필드(예를 들어 State)를 두고 이를 방문 플래그로 사용할 수 있다. (다른 방식으로 Hashtable 혹은 HashSet에 방문노드를 기록해가면서 체크할 수도 있다.)

public class GraphNode<T> {
    // csharpstudy.com/DS/graph.aspx 참조
    public VisitState State { get; set; }
}
public enum VisitState {
   Unvisited,        
   Visited
}

public void DFS(GraphNode<T> g) 
{
   // 가정: _nodeList : 그래프안의 GraphNode 리스트 필드
   _nodeList.ForEach(p => p.State = VisitState.Unvisited);
   DFSRecursive(g);
}
void DFSRecursive(GraphNode<T> g)
{
    Console.WriteLine(g.Data); // visit node
    g.State = VisitState.Visited;            
    foreach (var n in g.Neighbers)
    {
        if (n.State == VisitState.Unvisited) {
            DFSRecursive();
        }
    }
}

방향 그래프(Directed Graph)가 순환구조인지를 체크하기 위해서는 위의 DFS 방식으로 검색을 진행하면서 이웃노드중 하나가 이미 방문한 노드로 판명되는 경우 순환 구조임을 알 수 있다.

public bool HasCycle(GraphNode<T> g, bool initStates = true)
{
    if (initStates) {
        _nodeList.ForEach(p => p.State = VisitState.Unvisited);
    }

    g.State = VisitState.Visited;

    foreach (var n in g.Neighbers)
    {
        if (n.State == VisitState.Unvisited) {
            if (HasCycle(n, false))                    
                return true;                    
        }
        else
            return true;
    }            
    return false;
}