두 개의 임의의 정점 사이의 모든 연결을 찾는 그래프 알고리즘
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
아래 설명된 작업을 수행하기 위해 가장 효율적인 시간 효율적인 알고리즘을 결정하려고 합니다.
나는 일련의 기록을 가지고 있습니다.이 레코드 세트에 대해 이 세트의 레코드 쌍이 서로 연결되는 방식을 나타내는 연결 데이터가 있습니다.이는 기본적으로 레코드가 정점이고 연결 데이터가 가장자리인 무방향 그래프를 나타냅니다.
세트의 모든 레코드에는 연결 정보가 있습니다(예:고아 기록이 없습니다.세트의 각 레코드는 세트의 하나 이상의 다른 레코드에 연결됩니다.
나는 세트에서 두 개의 레코드를 선택하고 선택한 레코드 사이의 모든 간단한 경로를 표시할 수 있기를 원합니다."단순 경로"란 경로에 반복되는 레코드가 없는 경로를 의미합니다(예:유한 경로만 해당).
메모:선택한 두 레코드는 항상 다릅니다(예:시작 정점과 끝 정점은 결코 동일하지 않습니다.주기 없음).
예를 들어:
If I have the following records:
A, B, C, D, E
and the following represents the connections:
(A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
(C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)
[where (A,B) means record A connects to record B]
B를 시작 레코드로 선택하고 E를 종료 레코드로 선택한 경우 레코드 B를 레코드 E에 연결하는 레코드 연결을 통해 모든 간단한 경로를 찾고 싶을 것입니다.
All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E
이것은 하나의 예입니다. 실제로는 수십만 개의 레코드가 포함된 세트가 있을 수 있습니다.
해결책
이는 그래프의 깊이 우선 검색을 통해 달성할 수 있는 것으로 보입니다. 깊이 우선 검색은 두 노드 사이의 모든 비순환 경로를 찾습니다. 이 알고리즘은 매우 빠르며 큰 그래프로 확장되어야 합니다(그래프 데이터 구조는 희박하므로 필요한 만큼의 메모리만 사용합니다).
위에서 지정한 그래프에는 방향성(B,E) 간선이 하나만 있는 것으로 나타났습니다.이것은 오타였나요? 아니면 실제로 방향성 그래프인가요?이 솔루션은 관계없이 작동합니다.죄송합니다. C에서는 할 수 없었습니다. 저는 그 분야에 조금 약합니다.그래도 큰 어려움 없이 이 Java 코드를 번역할 수 있을 것으로 기대합니다.
그래프.자바:
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
public class Graph {
private Map<String, LinkedHashSet<String>> map = new HashMap();
public void addEdge(String node1, String node2) {
LinkedHashSet<String> adjacent = map.get(node1);
if(adjacent==null) {
adjacent = new LinkedHashSet();
map.put(node1, adjacent);
}
adjacent.add(node2);
}
public void addTwoWayVertex(String node1, String node2) {
addEdge(node1, node2);
addEdge(node2, node1);
}
public boolean isConnected(String node1, String node2) {
Set adjacent = map.get(node1);
if(adjacent==null) {
return false;
}
return adjacent.contains(node2);
}
public LinkedList<String> adjacentNodes(String last) {
LinkedHashSet<String> adjacent = map.get(last);
if(adjacent==null) {
return new LinkedList();
}
return new LinkedList<String>(adjacent);
}
}
검색.자바:
import java.util.LinkedList;
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");
LinkedList<String> visited = new LinkedList();
visited.add(START);
new Search().depthFirst(graph, visited);
}
private void depthFirst(Graph graph, LinkedList<String> visited) {
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
if (node.equals(END)) {
visited.add(node);
printPath(visited);
visited.removeLast();
break;
}
}
for (String node : nodes) {
if (visited.contains(node) || node.equals(END)) {
continue;
}
visited.addLast(node);
depthFirst(graph, visited);
visited.removeLast();
}
}
private void printPath(LinkedList<String> visited) {
for (String node : visited) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
프로그램 출력:
B E
B A C E
B A C F E
B F E
B F C E
다른 팁
NIST(National Institute of Standards and Technology) 온라인 알고리즘 및 데이터 구조 사전에는 이 문제를 "모든 간단한 경로" 그리고 추천한다 깊이 우선 탐색.CLRS는 관련 알고리즘을 제공합니다.
Petri Nets를 활용한 기발한 기술 발견 여기
여기 제가 생각해낸 의사코드가 있습니다.이것은 특별한 의사코드 방언은 아니지만 따라할 수 있을 만큼 간단해야 합니다.
누구든지 이것을 분리하고 싶어합니다.
[p]는 현재 경로를 나타내는 정점 목록입니다.
[x]는 기준을 충족하는 경로 목록입니다.
[s]는 소스 정점입니다.
[d]는 대상 정점입니다.
[c]는 현재 정점입니다(PathFind 루틴에 대한 인수).
인접한 정점을 찾는 효율적인 방법이 있다고 가정합니다(라인 6).
1 PathList [p]
2 ListOfPathLists [x]
3 Vertex [s], [d]
4 PathFind ( Vertex [c] )
5 Add [c] to tail end of list [p]
6 For each Vertex [v] adjacent to [c]
7 If [v] is equal to [d] then
8 Save list [p] in [x]
9 Else If [v] is not in list [p]
10 PathFind([v])
11 Next For
12 Remove tail from [p]
13 Return
기존의 비재귀 DFS 구현이 이 답변 고장난 것 같습니다. 실제로 작동하는 것을 제공하겠습니다.
나는 이것을 Python으로 작성했는데, 그 이유는 구현 세부 사항이 꽤 읽기 쉽고 깔끔하기 때문입니다(그리고 편리하기 때문입니다). 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다음과 같이 +1 노드:
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를 연결하도록 하여1 그리고 C2, 둘 다 노드 D에 연결됩니다.1 그리고 디2, 둘 다 E에 연결됩니다.1 그리고 E2, 등등.을 위한 N 이렇게 배열된 노드 레이어에서는 A에서 B까지의 모든 경로에 대한 순진한 검색은 결국 O(2)를 낭비하게 됩니다.N) 포기하기 전에 가능한 모든 막다른 골목을 조사하는 시간입니다.
물론 Clique의 노드 중 하나(C 제외) 또는 DAG의 마지막 레이어에서 대상 노드 B에 에지를 추가하면, ~일 것이다 A에서 B까지 기하급수적으로 많은 수의 가능한 경로를 생성하며, 순전히 로컬 검색 알고리즘은 실제로 그러한 가장자리를 찾을지 여부를 미리 알 수 없습니다.그러므로 어떤 의미에서 가난한 사람들은 출력 감도 이러한 순진한 검색의 대부분은 그래프의 전체 구조에 대한 인식이 부족하기 때문입니다.
이러한 "지수 시간 막다른 골목"을 피하기 위해 사용할 수 있는 다양한 전처리 방법(예: 반복적으로 리프 노드 제거, 단일 노드 정점 구분 기호 검색 등)이 있지만 일반적인 방법은 모르겠습니다. 이를 제거할 수 있는 전처리 트릭 모두 사례.일반적인 해결책은 검색의 모든 단계에서 대상 노드에 여전히 도달할 수 있는지 확인하고(하위 검색을 사용하여) 그렇지 않은 경우 조기에 역추적하는 것입니다. 그러나 아쉽게도 그렇게 하면 검색 속도가 크게 느려집니다(최악의 경우). , 그래프 크기에 비례) ~하지 않다 그러한 병리학적 막다른 골목을 포함하고 있습니다.
다음은 2층에 비해 논리적으로 더 보기 좋은 재귀 버전입니다.
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
C 코드의 솔루션.최소한의 메모리를 사용하는 DFS를 기반으로 합니다.
#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);
}
나는 최근에 이와 비슷한 문제를 해결했습니다. 모든 솔루션 대신 가장 짧은에만 관심이 있었습니다.
나는 그래프의 현재 지점과 거기에 도달하기 위해 택한 경로를 포함하는 레코드를 각각 보유하고 있는 상태 대기열을 사용하는 '폭 우선' 반복 검색을 사용했습니다.
시작 노드와 빈 경로가 있는 대기열의 단일 레코드로 시작합니다.
코드를 반복할 때마다 목록의 헤드에서 항목을 꺼내서 그것이 솔루션인지 확인합니다(도착한 노드가 원하는 노드이고, 그렇다면 완료된 것입니다). 그렇지 않으면 새로운 솔루션을 구성합니다. 현재 노드에 연결되는 노드와 이전 노드의 경로를 기반으로 하는 수정된 경로가 있고 끝에 새 점프가 첨부된 대기열 항목입니다.
이제 비슷한 것을 사용할 수 있지만 해결책을 찾았을 때 중단하는 대신 해당 솔루션을 '찾은 목록'에 추가하고 계속하세요.
방문한 노드 목록을 추적해야 합니다. 그래야 자신을 되돌아가지 않을 것입니다. 그렇지 않으면 무한 루프가 발생합니다.
좀 더 의사코드를 원하시면 댓글 등을 게시해 주시면 자세히 설명하겠습니다.
나는 당신이 이것 뒤에 있는 실제 문제를 설명해야 한다고 생각합니다.나는 당신이 시간 효율적인 것을 요구하기 때문에 이렇게 말하는 것입니다. 그러나 문제에 대한 답은 기하급수적으로 늘어나는 것 같습니다!
그러므로 나는 지수적인 것보다 더 나은 알고리즘을 기대하지 않을 것입니다.
나는 역추적을 하고 전체 그래프를 살펴볼 것입니다.순환을 방지하려면 도중에 방문한 모든 노드를 저장하세요.돌아갈 때 노드 표시를 해제합니다.
재귀 사용:
static bool[] visited;//all false
Stack<int> currentway; initialize empty
function findnodes(int nextnode)
{
if (nextnode==destnode)
{
print currentway
return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
findnodes(n);
visited[nextnode]=false;
pop from currenteay
}
아니면 그게 잘못된 걸까요?
편집하다:아, 그리고 잊어버렸어요:해당 노드 스택을 활용하여 재귀 호출을 제거해야 합니다.
기본 원칙은 그래프에 대해 걱정할 필요가 없다는 것입니다. 이는 동적 연결 문제로 알려진 표준 문제입니다.노드가 연결되어 있는지 여부를 확인할 수 있는 방법에는 다음과 같은 유형이 있습니다.
- 빠른 찾기
- 퀵 유니온
- 향상된 알고리즘(둘의 결합)
다음은 최소 시간 복잡도 O(log*n)로 시도한 C 코드입니다. 이는 65536개의 가장자리 목록에 대해 4번의 검색이 필요하고 2^65536의 경우 5번의 검색이 필요함을 의미합니다.알고리즘의 구현을 공유하고 있습니다. 프린스턴대학교 알고리즘 강좌
팁:위에 공유된 링크에서 적절한 설명과 함께 Java 솔루션을 찾을 수 있습니다.
/* Checking Connection Between Two Edges */
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
/*
Data structure used
vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/
/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);
int main() //Main Function
{
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;
printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
printf("File does not exist");
exit(1);
}
while (1)
{
if (first == 0) //getting no. of vertices
{
ch = getc(fp);
if (temp == 0)
{
fseek(fp, -1, 1);
fscanf(fp, "%s", &ch1);
fseek(fp, 1, 1);
temp = 1;
}
if (isdigit(ch))
{
size = atoi(ch1);
vertex = (int*) malloc(size * sizeof(int)); //dynamically allocate size
sz = (int*) malloc(size * sizeof(int));
initalize(vertex, sz, size); //initialization of vertex[] and sz[]
}
if (ch == '\n')
{
first = 1;
temp = 0;
}
}
else
{
ch = fgetc(fp);
if (isdigit(ch))
temp = temp * 10 + (ch - 48); //calculating value from ch
else
{
/* Validating the file */
if (ch != ',' && ch != '\n' && ch != EOF)
{
printf("\n\nUnkwown Character Detected.. Exiting..!");
exit(1);
}
if (ch == ',')
node1 = temp;
else
{
node2 = temp;
printf("\n\n%d\t%d", node1, node2);
if (node1 > node2)
{
temp = node1;
node1 = node2;
node2 = temp;
}
/* Adding the input nodes */
if (!connected(vertex, node1, node2))
add(vertex, sz, node1, node2);
}
temp = 0;
}
if (ch == EOF)
{
fclose(fp);
break;
}
}
}
do
{
printf("\n\n==== check if connected ===");
printf("\nEnter First Vertex:");
scanf("%d", &node1);
printf("\nEnter Second Vertex:");
scanf("%d", &node2);
/* Validating The Input */
if( node1 > size || node2 > size )
{
printf("\n\n Invalid Node Value..");
break;
}
/* Checking the connectivity of nodes */
if (connected(vertex, node1, node2))
printf("Vertex %d and %d are Connected..!", node1, node2);
else
printf("Vertex %d and %d are Not Connected..!", node1, node2);
printf("\n 0/1: ");
scanf("%d", &temp);
} while (temp != 0);
free((void*) vertex);
free((void*) sz);
return 0;
}
void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
vertex[i] = i;
sz[i] = 0;
}
}
int root(int *vertex, int i) //obtaining the root
{
while (i != vertex[i])
{
vertex[i] = vertex[vertex[i]];
i = vertex[i];
}
return i;
}
/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);
/* Adding small subtree in large subtree */
if (sz[i] < sz[j])
{
vertex[i] = j;
sz[j] += sz[i];
}
else
{
vertex[j] = i;
sz[i] += sz[j];
}
}
/* Time Complexity for Search -->lg* n */
int connected(int *vertex, int p, int q) //Checking of connectivity of nodes
{
/* Checking if root is same */
if (root(vertex, p) == root(vertex, q))
return 1;
return 0;
}
늦었을 수도 있지만 여기에 스택을 사용하여 두 노드 사이의 모든 경로를 탐색하는 Casey의 Java에서 동일한 C# 버전의 DFS 알고리즘이 있습니다.항상 그렇듯이 재귀를 사용하면 가독성이 더 좋습니다.
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();
}
}
This is a sample graph to test:
// Sample graph. Numbers are edge ids
// 1 3
// A --- B --- C ----
// | | 2 |
// | 4 ----- D |
// ------------------
find_paths[s, t, d, k]
이 질문은 오래되었으며 이미 답변되었습니다.그러나 동일한 작업을 수행하기 위해 더 유연한 알고리즘을 보여주는 것은 없습니다.그래서 나는 내 모자를 링에 던질 것이다.
나는 개인적으로 다음 형식의 알고리즘을 찾습니다. find_paths[s, t, d, k] 유용합니다. 여기서:
- s는 시작 노드입니다.
- t는 대상 노드입니다.
- d는 검색할 최대 깊이입니다.
- k는 찾을 경로의 수입니다.
프로그래밍 언어의 무한대 형식을 사용하여 d 그리고 k 모든 경로를 제공합니다§.
§ 분명히 방향성 그래프를 사용하고 있고 모든 것을 원하는 경우 방향이 없는 사이의 경로 s 그리고 t 이 작업을 두 가지 방법으로 모두 실행해야 합니다.
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
도우미 기능
저는 개인적으로 재귀를 좋아합니다. 때로는 어려울 수도 있지만, 어쨌든 먼저 도우미 함수를 정의하겠습니다.
def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found)
current_path.append(current)
if current_depth > max_depth:
return
if current == goal:
if len(paths_found) <= number_of_paths_to_find:
paths_found.append(copy(current_path))
current_path.pop()
return
else:
for successor in graph[current]:
self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found)
current_path.pop()
주요 기능
이를 제외하면 핵심 기능은 간단합니다.
def find_paths[s, t, d, k]:
paths_found = [] # PASSING THIS BY REFERENCE
find_paths_recursion(s, t, 0, d, k, [], paths_found)
먼저, 몇 가지 사항을 살펴보겠습니다.
- 위의 의사 코드는 언어의 매시업이지만 Python과 가장 유사합니다(단지 코딩을 했기 때문에).엄격한 복사-붙여넣기는 작동하지 않습니다.
[]초기화되지 않은 목록입니다. 선택한 프로그래밍 언어에 해당하는 목록으로 바꾸세요.paths_found지나가다 참조.재귀 함수가 아무것도 반환하지 않는다는 것은 분명합니다.이를 적절하게 처리하십시오.- 여기
graph어떤 형태로든 가정하고 있다hashed구조.그래프를 구현하는 방법에는 여러 가지가 있습니다.어느 쪽이든,graph[vertex]인접한 정점 목록을 얻습니다. 감독 그래프 - 그에 따라 조정하십시오. - 이는 "버클"(자체 루프), 사이클 및 다중 모서리를 제거하기 위해 사전 처리되었다고 가정합니다.
내 머리 꼭대기에 생각이 있습니다.
- 하나의 연결을 찾으십시오.(경로 길이는 중요하지 않기 때문에 깊이 우선 검색이 아마도 좋은 알고리즘일 것입니다.)
- 마지막 세그먼트를 비활성화합니다.
- 이전에 비활성화된 연결 이전의 마지막 노드에서 다른 연결을 찾아보십시오.
- 더 이상 연결이 없을 때까지 2로 이동합니다.
루프가 포함된 무한 경로를 포함하여 모든 경로를 열거하는 방법을 찾았습니다.
http://blog.vjeux.com/2009/project/project-shortest-path.html
원자 경로 및 순환 찾기
Definition
우리가 원하는 것은 A 지점에서 B 지점으로 가는 가능한 모든 경로를 찾는 것입니다.관련된 주기가 있기 때문에 모든 주기를 살펴보고 열거할 수는 없습니다.대신, 반복되지 않는 원자 경로와 가능한 가장 작은 주기(주기가 반복되는 것을 원하지 않음)를 찾아야 합니다.
내가 원자 경로에 대해 취한 첫 번째 정의는 동일한 노드를 두 번 통과하지 않는 경로입니다.그러나 나는 그것이 모든 가능성을 받아들이는 것이 아니라는 것을 알았습니다.약간의 성찰 끝에 노드는 중요하지 않지만 가장자리는 중요하다는 것을 알았습니다!따라서 원자 경로는 동일한 가장자리를 두 번 통과하지 않는 경로입니다.
이 정의는 편리하며 주기에도 적용됩니다.A 지점의 원자 순환은 A 지점에서 A 지점으로 끝나는 원자 경로입니다.
구현
Atomic Paths A -> B
A 지점에서 시작하는 모든 경로를 얻기 위해 A 지점에서 그래프를 재귀적으로 탐색하겠습니다.자식을 거치는 동안 우리는 이미 지나간 모든 가장자리를 알기 위해 자식 -> 부모 링크를 만들 것입니다.해당 자식으로 이동하기 전에 해당 연결 목록을 순회하고 지정된 가장자리가 이미 통과되지 않았는지 확인해야 합니다.
목적지 지점에 도착하면 찾은 경로를 저장할 수 있습니다.
Freeing the list
연결된 목록을 해제하려고 할 때 문제가 발생합니다.기본적으로 역순으로 연결된 트리입니다.해결책은 해당 목록을 이중 연결하고 모든 원자 경로가 발견되면 시작점에서 트리를 해제하는 것입니다.
그러나 영리한 해결책은 참조 카운팅(Garbage Collection에서 영감을 얻었음)을 사용하는 것입니다.상위 항목에 링크를 추가할 때마다 해당 참조 횟수에 링크가 추가됩니다.그런 다음 경로 끝에 도달하면 참조 카운트가 1인 동안 뒤로 이동하여 자유로워집니다.그보다 높으면 하나만 제거하고 중지하면 됩니다.
Atomic Cycle A
A의 원자주기를 찾는 것은 A에서 A까지의 원자 경로를 찾는 것과 같습니다.그러나 우리가 할 수 있는 몇 가지 최적화가 있습니다.먼저, 목적지 지점에 도착하면 가장자리 비용의 합이 음수인 경우에만 경로를 저장하려고 합니다.우리는 흡수주기만 거치기를 원합니다.
이전에 본 것처럼 원자 경로를 찾을 때 전체 그래프가 순회됩니다.대신 A를 포함하는 강하게 연결된 구성 요소로 검색 영역을 제한할 수 있습니다.이러한 구성 요소를 찾으려면 Tarjan의 알고리즘을 사용하여 그래프를 간단히 탐색해야 합니다.
원자 경로와 순환 결합
이 시점에서 우리는 A에서 B로 가는 모든 원자 경로와 각 노드의 모든 원자 주기를 갖고 있으며, 최단 경로를 얻기 위해 모든 것을 구성하는 일은 우리에게 맡겨져 있습니다.이제부터 원자 경로에서 원자주기의 최적 조합을 찾는 방법을 연구하겠습니다.
다른 포스터 중 일부에서 훌륭하게 설명된 것처럼 간단히 말해서 문제는 깊이 우선 검색 알고리즘을 사용하여 통신 종료 노드 사이의 모든 경로 조합에 대해 그래프를 반복적으로 검색하는 것입니다.
알고리즘 자체는 사용자가 제공한 시작 노드에서 시작하고, 나가는 모든 링크를 검사하고, 나타나는 검색 트리의 첫 번째 하위 노드를 확장하여 진행하고, 대상 노드를 찾을 때까지 또는 노드를 만날 때까지 점점 더 깊게 검색합니다. 그건 아이가 없어요.
그런 다음 검색은 역추적되어 아직 탐색이 완료되지 않은 가장 최근 노드로 돌아갑니다.
나 블로그에 올렸던 아주 최근에 이 주제에 대해 프로세스에 C++ 구현 예제를 게시했습니다.
Casey Watson의 답변에 추가하여 또 다른 Java 구현이 있습니다.시작 노드로 방문한 노드를 초기화합니다.
private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
for(String node : adjacent){
if(visitedNodes.contains(node)){
continue;
}
if(node.equals(END)){
visitedNodes.add(node);
printPath(visitedNodes);
visitedNodes.removeLast();
}
visitedNodes.add(node);
getPaths(graph, visitedNodes);
visitedNodes.removeLast();
}
}
