java - 表示具有未知节点数的图？

Question

在过去的几天里，如果事先不知道图中的顶点数量，我无法考虑如何将文本文件中的给定图表示为邻接矩阵。

输入文件具有定义为字符串的顶点和一对表示两个顶点之间的边的连续线。例如:

VertexA
VertexB
VertexC
VertexD

在上例中有一条边从 VertexA -> VertexB 和 VertexC -> VertexD。有向，权重任意取1。

我想在它自己的类中实现这个它不直接解析文件，而是只有一个方法，它在给定的源顶点和目标顶点之间添加一个定向。例如:

// adds a directed edge from vertex1 -> vertex2
addEdgeBetweenVertices(String vertex1, String vertex2);

到目前为止，在这个方法中，我已经创建了一个 HashMap，如果其中一个顶点不在 map 中，则将其添加到它自己的唯一索引中。 (键是顶点的名称，值是它的索引。)

我如何使用这种方法构造这个邻接矩阵，同时保持这个边缘信息，但不知道之前的顶点数 (|V|)？

我在想一个 ArrayList 的 ArrayList，但我无法解决这个问题。

Answer 1

您可以使用 ArrayList of ArrayList 并且您的想法很完美，您可以将 String 映射到唯一的 Integer id，然后直接添加列表的相应顶点。

邻接矩阵 的问题是您需要知道顶点的最大限制。 邻接矩阵 内存效率不高 并且对于动态操作也不可行。所以这里 Adjacency List 出现了。我写了一段小代码来演示邻接列表的创建以及如何添加新的 Vertex 或 Edge。

import java.util.ArrayList;
import java.util.HashMap;

public class AdjacencyListDemo {

    static int availableId=0;                            //Represents the available id for mapping
    static HashMap<String,Integer> mapping;              //To store the String-Integer mapping for Vertexes
    static ArrayList<ArrayList<Integer>> adjacencyList;

    public static void main(String args[])
    {
        adjacencyList = new ArrayList<ArrayList<Integer>>();

        mapping  = new HashMap<String,Integer>();

        String sampleVertexes[] = {"Vertex1","Vertex2","Vertex3","Vertex4"};

        for(String vertex : sampleVertexes)
            addNewVertex(vertex);

        addEdgeBetween("Vertex1","Vertex2");
        addEdgeBetween("Vertex3","Vertex4");

        System.out.println("Old List: ");
        printList();

        //Add New Vertex if required
        addNewVertex("Vertex5");

        addEdgeBetween("Vertex5","Vertex1");
        addEdgeBetween("Vertex2","Vertex1");
        addEdgeBetween("Vertex3","Vertex2");
        addEdgeBetween("Vertex5","Vertex2");

        System.out.println("\n\nNew List: ");
        printList();

    }

    private static void printList()
    {
        for(String vertex : mapping.keySet()) {
            int index = mapping.get(vertex);
            System.out.println(vertex+" ID: "+index+" List: "+adjacencyList.get(index));
        }
    }
    private static void addEdgeBetween(String vertex1, String vertex2) {
        //get both indexes
        int index1 = mapping.get(vertex1);
        int index2 = mapping.get(vertex2);

        //add index2 into the arraylist of index1 
        adjacencyList.get(index1).add(index2);
    }

    private static void addNewVertex(String vertex) {

        if(!mapping.containsKey(vertex))
        {  
            //assign available ID
            mapping.put(vertex,availableId);
            availableId++;                                   //make increment in available id
            adjacencyList.add(new ArrayList<Integer>());     //Add an Empty ArrayList
        }
    }
}

输出:

Old List: 
Vertex2 ID: 1 List: []
Vertex3 ID: 2 List: [3]
Vertex1 ID: 0 List: [1]
Vertex4 ID: 3 List: []


New List: 
Vertex2 ID: 1 List: [0]
Vertex3 ID: 2 List: [3, 1]
Vertex1 ID: 0 List: [1]
Vertex4 ID: 3 List: []
Vertex5 ID: 4 List: [0, 1]