정점 연결에 대한 알고리즘

Question

유향 그래프의 제곱 G = (V, E)는 u ≠ w 인 경우에만 u → w가 E2에있는 그래프 G2 = (V, E2) u → v와 v → w가 둘 다 E2에있는 버텍스 v가 있습니다. 입력 파일은 정점의 순서쌍으로 임의의 순서로 가장자리를 나열하며 각 가장자리는 별도의 선에 있습니다. 정점은 1에서부터 정점의 총수까지 순서대로 번호가 매겨집니다.

1 6 
1 4 
1 3 
2 4 
2 8 
2 6 
2 5 
3 5 
3 2 
3 6 
4 7 
4 5 
4 6 
4 8 
5 1 
5 8 
5 7 
6 3 
6 4 
7 5 
7 4 
7 6 
8 1 

그렇다면 출력이 될 것이다 :

1: 3 4 7 8 5 2 6 
2: 5 6 3 4 1 8 7 
3: 1 7 8 6 5 4 
4: 5 6 8 7 3 1 
5: 3 1 4 6 
6: 2 7 5 8 
7: 1 5 6 8 3 4 
8: 6 4 3 

우리는 입력 데이터의 예를 보면

* 자기 루프 중복은/병렬 에지

허용되지

나는이 코드를 C로 작성하고있다.

내 생각은 파일을 통해 실행하는 것이다. 포인터가 얼마나 많은지를 결정한 다음 포인터의 배열을 할당합니다. 목록에 1이 들어있는 곳을 다시 검색 한 다음 해당 숫자가 어디에 있는지 찾아 봅니다. 그것의 중복 또는 동일한 번호 (1) 다음 포인터의 배열에서 연결된 목록에 추가합니다. 파일의 모든 정점 번호에 대해이 작업을 수행합니다.

그러나 나는 이것이 매우 비효율적이라고 생각하며이를 수행하는 최선의 방법이 아닙니다. 누구든지 다른 제안이 있다면 나는 매우 감사 할 것입니다.

Answer 1

올바른 결과를 얻으려면 각 노드마다 1과 2의 거리를 가진 모든 노드가 명시된 각 노드에 대한 결과 집합을 작성해야합니다.

따라서 비트 배열의 인접 행렬에서 에지를 유지할 수 있습니다. 비트는 에지가 존재할 때 1이고 그렇지 않은 경우 0입니다.

이제이 행렬에 자체를 곱할 수 있습니다. 이 경우 곱하기는 행과 열에서 AND를 만들 수 있음을 의미합니다.

작은 예 (미안 해요, 제대로 매트릭스를 삽입하는 방법을 모른다) :

0 1 0 0 1 0 0 0 1 
0 0 1 x 0 0 1 = 1 1 0 
1 1 0 1 1 0 0 1 1 

이 매트릭스는 두 단계로 도달 할 수있는 모든 노드에 대한 하나 포함되어 있습니다. 간단히 말해 하나의 단계가 아닌 2 개의 인접 행렬입니다. 이 행렬을 초기 행렬과 OR 연산하면 길이가 1과 2 인 모든 행렬을 유지하는 행렬을가집니다.

이 접근법은 여러 가지 이점이 있습니다. 처음 비트 작업은 매우 빠릅니다. cpu는 계산을 paralyze하고 결과가 하나 인 곳에서 한 쌍이 발견되면 결과 행렬 셀을 멈출 수 있습니다.

또한 행렬 곱셈을 병렬로 계산하는 방법은 잘 설명되어 있습니다.

다른 모든 길이의 patches를 쉽게 계산할 수 있습니다. 길이 K의 하나가 계산하는 경우 : 정점의 잠재적 가치에 따라