java - 使用文本文件中的数据的符号有向图

Question

我被困住了，我将不胜感激。我目前正在学习算法，但我不知道从哪里开始。

我最近收到了代码(我们只真正完成了理论，所以看到代码让我感到害怕)而且我的任务是修改此代码以从文本文件中获取详细信息并将其放入图表中。文本文件与此类似。

Trout is-a fish
Fish has gills
Fish has fins
Fish is food
Fish is-an animal

里面还有很多。我只是想知道。我将如何开始这整件事？我必须问一百万个问题，但我觉得如果我知道如何使用文本文件分配顶点，我就可以解决这些问题？我提供并必须编辑的代码如下。任何帮助都会很棒，如果您愿意，只需朝正确的方向插入即可。

(另外，在 addEdge 类中权重到底是什么？我知道这是遍历边缘的“成本”，但我如何分配权重？)

谢谢!

public class Graph {
    private final int MAX_VERTS = 20;
    private final int INFINITY = 1000000;
    private Vertex vertexList[]; // list of vertices
    private int adjMat[][]; // adjacency matrix
    private int nVerts; // current number of vertices
    private int nTree; // number of verts in tree
    private DistPar sPath[]; // array for shortest-path data
    private int currentVert; // current vertex
    private int startToCurrent; // distance to currentVert
// -------------------------------------------------------------
    public Graph() // constructor
    {
    vertexList = new Vertex[MAX_VERTS];
    // adjacency matrix
    adjMat = new int[MAX_VERTS][MAX_VERTS];
    nVerts = 0;
    nTree = 0;
    for(int j=0; j<MAX_VERTS; j++) // set adjacency
        for(int k=0; k<MAX_VERTS; k++) // matrix
            adjMat[j][k] = INFINITY; // to infinity
    sPath = new DistPar[MAX_VERTS]; // shortest paths
    } // end constructor
// -------------------------------------------------------------
    public void addVertex(char lab)
    {
    vertexList[nVerts++] = new Vertex(lab);
    }
// -------------------------------------------------------------
    public void addEdge(int start, int end, int weight)
    {
    adjMat[start][end] = weight; // (directed)
    }
// -------------------------------------------------------------
    public void path() // find all shortest paths
    {
    int startTree = 0; // start at vertex 0
    vertexList[startTree].isInTree = true;
    nTree = 1; // put it in tree
    // transfer row of distances from adjMat to sPath
    for(int j=0; j<nVerts; j++)
    {
        int tempDist = adjMat[startTree][j];
        sPath[j] = new DistPar(startTree, tempDist);
    }
    // until all vertices are in the tree
    while(nTree < nVerts)
    {
        int indexMin = getMin(); // get minimum from sPath
        int minDist = sPath[indexMin].distance;
        if(minDist == INFINITY) // if all infinite
        { // or in tree,
            System.out.println("There are unreachable vertices");
            break; // sPath is complete
        }
        else
        { // reset currentVert
            currentVert = indexMin; // to closest vert
            startToCurrent = sPath[indexMin].distance;
            // minimum distance from startTree is
            // to currentVert, and is startToCurrent
        }
        // put current vertex in tree
        vertexList[currentVert].isInTree = true;
        nTree++;
        adjust_sPath(); // update sPath[] array
   } // end while(nTree<nVerts)
    displayPaths(); // display sPath[] contents
    nTree = 0; // clear tree
    for(int j=0; j<nVerts; j++)
        vertexList[j].isInTree = false;
    } // end path()
// -------------------------------------------------------------
    public int getMin() // get entry from sPath
    { // with minimum distance
    int minDist = INFINITY; // assume minimum
    int indexMin = 0;
    for(int j=1; j<nVerts; j++) // for each vertex,
    { // if it’s in tree and
        if( !vertexList[j].isInTree && // smaller than old one
            sPath[j].distance < minDist )
        {
            minDist = sPath[j].distance;
            indexMin = j; // update minimum
        }
    } // end for
    return indexMin; // return index of minimum
    } // end getMin()
// -------------------------------------------------------------
    public void adjust_sPath()
    {
    // adjust values in shortest-path array sPath
    int column = 1; // skip starting vertex
    while(column < nVerts) // go across columns
    {
    // if this column’s vertex already in tree, skip it
    if( vertexList[column].isInTree )
    {
        column++;
        continue;
    }
    // calculate distance for one sPath entry
    // get edge from currentVert to column
    int currentToFringe = adjMat[currentVert][column];
    // add distance from start
    int startToFringe = startToCurrent + currentToFringe;
    // get distance of current sPath entry
    int sPathDist = sPath[column].distance;
    // compare distance from start with sPath entry
    if(startToFringe < sPathDist) // if shorter,
    { // update sPath
        sPath[column].parentVert = currentVert;
        sPath[column].distance = startToFringe;
    }
    column++;
    } // end while(column < nVerts)
    } // end adjust_sPath()
// -------------------------------------------------------------
    public void displayPaths()
    {
        for(int j=0; j<nVerts; j++) // display contents of sPath[]
    {
        System.out.print(vertexList[j].label + "="); // B=
        if(sPath[j].distance == INFINITY)
            System.out.print("inf"); // inf
        else
            System.out.print(sPath[j].distance); // 50
        char parent = vertexList[ sPath[j].parentVert ].label;
        System.out.print("(" + parent + ") "); // (A)
    }
        System.out.println("");
    }
// -------------------------------------------------------------
} // end class Graph

Answer 1

我画图的方式是我有一个列表或边数组，而不是将这些信息存储在矩阵中。我会创建一个包含两个节点的内部边类，因为这是一个有向图，两个节点必须彼此不同。您还可以使用边类而不是 DistPar 类来跟踪最短路径。 (或者您可以重新利用 distPar 类来为您实现边缘功能)。

权重是赋予边的属性。我喜欢使用的类比是航线。想象一下，有一条从纽约到洛杉矶的航线，但在这架飞机上买一张机票需要 300 美元，但是，如果你选择了一条通过转机机场的航线，机票只需 150 美元。在这种情况下，您可以将每个机场视为一个节点，机场之间的航线是将节点连接在一起的边。在这种情况下，节点的“权重”就是价格。如果您想以最便宜的价格从纽约飞往洛杉矶，您会选择更便宜的路线，即使它经过更多机场。

权重基本上将任意两个节点之间的最短路径的定义从最少的连接节点转移到这两个节点之间的最小权重。 Dijkstra 算法类似于您已实现的算法，但也利用了权重，重新定义了我们上面的最短路径。

我希望这可以帮到你!