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.
sealed class EdgeType
class Directed() : EdgeType()
class Undirected(): EdgeType()
data class Edge<T:Comparable<T>>(var source: Vertex<T>, var destination: Vertex<T>, val weight: Double?)
