如何找到无向图中到达其他节点的最少顶点数

Question

我的高中老师布置了一个最终项目，您必须在无向图中找到到达其他节点的最少顶点数。在图中，顶点被标记为社区，最小顶点的子集被称为消防站。

老师说我们必须“找到最少数量的位置，以便所有社区都受到保护。如果社区内有消防站或邻近社区之一有消防站，则该社区被视为受到保护”。

附图是老师指定的图，Fs应该是最小的顶点数，但我不知道如何编写搜索图并确定顶点的算法。请让您的回答尽可能简单，因为我是初学者，水平不太好。

我尝试彻底迭代每个顶点，尝试获取度数最高的顶点，然后将其相邻顶点及其自身标记为已访问。然而，我认为这种方法行不通，而且我编写的代码并没有真正反映出这一点，因为我真的不知道我在做什么。另外，我使用哈希映射，其中键代表顶点，值代表其相邻顶点。我写的代码如下。如果难以阅读，请见谅。

import java.io.FileNotFoundException;
import java.util.*;
import java.io.File;
public class FireStationPlacement {

    public static void main(String[] args) {
    Map<String, List<String>> graphExample = new HashMap<>();
    try {
        Scanner Layout2 = new Scanner( new File("text/stuff.txt") );  
        for (int x=0;x<5;x++) {
            graphExample.put(Layout2.next(), Arrays.asList(Layout2.next()));
        }
        for (int x=0;x<19;x++) {
            graphExample.put(Layout2.next(), Arrays.asList(Layout2.next(), Layout2.next()));
        }      
        for (int x=0;x<7;x++) {
                graphExample.put(Layout2.next(), Arrays.asList(Layout2.next(), Layout2.next(),Layout2.next()));
        }
         
        Layout2.close();
    } 
    catch (FileNotFoundException e) {
        // TODO Auto-generated catch block
        System.err.println( "File not found" );
    }

    Set<String> dominatingSet = minVertexCover(graphExample);
    System.out.println("Dominating set: " + dominatingSet);

    }
    
     
    public static int getDegree(Map<String, List<String>> graph, Set<String> visited, String vertex) {
        int degree = 0;
        List<String> neighbors = graph.get(vertex);
        for (String neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                degree++;
            }
        }
        return degree;
    }

    private static Set<String> minVertexCover(Map<String, List<String>> graph) {
        Set<String> fireStations = new HashSet<>();
        Set<String> visited = new HashSet<>();
        for (String node: graph.keySet()) {
            
            if (!visited.contains(node)) {

                int maxDegree = 0;
                String highestVertex = null;
                boolean validPlacement = true;
                visited.add(node);
                 
                int degree = getDegree(graph, visited, node);
                if (degree>maxDegree) {
                    maxDegree = degree;
                    highestVertex = node;
                }
                 
                
                if (highestVertex!=null) {
                    for (String adjacents: graph.get(highestVertex)) {
                        if (visited.contains(adjacents)) {
                            validPlacement = false;
                        }
                    }
                    if (validPlacement) {
                        fireStations.add(highestVertex);    
                     
                        visited.add(highestVertex);
                    }
                }   
            }
        }
        return fireStations;

        }

}

Answer 1

要找到无向图中到达其他节点的最少顶点数，可以使用原始图的补图。如果补图是断开的，那么补图的任意连通分量是这样的：在原图中，连通分量的每个顶点都连接到连通分量1之外的所有顶点。到达所有其他连通分量所需的最少顶点数原图中的节点是补图1的最小连通分量的大小。 如果补图是连通的，那么不存在这样一组顶点可以到达原图中的所有其他节点