topological-sort

0열

1답변

연결이 끊어진 DAG의 토폴로지 정렬 순서

숫자 0, 1, 2가 유성 비순환 그래프의 노드이고 우리의 가장자리가 하나만있는 경우 : 1 -> 2입니다. 올바른 주문은 다음과 같습니다. 1,2,0 0,1,2 1,0,2 정확합니까? 나는 마지막 순서에 대해서만 확신하지 못합니다. 1,0,2 유효합니까?

directed-acyclic-graphs topological-sort 2017-05-17

---

0열

1답변

Gremlin의 위상 별 정렬

Gremlin/TinkerPop 쿼리 언어를 사용하면 방향성이있는 비순환 그래프의 위상 순서를 계산할 수 있습니까? 예를 들어, I는 다음과 같은 순서, 위상 중 하나를 획득하려는 다음 에지 a -> b, a -> d, b -> c, c -> d, e -> c 와 그래프 주어진 : a, b, e, c, d 또는 a, e, b, c, d 또는 e, a,

graph-algorithm gremlin directed-acyclic-graphs topological-sort tinkerpop3 2017-02-07

---

0열

1답변

Topological sort (Kahn 's algorithm) trouble

중첩 for 루프에서 내 머리를 감싸는 데 문제가 있습니다. 위키에 Kahn의 알고리즘을 따르고 있습니다 : Kahn's. outgoingEdge가 각 endArray 요소 (m)에 들어오는 가장자리를 가지고 있는지 테스트하는 방법을 이해할 수 없습니다. 여기 는 내가 지금까지 무엇을 가지고 : 여기 def topOrdering(self, graph):

python algorithm topological-sort 2017-02-13

---

1열

1답변

DAG 및 상위 정렬

"증가하는 사전 번호에 따라 DAG의 정점을 정렬하면 토폴로지 정렬이 발생합니다." 분명히 진실한 진술이 아니지만 나는 그것이 왜 그렇게 보이지 않는 것입니다. 그래프가 지시되고 사이클을 가지지 않는다면 우리가 꼭지점을 방문하는 순서가 반드시 위상 적으로 정렬하는 올바른 순서가되어서는 안됩니까?

directed-acyclic-graphs topological-sort 2017-02-22

---

1열

1답변

트래버스 중 위상 적 정렬?

지향 비순환 그래프를 순회하면서 토폴로지별로 정렬 할 수 있습니까? 내 경우에 해당하는 추가 조건 중 하나는 항상 내 DAG에 들어오는 가장자리가없는 꼭지점 하나가 있다는 것입니다. (내 경우는 하나의 엔트리 파일 만있는 파일 종속성 구조입니다.) 모든 정점을 먼저 찾은 다음 정렬하지 않고 그래프를 가로 지르는 동안 토폴로지별로 정렬 된 목록을 작성할 수

algorithm sorting graph graph-algorithm topological-sort 2017-10-29

---

0열

1답변

BGL (부스트 그래프 라이브러리)을 사용하여 DAG의 모든 토폴로지 정렬 찾기

부스트 그래프 라이브러리를 사용하여 주어진 DAG의 모든 토폴로지 종류를 어떻게 찾을 수 있습니까 G? 가능한 이론적 인 언급을 발견했습니다. 여기에 구현이있는 code도 있습니다. 하지만 처음부터 실제로 시작하고 싶지는 않습니다. BGL을 사용하여 계산하고 싶습니다.

c++ boost topological-sort 2017-02-24

---

1열

1답변

나는 교과서에서이 구절을 가로 질러왔다

토폴로지 정렬과 익스트라의 알고리즘 :. "그래프가 비순환 경우, 우리는 다 익스트라의 알고리즘을 향상시킬 수있는 정점은 정점을 선택하면 이후 위상 순서로 선택 될 수 있으며, 그 거리 알 수없는 노드로부터 들어오는 모서리가 없으므로 더 이상 낮출 수 없습니다. " Topological Sort와 Dijkstra의 알고리즘을 이해하고 있지만 순서가 항상 고

algorithm dijkstra shortest-path topological-sort 2017-01-07

---

0열

1답변

가중 된 비순환 그래프에서 소스 노드에서 다른 모든 노드까지의 최단 경로를 찾기 위해 BFS를 (가장 최적의 방법으로) 사용할 수 있습니까?

위상 정렬을 사용하여 O (V + E)에서 수행 할 수 있음을 알고 있습니다. 그러나 BFS를 사용하여 동일한 복잡성으로도 수행 할 수 있다고 생각합니다.

graph shortest-path breadth-first-search directed-acyclic-graphs topological-sort 2017-04-23

---

0열

1답변

유향 그래프에 단 하나의 토폴로지 정렬이 있는지 확인

유향 그래프에 단 하나의 위상 배열이 있는지 여부를 확인하는 알고리즘에 대한 의사 코드를 작성하려고합니다. 이미 토폴로지 정렬 (DFS 사용)을위한 의사 코드를 생각해 냈습니다.하지만 그다지 도움이되지는 않습니다. 그래프에 싱크대가 없는지 궁금합니다. 하나의 토폴로지 순서가 없습니다 (도움이 될만한가요?).

directed-graph topological-sort 2017-12-30

---

0열

2답변

DAG에 가장자리를 추가하는 것이 지시 된주기를 형성하는지 확인하는 방법은 무엇입니까?

그래프의 모든 버텍스 v에 대해 DAG와 주어진 토폴로지 순서 함수를 가정하면, 2 개의 특정 노드를 볼 때 : x, y는 내가 알고있는 | top (x) -top (y) | < 10 에지 x-> y를 추가하면 그래프에 사이클이 형성되는지 어떻게 알 수 있습니까? 저는 O (V + E)보다 나은 솔루션을 얻으려고합니다 ... 내가 top (x)> top (

algorithm directed-acyclic-graphs topological-sort sanity-check 2017-01-26

---