그래프의 최소 무게를 찾는

나는 Kruskal의 알고리즘을 사용하여 최소 스패닝 웨이트를 계산하는 프로그램을 만들려고 노력하고 있습니다. 나는 그 순서를 따라 가장자리를 정렬하여 2 차원 목록에 넣었습니다. 는 내가 방법이그래프의 최소 무게를 찾는

vertexcheck = [] 
minimumdistance = 0 
def MSW: 
    for i in range(len(sortededge)): 
     if (sortededge[i][0] not in vertexcheck) or (sortededge[i][1] not in vertexcheck): 
      if (sortededge[i][0] not in vertexcheck): 
       vertexcheck.append(sortededge[i][0]) 


      if (sortededge[i][1] not in vertexcheck): 
       vertexcheck.append(sortededge[i][1]) 
      minimumdistance += int(sortededge[i][2])

입니다 sortededge = [['1', '2', '1'], ['5', '6', '1'], ['2', '4', '2'], ['3', '6', '2'], ['3', '5', '3'], ['4', '6', '3'], ['3', '4', '5'], ['1', '3', '6']] , 샘플에 대해 수행 의 sortededge를 사용하여 최소한의 무게를 얻을 수있는 방법을 쓰기가 있지만 모든 그래프에 대한 작업을 doesnot 그리고 난 어떤 도움을 환영

출처

2014-12-12 Kal

에 오신 것을 환영에 유래하기를! 편집기에서 "{}"단추를 사용하여 코드를 읽을 수있는 형식으로 서식을 지정할 수 있습니다. "작동하지 않는다"는 의미를 지정하십시오. 코드가 실패한 예가 무엇입니까? 이 예에서 실제적이고 예상되는 결과는 무엇입니까? –

알고리즘 구현이 잘못되었습니다.

enter image description here

을 그리고 가장자리를 정렬 한 후 다음과 같이 표시됩니다 :

하면 너 한테이 실패 할 경우 예를 보자

가장자리 : 1의 반복에

1, 2, 1 
    3, 4, 2 
    2, 3, 5

당신은 넣을 것 1 및 2를 정점 검사에서 선택합니다. 업데이트 된 vertexcheck = [1,2]
두 번째 반복에서 정점 검사에 3과 4를 넣습니다. updated vertexcheck = [1,2,3,4]
그러나 세 번째 반복에서 두 정점이 정점 검사에 모두 있기 때문에 2 -> 3 모서리를 추가 할 수 없습니다. 의

이유를 알고 당신이 연결을 시도하는 현재 노드 여부를 알려줍니다 연합-찾기라는 데이터 구조 알고리즘을 사용할 필요가 크루스 칼의 구현을 위해

사실 잘못된 출력을 :(주고 구현 이미 연결되어 :

그들은 이미 그들이 이미 낮은 비용 : 다른 이들을 연결로 연결되어 있기 때문에 가장자리를 건너 뛰고 다음 연결되어있는 경우 ... 구현의 많은으로

이 MST 사용하여 파이썬 사용할 수 있습니다 , 나는 너에게 1 개를주는 것을 성가 시게하지 않을 것이다 :

01 23,516,

당신은 여기에 의사 코드를 찾을 수 있습니다 Kruskal's_algorithm

그리고 샘플 구현 : Kruskal's_implementation

출처

2014-12-14 06:48:44

그래프의 최소 무게를 찾는

답변

관련 문제