그래프의 경로 계산

Question

그래프의 모든 경로를 사용하여 목록을 만드는 방법을 만들어야합니다. 내 그래프에는 시작 노드와 끝 노드가 하나만 있습니다. 각 노드에는 자식과 다른 목록이 부모 목록에 있습니다. 모든 경로가 포함 된 다른 목록을 만들어야합니다 (각 목록은 다른 목록에 있음)

의견이 있습니까?

Answer 1

(조합을 사용하여) 모든 가능한 정점 조합을 생성하고 존재하지 않는 경로를 필터링 할 수 있습니다 (정점이 모서리로 결합되지 않았거나 모서리의 방향이 틀린 경우).

조합을 생성하는 코드에서 현재 버텍스에서 사용할 수있는 나머지 버텍스를 확인하면이 기본 아이디어를 향상시킬 수 있습니다.

이것은 모두 비순환 그래프가 있다고 가정하고 각 꼭지점을 정확히 한 번 방문하기를 원합니다.

Answer 2

비순환인지 여부에 달려 있습니다. 명확하게 순환은 무한 경로 (한 번 루프 반복, 두 번 라운드, 세 번 라운드 ... 등)가 발생합니다. 그래프가 비 주기적이라면 깊이 우선 탐색 (DFS) (http://en.wikipedia.org/wiki/Depth-first_search)을 수행하고 대상 노드에 도달 한 횟수를 계산할 수 있어야합니다.

Answer 3

먼저 기본 그래프 알고리즘 (교과서 또는 Google)을 익히십시오. 어떤 문제가 해결중인 문제에 가장 잘 맞는지 파악하고 구현하십시오. 알고리즘을 약간 조정해야 할 수도 있지만 일반적으로 모든 기본 그래프 문제에 대해 널리 알려진 알고리즘이 있습니다.

Answer 4

이 같은 것을 보이는 GraphNode 클래스가있는 경우 :

public class GraphNode 
{ 
    public IEnumerable<GraphNode> Children { get; set; } 
    // ... 
} 

다음이이 일을 sould :

public static class GraphPathFinder 
{ 
    public static IEnumerable<IEnumerable<GraphNode>> FindAllPathsTo(this GraphNode startNode, GraphNode endNode) 
    { 
     List<IEnumerable<GraphNode>> results = new List<IEnumerable<GraphNode>>(); 
     Stack<GraphNode> currentPath = new Stack<GraphNode>(); 
     currentPath.Push(startNode); 

     FindAllPathsRecursive(endNode, currentPath, results); 

     return results; 
    } 

    private static void FindAllPathsRecursive(GraphNode endNode, Stack<GraphNode> currentPath, List<IEnumerable<GraphNode>> results) 
    { 
     if (currentPath.Peek() == endNode) results.Add(currentPath.ToList()); 
     else 
     { 
      foreach (GraphNode node in currentPath.Peek().Children.Where(p => !currentPath.Contains(p))) 
      { 
       currentPath.Push(node); 
       FindAllPathsRecursive(endNode, currentPath, new List<IEnumerable<GraphNode>>()); 
       currentPath.Pop(); 
      } 
     } 
    } 
} 

그것은 DFS 알고리즘의 간단한 구현입니다를. 오류 검사, 최적화, 스레드 안전 등 ...

또한 그래프가 순환하지 않는다고 확신하는 경우 마지막 메서드에서 foreach 문에서 where 절을 제거 할 수 있습니다.

희망이 도움이되었습니다.