[algorithm] 두 임의의 정점 사이의 모든 연결을 찾기위한 그래프 알고리즘

이 답변에 제공된 기존 비 재귀 DFS 구현 이 손상된 것 같으므로 실제로 작동하는 것을 제공하겠습니다.

파이썬으로 작성했습니다. 왜냐하면 구현 세부 사항에 의해 꽤 읽기 쉽고 복잡하지 않기 때문입니다 (그리고 생성기yield 를 구현하기위한 편리한 키워드 가 있기 때문입니다 ). 그러나 다른 언어로 이식하는 것은 상당히 쉽습니다.

# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
    visited = set()
    visited.add(start)

    nodestack = list()
    indexstack = list()
    current = start
    i = 0

    while True:
        # get a list of the neighbors of the current node
        neighbors = graph[current]

        # find the next unvisited neighbor of this node, if any
        while i < len(neighbors) and neighbors[i] in visited: i += 1

        if i >= len(neighbors):
            # we've reached the last neighbor of this node, backtrack
            visited.remove(current)
            if len(nodestack) < 1: break  # can't backtrack, stop!
            current = nodestack.pop()
            i = indexstack.pop()
        elif neighbors[i] == end:
            # yay, we found the target node! let the caller process the path
            yield nodestack + [current, end]
            i += 1
        else:
            # push current node and index onto stacks, switch to neighbor
            nodestack.append(current)
            indexstack.append(i+1)
            visited.add(neighbors[i])
            current = neighbors[i]
            i = 0

이 코드는 두 개의 병렬 스택을 유지합니다. 하나는 현재 경로의 이전 노드를 포함하고 다른 하나는 노드 스택의 각 노드에 대한 현재 이웃 인덱스를 포함합니다 (따라서 노드를 다시 꺼낼 때 노드의 이웃을 통해 반복을 재개 할 수 있습니다. 스택). 나는 (노드, 인덱스) 쌍의 단일 스택을 똑같이 잘 사용할 수 있었지만 두 스택 방법이 더 읽기 쉽고 다른 언어 사용자에게 구현하기 더 쉬울 것이라고 생각했습니다.

이 코드는 또한 visited항상 현재 노드와 스택의 모든 노드를 포함 하는 별도의 집합을 사용하여 노드가 이미 현재 경로의 일부인지 여부를 효율적으로 확인할 수 있도록합니다. 언어에 효율적인 스택과 같은 푸시 / 팝 작업 과 효율적인 멤버십 쿼리를 모두 제공하는 “정렬 된 집합”데이터 구조가 있는 경우이를 노드 스택에 사용하고 별도의 visited집합을 제거 할 수 있습니다 .

또는 노드에 대해 사용자 지정 변경 가능한 클래스 / 구조를 사용하는 경우 각 노드에 부울 플래그를 저장하여 현재 검색 경로의 일부로 방문했는지 여부를 나타낼 수 있습니다. 물론,이 방법을 사용하면 같은 그래프에서 두 개의 검색을 병렬로 실행할 수 없습니다.

다음은 위에 주어진 함수가 어떻게 작동하는지 보여주는 테스트 코드입니다.

# test graph:
#     ,---B---.
#     A   |   D
#     `---C---'
graph = {
    "A": ("B", "C"),
    "B": ("A", "C", "D"),
    "C": ("A", "B", "D"),
    "D": ("B", "C"),
}

# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)

주어진 예제 그래프에서이 코드를 실행하면 다음과 같은 출력이 생성됩니다.

A-> B-> C-> D
A-> B-> D
A-> C-> B-> D
A-> C-> D

이 예제 그래프는 방향이 지정되지 않은 반면 (즉, 모든 에지가 양방향으로 이동) 알고리즘은 임의의 방향성 그래프에서도 작동합니다. 예를 들어 C -> B가장자리를 제거하면 ( B의 인접 목록에서 제거 하여 ) 더 이상 불가능한 C세 번째 경로 ( A -> C -> B -> D)를 제외하고 동일한 출력이 생성 됩니다.

추신. 이와 같은 간단한 검색 알고리즘 (및이 스레드에 제공된 다른 알고리즘)이 매우 저조한 성능을 발휘하는 그래프를 구성하는 것은 쉽습니다.

