graph-theory

2열

1답변

중첩 상자 알고리즘 - 중첩 된 인형을 기반으로하지만 근본적으로 다른 알고리즘?

SPOJ 중첩 된 인형 문제와 관련된 문제를 해결하려고했습니다. 여기서는 단일 배율 매개 변수가 다른 인형 대신 2 차원 아래 상자가 사용되었습니다. 나는 알고리즘을 가지고 있지만 문제에 대한 실제 이론과 더 나은 접근법이 존재하는지에 대해 매우 진흙 투성이입니다. 누구든지 문제를 더 잘 이해하고 더 나은 알고리즘을 찾도록 도와 줄 수 있습니까? 재교육로서

0열

1답변

정확한 1800 개의 해밀턴 경로를 가진 7 개의 꼭지점 단순 그래프 그리기

'Graph Theory 소개'에서 강의를 준비하면서이 질문을 보았습니다. 나는 누군가가 그러한 질문 (당신이 정점의 수와 해밀턴 또는 유클리드 경로를 지정하고 그래프의 구조를 묻는 곳)에 접근하는 방법론을 제공하면 크게 감사 할 것입니다.

0열

1답변

색도에 대한 빠른 정확도 해석기

그래프의 반음계 수를 찾는 것은 NP 하드 문제이므로 '이론적으로는'빠른 솔버가 없습니다. 그래프의 정확한 반음계 수를 신속하게 계산할 수있는 공개적으로 사용 가능한 소프트웨어가 있습니까? 많은 그래프의 반음계를 계산하는 Python 스크립트를 작성하고 있지만 작은 그래프의 경우에도 너무 오래 걸립니다. 그래프 나는 스파 스 또는 밀도가 있지만 일반적으로

0열

1답변

Cytoscape.js를 사용하여 모든 노드에서 중심 기능 수행

그래프의 모든 노드에 대해 degree, 근접성 및 중심성을 계산해야합니다. 현재 cy.ready() 이벤트 이후 각 노드의 Cytoscape.js에 내장 된 기능을 사용하고 있습니다. 그러나 그래프가 상당히 크기 때문에 (250 + 노드, 650+ 연결) 계산 시간이 너무 오래 걸립니다. 누구든지보다 효율적인 방법을 제안 할 수 있습니까? var calc

1열

1답변

재귀 스트리밍 API

현재 재귀 깊이 우선 검색을 사용하는 작은 그래프 이론 알고리즘을 연구 중입니다. 반복적이므로 스트림 API를 사용하여 이러한 작업을 수행하거나 반복자를 사용하고 각 루프에 사용해야하는지 스스로 묻습니다. 100 %가 의도 작동 private void processNext(Node node) { //METHOD A for (Node neighbo

1열

1답변

Directed Acyclic Graph의 노드에 최신 시작 시간 설정

노드 노드의 개체로 구성된 DAG를 만들었습니다. 모든 노드는 자신의 가장 빠른 시작 시간, 가장 빠른 종료 시간 및 자체 시간을 알고 있습니다. 모든 노드에는 List<Task> innNodes 및 List<Task> outNodes도 있습니다. 내가 지금까지 한 것은 토폴로지 정렬을 사용하여 정렬하는 것입니다. 이 그래프에서 모든 노드의 최신 시작 시간

-1열

1답변

알고리즘 설계, 유향 그래프 알고리즘 구현

알고리즘 설계와 관련된이 흥미로운 질문을 발견했습니다. 제대로 풀 수 없었습니다. adjancency 목록을 사용하는 유향 그래프 G = (V, E) 및 정수 K < 감안 | V |가 선형 시간 복잡도의 알고리즘을 구현할 (O (N)), 만약 확인 그래프 G는 동일한 실수를 갖는 적어도 k 개의 꼭지점을 갖는다. n == | V | + | E |

1열

1답변

C++ : 트리의 모든 노드 쌍 사이의 거리를 계산하는 BFS

나는 인접리스트 형태로 저장된 N 버텍스가있는 가중치 트리를가집니다. M 노드 목록이 있습니다.이 using namespace std; #define MAX_N (1<<17) #define MAX_V (1<<17) typedef pair<int,int> pii; vector<pii> adj[MAX_V]; bool vis[MAX_N]; //ma

1열

2답변

std :: sort를 사용하여 종속성 트리 정렬

여러 가지 플러그인을 종속성별로 정렬하여 충돌없이 선형 적으로로드 할 수있게하려고합니다. 종속성주기는 계약에 의해 제외됩니다 (정의되지 않은 동작이 발생 함). 가장자리가 잎을 향하는 깊이 2의 이진 트리를 상상해보십시오. 이것이 인공적인 의존성 트리라고합시다. 가장자리의 세트는 가 나는 우를 달성하기 위해 좌에 따라 관계를 나타내는 비교와 표준 : 종류를

0열

1답변

트리의 모든 노드에 대한 최대 거리를 선형 시간으로 찾으십시오.

노드의 최대 거리를 노드의 노드와 트리의 다른 모든 노드 사이의 거리 중 최대 값으로 정의하십시오. . 내 문제는 트리 내에서 모든 노드의 최대 거리를 찾아서 인쇄하는 것입니다 (반드시 바이너리가 아닌). 기본적으로 각 노드마다, 우리가보고있는 노드와 트리 내의 다른 노드 사이에 노드가 가지고있는 최대 거리를 출력해야합니다. 런타임은 O (n) 일 것으로