Adjacency List Algorithm
The Adjacency List Algorithm is a graph representation technique that is particularly useful for representing sparse graphs, where the number of edges is significantly less than the maximum possible number of edges. It consists of maintaining a list (or array) of vertices, where each vertex has a list (or linked list) of its neighboring vertices or adjacent nodes. This approach is efficient in terms of storage space and allows for quick traversal of the graph, as it only stores the existing edges rather than all possible edges. The adjacency list representation is generally preferred over the adjacency matrix representation, particularly when dealing with large sparse graphs, as it consumes less memory and provides faster access to the required information.
In the Adjacency List Algorithm, the main operations include adding or removing vertices and edges, querying for the existence of an edge between two vertices, and retrieving the neighbors of a particular vertex. Adding vertices is a simple process of appending the vertex to the main list, while adding edges requires updating the corresponding adjacency lists of the involved vertices. Removing vertices and edges is slightly more complex, as it requires updating the adjacency lists of all affected vertices. Querying for the existence of an edge can be performed by searching the adjacency list of one of the vertices, and retrieving the neighbors of a vertex is a direct operation, as it involves returning the adjacency list of that vertex. Overall, the Adjacency List Algorithm is a versatile and efficient method for graph representation, offering a balance between memory usage and performance for various graph-related operations.
class AdjacencyList<T: Comparable<T>>: Graphable<T> {
var adjacencyMap: MutableMap<Vertex<T>, MutableList<Edge<T>>> = mutableMapOf()
private fun addDirectedEdge(source: Vertex<T>, destination: Vertex<T>, weight: Double?) {
val edge = Edge(source, destination, weight)
adjacencyMap[source]?.add(edge)
}
private fun addUndirectedEdge(vertices: Pair<Vertex<T>, Vertex<T>>, weight: Double?) {
val (source, destination) = vertices
addDirectedEdge(source, destination, weight)
addDirectedEdge(destination, source, weight)
}
override fun createVertex(data: T): Vertex<T> {
val vertex = Vertex(data)
adjacencyMap[vertex] ?: run {
adjacencyMap[vertex] = mutableListOf()
}
return vertex
}
override fun add(type: EdgeType, source: Vertex<T>, destination: Vertex<T>, weight: Double?) = when(type) {
is Directed -> {
addDirectedEdge(source, destination, weight)
}
is Undirected -> {
addUndirectedEdge(Pair(source, destination), weight)
}
}
override fun weight(source: Vertex<T>, destination: Vertex<T>): Double? {
val edges = adjacencyMap[source]
edges?.let {
it.forEach { edge ->
if (edge.destination == destination) return edge.weight
}
}
return null
}
override fun edges(source: Vertex<T>): MutableList<Edge<T>>? = adjacencyMap[source]
override fun toString(): String {
var result = ""
for ((vertex, edges) in adjacencyMap) {
var edgeString = ""
for ((index, edge) in edges.withIndex()) {
if (index != edges.count() - 1) {
edgeString += "${edge.destination}, "
} else {
edgeString += "${edge.destination}"
}
}
result += "$vertex ---> [ $edgeString ] \n"
}
return result
}
}
