白駿1197号最小生成ツリー

🛠 デザイン

💻 コード#コード#

グラフィック設定

	Graph g = new Graph(V);

        for(int i = 0; i < E; ++i){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            g.addEdge(new Edge(a, b, w));
            g.addEdge(new Edge(b, a, w));
        }

必要な資料構造。

        PriorityQueue<Edge> pq = new PriorityQueue<>(); // 가중치가 최소인 간선을 도출하기 위한 우선 순위 큐
        Queue<Integer> queue = new LinkedList<>(); // MST를 구성하는 정점 후보를 담고 있는 queue
        boolean[] visited = new boolean[V + 1]; // 정점 방문 체크 배열

プリフェッチアルゴリズム

        queue.add(1); // 시작 단계에서 한 정점을 기준으로 잡아준다.
        while(!queue.isEmpty()){
            int minV = queue.poll();
            visited[minV] = true;
            // 정점 minV와 간선으로 연결된 곳 중 방문하지 않은 정점을 우선 순위 큐에 추가
            for(Edge e : g.edgeList[minV]){
                if(!visited[e.end]) pq.add(e);
            }

            while(!pq.isEmpty()){
                // minE는 가중치가 가장 작은 간선
                Edge minE = pq.poll();
                //간선 minE의 목적지가 아직 방문하지 않은 곳이라면
                if(!visited[minE.end]){
                   // MST를 구성하는 정점 후보에 minE의 목적지를 담고 가중치 총 합에 가중치를 더해준다.
                    queue.add(minE.end);
                    visited[minE.end] = true;
                    sum += minE.weight;
                    break;
                }
            }
        }

        System.out.println(sum);

📝 ポスト

          for(Edge e : g.edgeList[minV]){
              if(!visited[e.end]) pq.add(e);
          }