java - 代表节点数目未知的图？

在过去的几天里，我不知道如何将文本文件中的给定图表示为邻接矩阵，而事先不知道图中的顶点数。
输入文件具有定义为字符串的顶点和表示两个顶点之间的边的一对连续线。例如：

VertexA
VertexB
VertexC
VertexD

在上面的例子中，vertexa->vertexb和vertexc->vertexd之间有一条边。有向，权重任意为1。
我想在它自己的类中实现它，该类不直接解析文件，而只有一个方法在给定的源和目标顶点之间添加一个定向。例如：

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

到目前为止，在这个方法中，我已经制作了一个hashmap，如果其中一个顶点不在这个映射中，就用它自己的唯一索引添加它。（键是顶点的名称，值是顶点的索引。）
如何使用这样的方法构造这个邻接矩阵，同时保持这个边信息，但不知道前面的顶点数（v）？
我在想一个阿拉伯主义者的名单，但我不能把我的头围绕着这个。

最佳答案

您可以使用ArrayList of ArrayList并且您的想法非常完美，您可以将Strings映射为唯一的Integerid，然后直接将相应的顶点添加到列表中。
Adjacency Matrix的问题是，您需要知道顶点的最大极限。Adjacency Matrix不是memory efficient也不适用于动态操作所以这里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]