예를 들어, 시작 노드 A에 두 개의 이웃이있는 방향이 지정되지 않은 그래프에서 A에서 B까지의 모든 경로를 찾는 작업을 생각해보십시오. 대상 노드 B (A 이외의 다른 이웃이 없음)와 파벌의 일부인 노드 C 의 N 과 같은 하나의 노드 :

graph = {
    "A": ("B", "C"),
    "B": ("A"),
    "C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
    "G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
    "H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
    "I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
    "J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
    "K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
    "L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
    "M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
    "N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
    "O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}

A와 B 사이의 유일한 경로가 직접적인 경로라는 것을 쉽게 알 수 있지만, 노드 A에서 시작된 순진한 DFS는 (인간에게) 명백한 경우에도 무리 내에서 경로를 탐색하는 데 O ( n !) 시간을 낭비하게됩니다 . 이러한 경로 중 어느 것도 B로 이어질 수 없습니다.

DAG 를 구성 할 수도 있습니다.예를 들어 시작 노드 A가 대상 노드 B와 두 개의 다른 노드 C ₁ 및 C ₂ 를 연결하도록하여 유사한 속성을 가진 를 . 둘 다 노드 D ₁ 및 D ₂ 에 연결되며 둘 다 E에 연결됩니다. ₁ 및 E ₂ 등. 들면 N 이런 배열 노드 층, O 낭비 끝날 B A에서 모든 경로에 대한 검색 나이브 (2 ^N 포기하기 전에 모든 가능한 데드 단부 검사) 시간.

물론, (C 이외) 또는 DAG의 마지막 층으로부터 도당의 노드 중 하나에서 타겟 노드 B로 에지를 추가하는 것 기하 급수적으로 많은 B A에서 가능한 경로의 수, 및를 만들 순전히 로컬 검색 알고리즘은 그러한 에지를 찾을 수 있는지 여부를 미리 알 수 없습니다. 따라서 어떤 의미에서 이러한 순진한 검색의 출력 감도 가 좋지 않은 것은 그래프의 글로벌 구조에 대한 인식 부족 때문입니다.

이러한 “지수 시간 막 다른 골목”중 일부를 피하는 데 사용할 수있는 다양한 전처리 방법 (예 : 리프 노드를 반복적으로 제거, 단일 노드 정점 구분 기호 검색 등)이 있지만 일반적인 방법은 알 수 없습니다. 모든 경우에 그들을 제거 할 수있는 전처리 트릭 . 일반적인 해결책은 검색의 모든 단계에서 대상 노드에 도달 할 수 있는지 (하위 검색을 사용하여) 확인하고 그렇지 않은 경우 조기에 역 추적하는 것입니다.하지만 안타깝게도 검색 속도가 크게 느려집니다 (최악의 경우 , 그래프 크기에 비례 함) 이러한 병리학 적 막 다른 골목을 포함 하지 않는 많은 그래프의 경우 .

답변

public class Search {

private static final String START = "B";
private static final String END = "E";

public static void main(String[] args) {
    // this graph is directional
    Graph graph = new Graph();
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("B", "A");
    graph.addEdge("B", "D");
    graph.addEdge("B", "E"); // this is the only one-way connection
    graph.addEdge("B", "F");
    graph.addEdge("C", "A");
    graph.addEdge("C", "E");
    graph.addEdge("C", "F");
    graph.addEdge("D", "B");
    graph.addEdge("E", "C");
    graph.addEdge("E", "F");
    graph.addEdge("F", "B");
    graph.addEdge("F", "C");
    graph.addEdge("F", "E");
    List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
    String currentNode = START;
    List<String> visited = new ArrayList<String>();
    visited.add(START);
    new Search().findAllPaths(graph, seen, paths, currentNode);
    for(ArrayList<String> path : paths){
        for (String node : path) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {
    if (currentNode.equals(END)) {
        paths.add(new ArrayList(Arrays.asList(visited.toArray())));
        return;
    }
    else {
        LinkedList<String> nodes = graph.adjacentNodes(currentNode);
        for (String node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            List<String> temp = new ArrayList<String>();
            temp.addAll(visited);
            temp.add(node);
            findAllPaths(graph, temp, paths, node);
        }
    }
}
}

B A C E

B A C F E

B E

B F C E

B F E

#include <stdio.h>
#include <stdbool.h>

#define maxN    20

struct  nodeLink
{

    char node1;
    char node2;

};

struct  stack
{
    int sp;
    char    node[maxN];
};

void    initStk(stk)
struct  stack   *stk;
{
    int i;
    for (i = 0; i < maxN; i++)
        stk->node[i] = ' ';
    stk->sp = -1;
}

void    pushIn(stk, node)
struct  stack   *stk;
char    node;
{

    stk->sp++;
    stk->node[stk->sp] = node;

}

void    popOutAll(stk)
struct  stack   *stk;
{

    char    node;
    int i, stkN = stk->sp;

    for (i = 0; i <= stkN; i++)
    {
        node = stk->node[i];
        if (i == 0)
            printf("src node : %c", node);
        else if (i == stkN)
            printf(" => %c : dst node.\n", node);
        else
            printf(" => %c ", node);
    }

}


/* Test whether the node already exists in the stack    */
bool    InStack(stk, InterN)
struct  stack   *stk;
char    InterN;
{

    int i, stkN = stk->sp;  /* 0-based  */
    bool    rtn = false;

    for (i = 0; i <= stkN; i++)
    {
        if (stk->node[i] == InterN)
        {
            rtn = true;
            break;
        }
    }

    return     rtn;

}

char    otherNode(targetNode, lnkNode)
char    targetNode;
struct  nodeLink    *lnkNode;
{

    return  (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;

}

int entries = 8;
struct  nodeLink    topo[maxN]    =
    {
        {'b', 'a'},
        {'b', 'e'},
        {'b', 'd'},
        {'f', 'b'},
        {'a', 'c'},
        {'c', 'f'},
        {'c', 'e'},
        {'f', 'e'},
    };

char    srcNode = 'b', dstN = 'e';

int reachTime;

void    InterNode(interN, stk)
char    interN;
struct  stack   *stk;
{

    char    otherInterN;
    int i, numInterN = 0;
    static  int entryTime   =   0;

    entryTime++;

    for (i = 0; i < entries; i++)
    {

        if (topo[i].node1 != interN  && topo[i].node2 != interN)
        {
            continue;
        }

        otherInterN = otherNode(interN, &topo[i]);

        numInterN++;

        if (otherInterN == stk->node[stk->sp - 1])
        {
            continue;
        }

        /*  Loop avoidance: abandon the route   */
        if (InStack(stk, otherInterN) == true)
        {
            continue;
        }

        pushIn(stk, otherInterN);

        if (otherInterN == dstN)
        {
            popOutAll(stk);
            reachTime++;
            stk->sp --;   /*    back trace one node  */
            continue;
        }
        else
            InterNode(otherInterN, stk);

    }

        stk->sp --;

}


int    main()

{

    struct  stack   stk;

    initStk(&stk);
    pushIn(&stk, srcNode);

    reachTime = 0;
    InterNode(srcNode, &stk);

    printf("\nNumber of all possible and unique routes = %d\n", reachTime);

}

    void DepthFirstIterative(T start, T endNode)
    {
        var visited = new LinkedList<T>();
        var stack = new Stack<T>();

        stack.Push(start);

        while (stack.Count != 0)
        {
            var current = stack.Pop();

            if (visited.Contains(current))
                continue;

            visited.AddLast(current);

            var neighbours = AdjacentNodes(current);

            foreach (var neighbour in neighbours)
            {
                if (visited.Contains(neighbour))
                    continue;

                if (neighbour.Equals(endNode))
                {
                    visited.AddLast(neighbour);
                    printPath(visited));
                    visited.RemoveLast();
                    break;
                }
            }

            bool isPushed = false;
            foreach (var neighbour in neighbours.Reverse())
            {
                if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
                {
                    continue;
                }

                isPushed = true;
                stack.Push(neighbour);
            }

            if (!isPushed)
                visited.RemoveLast();
        }
    }

다음은 테스트 할 샘플 그래프입니다.

    // 샘플 그래프. 숫자는 가장자리 ID입니다.
    // 1 3
    // A --- B --- C ----
    // | | 2 |
    // | 4 ----- D |
    // ------------------