返回邻接列表中的最高权重边

Question

我正在尝试解决一个练习题，编写一个函数，该函数 return 来自有向加权图的最高加权边，表示为邻接表。

由于我最近刚刚在我的课程中完成这个主题，所以我对上述问题有些困惑，所以我非常感谢任何帮助。首先，函数应该 return 一个 "edge"，但是我如何 return 一个由对象表示的边缘相互引用？换句话说，我找到了最高的权重，但我不知道要做什么 return，另外如果有两个顶点都以相同的距离指向彼此 - 相同的权重 - 怎么办？

这是带有示例图的代码，我 return将 D4 设置为要到达的最长目的地 110：

Class 列表节点

public class ListNode {

protected int destination;
protected float wt;
protected ListNode next;

public ListNode(int destination) {
    this.destination = destination;
}

public void addToSL(ListNode header, ListNode node) {
    if (header == null)
        return;
    else {
        ListNode trav = header;
        while (trav.next != null) {
            trav = trav.next;
        }

        trav.next = node;
        node.next = null;
    }
}
}

Class 邻接

public class Adjacency {

protected int lastAdded_index_w = -1;// for array of adjacency list
protected ListNode directList_W[];
public void createNewDirectGraphList_w(int numberOfvertices) // w means weighted graph
{
    this.directList_W = new ListNode[numberOfvertices]; //size is number of vertices
}

public void addVerticesToList_W(ListNode node)
{
    // adding all vertices to the adjacency list
    this.directList_W[lastAdded_index_w+1] = node;
    lastAdded_index_w++;
}

public void addAdjacencyVertices(ListNode v, ListNode adjV)
{
   // adding adjacency vertex adj to the linked list of vertex v
        v.addToSL(v, adjV);

}

public ListNode getHighestWeightedEdge(ListNode[] graph)
{
    ListNode highest = graph[0].next;
    for(int i=0; i < this.directList_W.length; i++)
    {
        ListNode trav = this.directList_W[i].next;
        while(trav!=null)
        {
            if(trav.wt >= highest.wt)
                highest = trav;
            trav = trav.next;
        }
    }

    return highest;

}

主要class public class 主要 {

public static void main(String[] args) {

Adjacency mat = new Adjacency(3);

 /*   
                 "Both direction"
            *D1-----"30km"-------------*D2
             |  \                       /
 "both"      |   \                     /
 "direction" |    \ "both direction"  /                
             |     \                 /
             |      \"90km"         /"110km" "one direction from D2 to D4"
       "20km"|       \             /
             |        \           /
             D3        \---*D4---/

        */

        // calling method to create graph adjacency list
        mat.createNewDirectGraphList_w(4); 

        // Creating vertices to connect "destination 1" with others.
        ListNode D1 = new ListNode(1);
        ListNode D2 = new ListNode(2);
        ListNode D3 = new ListNode(3);
        ListNode D4 = new ListNode(4);

        mat.addVerticesToList_W(D1);
        mat.addVerticesToList_W(D2);
        mat.addVerticesToList_W(D3);
        mat.addVerticesToList_W(D4);
  // parameter takes name of destinationm type int.
        ListNode D2_fromD1 = new ListNode(2); 
        D2_fromD1.wt = 30;
        ListNode D4_fromD1 = new ListNode(4);
        D4_fromD1.wt = 90;
        ListNode D3_fromD1 = new ListNode(3);
        D3_fromD1.wt = 20;

        // adding first destination and its adjacency vertices.
        mat.addAdjacencyVertices(D1, D2_fromD1); 
        mat.addAdjacencyVertices(D1, D3_fromD1);
        mat.addAdjacencyVertices(D1, D4_fromD1);

        // Creating vertices to connect "destination 2" with others.
        ListNode D4_FromD2 = new ListNode(4);
        D4_FromD2.wt= 110;
        ListNode D1_FromD2 = new ListNode(1);
        D1_FromD2.wt = 30;
        // adding second destination and its adjacency vertices.
        mat.addAdjacencyVertices(D2, D4_FromD2);
        mat.addAdjacencyVertices(D2, D1_FromD2);

        // Creating vertices to connect "destination 3" with others.
        ListNode D1_FromD3 = new ListNode(1);
        D1_FromD3.wt = 20;
        // adding second destination and its adjacency vertices.
        mat.addAdjacencyVertices(D3, D1_FromD3);

        // Creating vertices to connect "destination 3" with others.
        ListNode D1_FromD4 = new ListNode(1);
        D1_FromD4.wt = 90;
        // adding second destination and its adjacency vertices.
        mat.addAdjacencyVertices(D4, D1_FromD4);

       // saving the adjacency list array.
        ListNode weightedDirectedGraph [] = mat.directList_W; 

        // calling method to return highest weighted edge
        ListNode highestWeighted =    mat.getHighestWeightedEdge
                                       (weightedDirectedGraph);    

        System.out.println("Longest distenation in the 
        following destinations- D1, D2, D3, D4- \n"+
        "D"+highestWeighted.destination + "  " + highestWeighted.wt);
 }
    }

控制台输出：

Longest distenation in the following destinations- D1, D2, D3, D4- 

D4  110.0

Answer 1

有多种选择：

您可以将指向 header 的指针添加回 ListNode class，将其变成完整的边缘表示。
您可以更改表示以具有专用的顶点和边 classes。
您可以 return 一个节点对（例如，大小为 2 的 ListNode 数组）包含表示起始边的 ListNode 和表示权重和目的地的 ListNode 作为结果。

返回邻接列表中的最高权重边

Returning highest weighted edge in an Adjacency List

java

directed-acyclic-graphs

adjacency-matrix

data-structures