图形邻接列表，拓扑排序使顶点名称为字符串，而不是Int的* Updated *

Question

因此，我有这段代码可以创建边并使用TopoSort遍历它们，它可以按预期工作，但是我希望能够将每个顶点的名称更改为字符串。我这样做是为了让我可以根据学校提供给我们的图表查看按特定顺序上的哪些课。感谢您的任何帮助，谢谢！

编辑：我能够尝试同时添加地图和列表以具有indexToLabel和labelToIndex。我在使用int而不是最后一个数组时一直遇到错误，我担心在填充表格时会出现空指针异常。

import java.util.*;

class Graph {

    private int V;
    private LinkedList<Integer> adj[];

    //Constructor
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    Map<String, Integer> labelToIndex;
    List<String> indexToLabel;

    // Function to add an edge into the graph
    void addEdge(String v, String w, Integer i) {
        labelToIndex.put(v, i);
        indexToLabel.add(v);
        adj[labelToIndex.get(v)].add(labelToIndex.get(w));
    }

    // A recursive function used by topologicalSort
    void topologicalSortUtil(int v, boolean visited[], Stack stack) {
        // Mark the current node as visited.
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this
        // vertex
        Iterator<Integer> it = adj[v].iterator();
        while (it.hasNext())
        {
            i = it.next();
            if (!visited[i])
                topologicalSortUtil(i, visited, stack);
        }

        // Push current vertex to stack which stores result
        stack.push(new Integer(v));
    }

    // The function to do Topological Sort. It uses
    // recursive topologicalSortUtil()
    void topologicalSort()
    {
        Stack stack = new Stack();

        // Mark all the vertices as not visited
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive helper function to store
        // Topological Sort starting from all vertices
        // one by one
        for (int i = 0; i < V; i++) {
            if (visited[i] == false) {
                topologicalSortUtil( i, visited, stack );
            }
        }

        // Print contents of stack
        while (stack.empty()==false) {
            System.out.print(indexToLabel[stack.pop()] + " " );
        }
    }
}

Answer 1

首先，恭喜您尝试使用计算机科学解决一个很酷的问题。

由于所有内容都已在使用索引，所以最简单的方法是添加一个或两个表，使您可以轻松地将其从顶点索引转换为字符串标签，并在需要时再次返回。

第一个是String的数组，或者-如果您选择--List<String> indexToLabel。第二个是Map<String, Integer> labelToIndex。创建图形时，请填写以下表格。然后打印出结果名称只需更改

System.out.print(stack.pop() + " ");

to

System.out.print(indexToLabel[stack.pop()] + " ");

例如，第二个表将很有用，以允许通过标签添加边：

void addEdge(String v, String w) {
  adj[labelToIndex.get(v)].add(labelToIndex.get(w));
}

欢呼声。