격리 된 정점을 제거하고 결과 그래프의 정점 순서를 바꿀 수있는 효율적인 방법

Question

제목이 상당히 입소문이지만 여기에 있습니다. 무 직선 모서리와 입력 스트림에서 다수의 정점을 읽고 가장자리 집합을 출력하는 문제에 직면했습니다. 내가 출력하고있는 모서리 세트는 '공백'을 가질 수 없습니다.이 말은 내가 (1, 2), (2, 4) 및 (4, 5)의 모서리를 가질 수 없다는 것입니다. 꼭지점 # 3은 꼭지점 집합에서 언급되지 않습니다.

이 그래프에는 "공백"은 접속에 존재하지 않기 때문에 (2)는 "블랭크"

이 그래프가 허용 될가 허용되지 않을 것이다

그래프. 4 개의 꼭지점이 있으며 1에서 4까지 번호가 매겨집니다.이 그래프의 출력은 [[1, 3] [4, 2] [2, 1]]

입니다. 이것에 관해서는 아직까지 다음과 같습니다 :

나는 얼마나 많은 정점이 있는지를 배울 때 모든 인덱스를 고립 된 모든 정점을 포함하는 HashSet에 추가합니다. 입력 스트림에서 가장자리를 읽으면 HashSet에서 모든 가장자리의 정점을 모두 제거합니다. 그런 다음 치수 (| V |, 2)가있는 2D 배열에 추가합니다. 모든 가장자리를 찍은 후에 고립 된 꼭지점이 있으면 "재정렬 방법"을 호출합니다.

그것은 무엇을합니까?

• 은 반복에 의해 구별되는 정점의 수가 aswell 행렬의 최대 값을 발견 2D 매트릭스와 내 도움-방법 findMatrixProperties에 입력
• 전화 (같은 고립 된 정점의 집합을) 인수합니다 전체 행렬은 중첩 루프를 통해 한 번에 하나의 요소를 나타냅니다.
• 그럼 while while 루프를 입력하십시오. (matrixMax> nrOfVertices)
• while 루프에서 나는 모든 최대 값을 고립 된 정점을 가진 HashSet의 최소값으로 대체하여 전체 행렬을 반복합니다.
• 행렬의 전체 반복을 수행 한 후에는 격리 된 정점 집합에서 최소값을 제거하고 findMatrixProperties()를 다시 호출합니다. 의사에서

이

reorderMethod(matrix M, isolated vertex set I) 
    matrixProperties = findMatrixProperties(M) // matrixProperties is an instance of a helper class MatrixProperty which holds two integers, max and nrOfVertices 
    while (max > nrOfVertices) 
    for row in M 
     for col in M 
     if M[col, row] = max: 
      M[col, row] = min(I) 
    // Remove min(I) from I 
    matrixProperties = findMatrixProperties(M) 

는 어떻게 든이 더 효율적으로 만들 수있는 방법이 있습니까 (프로그램 자체가 자바로 작성)입니까?

Answer 1

질문을 올바르게 이해하면 완전히 연결되지 않은 노드가 연결된 노드보다 작은 레이블을 갖지 않도록 그래프의 정점에 대해 표준 번호 재 지정을 찾으려합니다.

간단히 대답하면 각 꼭지점에 작은 꼭지점의 수가 더한 레이블을 붙이는 것입니다. (0이 아닌 1부터 시작하는 꼭지점에 번호를 붙이 겠지만, 모든 레이블에 쉽게 하나씩 추가 할 수 있습니다.)

인접 목록 대신 부울 NxN 배열을 사용하는 것 같습니다. 그래서 다음과 같이 작성했습니다. 의사 코드. 그러나 인접 목록의 변경은 간단합니다.

먼저 모든 행에 or 연산자를 적용하여 부울 배열을 부울 벡터로 줄입니다. 노드는 전체 행이 false가 아닌 한 무언가에 연결되므로 노드가 연결되었는지 여부를 알려주는 부울 벡터로 충분합니다. 분명히 우리는 첫 번째 true 값을 때 행을 검색 할 때 중지 할 수 있습니다. 그런 다음 부울 벡터를 0과 1의 정수 벡터로 재 해석하고 벡터에 대한 누적 합계와 매우 유사한 것을 수행하여 벡터가 각 엔트리에 대해 더 작은 레이블을 가진 연결된 구성 요소의 수를 포함하게합니다. 결과 벡터는 연결되지 않은 정점을 무시하면 이전 레이블에서 정식 레이블로 정확하게 변환됩니다. (모든 정점에 대한 변환을 구성 할 수 있습니다. 아래의 의사 코드는 연결되지 않은 정점을 마지막 레이블에서 번호를 다시 매김으로써 수행됩니다.)

Java가 의사 용으로 충분하지 않기 때문에 파이썬 형 의사 코드를 사용했습니다. 나를 :)

# M is an adjacency matrix; we assume that it is square. 
# The function returns the translation vector 
def renumber(M): 
    ones = 0 
    zeros = len(M) - 1 
    trans = [] 
    for row in M: 
    if any(row): 
     # the edge is connected 
     trans.append(ones) 
     ones += 1 
    else: 
     # the edge is unconnected 
     zeros -= 1 
     trans.append(zeros) 
    return trans