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

Question

VertexA
VertexB
VertexC
VertexD

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

Answer 1

您可以使用ArrayList的ArrayList，您的想法非常完美，您可以将String与唯一的IntegerID映射，然后直接将相应的顶点添加到列表中。

邻接矩阵的问题是需要知道顶点的最大极限。邻接矩阵不内存效率并且对于动态操作也不可行。因此，这里出现了邻接列表。我编写了一个小代码来演示邻接列表的创建，以及如何添加新的顶点或和边。

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]