Directed vs Undirected, Weighted vs Unweighted

Graphs adapt to diverse problem domains through two foundational attributes: edge direction and edge weight.

Directed Graphs (Digraphs)

In a Directed Graph, edges have an orientation represented by arrows. An edge from vertex u to vertex v (u → v) allows traversal only from u to v.

Copy code( A ) --------> ( B )
  ^               |
  |               v
( D ) <-------- ( C )

Key Concept: Directed Acyclic Graph (DAG)

A DAG is a directed graph with no directed cycles. You cannot start at vertex v and follow arrows back to v.

DAGs are the universal structure for Dependency Resolution:

• Gradle & Android Build Systems: Build tasks (compileKotlin, processResources, packageApk) form a DAG.
• Dependency Injection (Dagger / Hilt): Component creation graph.
• Git Commit History: Commits point back to parent commits in a DAG.

Weighted Graphs

In a Weighted Graph, every edge is assigned a numerical cost, distance, latency, or capacity:

Copy code        12 km
(City A) ---- (City B)
   |             |
   | 4 km        | 7 km
   v             v
(City C) ---- (City D)
        9 km

Representation in Code:

Copy codedata class Edge(val destination: Int, val weight: Double)

class WeightedGraph(val numVertices: Int) {
    val adjList: Array<MutableList<Edge>> = Array(numVertices) { mutableListOf() }

    fun addEdge(u: Int, v: Int, weight: Double) {
        adjList[u].add(Edge(v, weight))
    }
}

Classic Graph Problems by Type

Summary

• Directed graphs enforce one-way relationships; DAGs model task dependencies and build pipelines.
• Weighted graphs associate numbers with edges to represent costs, distances, or capacities.