JGraphT를 써서 최소걸침나무(minimum spanning tree)를 구현할 때 주의 점

JGraphT에서 가중치 그래프 (weighted graph)를 써보면 가중치가 잘 입력 안될 때가 있다.

예를 들어, 최소걸침나무를 찾는 함수를 구현할 때, 가중치가 잘 입력되지 않는다.

아래 예시 코드를 보면,

public static SimpleWeightedGraph<String,DefaultWeightedEdge> getMST(SimpleWeightedGraph<String,DefaultWeightedEdge> G) {
		SimpleWeightedGraph<String,DefaultWeightedEdge> MST = new SimpleWeightedGraph<String,DefaultWeightedEdge>(DefaultWeightedEdge.class);
		HashSet<String> inMST = new HashSet<String>();
		HashSet<String> inG = new HashSet<String>();
		
		for (int i = 0; i < G.vertexSet().size(); i++) {
			String v = G.vertexSet().toArray()[i].toString();
			inG.add(v);
		}

		while(inG.size() > 1) {
		
			String minV = "";
			DefaultWeightedEdge minEdge = new DefaultWeightedEdge();
			double minWeight = Double.MAX_VALUE;
			for (int i = 0; i < inG.size()-1; i++) {
				String v1 = inG.toArray()[i].toString();
				for (int j = i+1; j < inG.size(); j++) {
					String v2 = inG.toArray()[j].toString();
					
					DefaultWeightedEdge e = G.getEdge(v1, v2);
					double weight = G.getEdgeWeight(e);
					if(weight < minWeight) {
						minEdge = e;
						minWeight = weight;
						minV = v1;
					}
				}
			}

			String v1 = G.getEdgeSource(minEdge);
			String v2 = G.getEdgeTarget(minEdge);
			MST.addVertex(v1);
			MST.addVertex(v2);
			MST.addEdge(v1,v2);
			
			// 틀린 예제
			MST.setEdgeWeight(minEdge, minWeight);
			
			// 맞는 예제
			DefaultWeightedEdge eMST = MST.getEdge(v1, v2);
			MST.setEdgeWeight(eMST, minWeight);

			inMST.add(minV);
			inG.remove(minV);
		}

		return MST;
	}

함수 getMST에서 최소 가중치를 찾아서 MST 그래프에 입력해주는 부분을 보면 노란 배경색으로 틀린 코드와 맞는 코드를 보였습니다.

틀린 코드처럼 가중치를 입력하면, 함수로 반환 받은 그래프에서 가중치가 모두 1로 설정됩니다.

그래서 맞는 코드처럼 새로 만든 MST 그래프에서 DefaultWeightedEdge를 받아온 후에 가중치를 입력해줘야 합니다.