DUGraph Algorithm
The DUGraph (Directed Unweighted Graph) Algorithm is a class of algorithms designed to solve various problems in graph theory, specifically for directed unweighted graphs. Directed unweighted graphs consist of a collection of vertices and directed edges, where the edges have no weights associated with them. In other words, each edge in the graph has a direction (from one vertex to another) and all edges are considered to have equal importance. DUGraph algorithms are widely used in computer science and mathematics for solving problems such as finding the shortest path between nodes, detecting cycles, topological sorting, and determining the connectivity of a graph.
One of the most common DUGraph algorithms is the Breadth-First Search (BFS) algorithm, which is used to explore the vertices and edges of a graph systematically in a breadthward motion. The algorithm starts from a source vertex and visits all its adjacent vertices before moving on to explore the neighbors of these adjacent vertices. This process is continued until all reachable vertices have been visited. Another popular DUGraph algorithm is the Depth-First Search (DFS) algorithm, which explores the graph in a depthward motion, visiting a vertex and then recursively exploring each of its adjacent vertices before backtracking. Both BFS and DFS can be adapted to solve various graph-related problems, such as finding connected components, determining if a graph contains a cycle, and computing a topological ordering of the vertices.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.graphs.directed.unweighted
import com.algorithmexamples.datastructures.Queue
import com.algorithmexamples.graphs.Graph
class DUGraph(public override val V: Int): Graph {
override var E: Int = 0
private val adj: Array<Queue<Int>> = Array(V) { Queue<Int>() }
private val indegree: IntArray = IntArray(V)
public fun addEdge(from: Int, to: Int) {
adj[from].add(to)
indegree[to]++
E++
}
public override fun adjacentVertices(from: Int): Collection<Int> {
return adj[from]
}
public fun outdegree(from: Int): Int {
return adj[from].size
}
public fun indegree(v: Int): Int {
return indegree[v]
}
}
