Edge Algorithm
The Edge Weighted Depth First Order (EW-DFO) Algorithm is a graph traversal technique that is used to explore the vertices and edges in a weighted graph in depth-first order. The algorithm is an extension of the traditional Depth First Search (DFS) algorithm, with the significant difference being that in EW-DFO, the edges are assigned weights, and these weights influence the order in which the vertices are visited. The primary objective of the algorithm is to find an ordering of the vertices that allows for efficient processing of the graph, such as finding the shortest path, minimum spanning tree or any other optimization problem involving graph traversal.
The EW-DFO algorithm begins at a source vertex and explores as far as possible along each branch before backtracking. During the traversal, the algorithm takes into account the edge weights, and the order in which the vertices are visited is determined by the weights. Typically, vertices connected by lower weight edges are given priority in exploration. Once all the vertices have been visited, the algorithm terminates, and the order of the vertices visited is returned. This order can be used for various graph-related problems, as mentioned earlier. The algorithm can be implemented using either recursion or an explicit stack data structure to keep track of the vertices being visited. The time complexity of the EW-DFO algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the graph. This makes it an efficient approach for solving a variety of graph-based problems in scenarios where edge weights play a crucial role.
package org.gs.graph
/** Weighted Edge for graphs
*
* @constructor creates a new Edge with both vertices and weight
* @param v vertex at one end of edge
* @param w vertex at the other end of edge
* @param weight of Edge uses scala.math.Ordered for comparison
* @see [[https://algs4.cs.princeton.edu/43mst/Edge.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class Edge(v: Int, w: Int, weight: Double) extends BaseEdge(v, w, weight) with Ordered[Edge] {
/** returns edge's "from" vertex */
def either(): Int = v
/** returns the matchinf "from" or "to" vertex for vertex, error if no match */
def other(vertex: Int): Int = vertex match {
case `v` => w
case `w` => v
case _ => throw new IllegalArgumentException(s"Illegal endpoint vertex:${vertex}")
}
/** returns -1 if this < that, 0 if equal, +1 if > */
def compare(that: Edge): Int = weight.compareTo(that.weight)
/** returns true if other is an Edge */
def canEqual(other: Any): Boolean = other.isInstanceOf[Edge]
override def hashCode(): Int = 41 * (41 + v) + w + weight.hashCode
override def equals(that: Any): Boolean = that match {
case that: Edge => (that canEqual this) && this.hashCode == that.hashCode
}
}
