符号定向图使用来自文本文件的数据

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 算法与您已经实现的算法类似，但也利用了权重，重新定义了我们上面的最短路径。

我希望这可以帮到你！