Undirected and Directed Graphs

DSA, Database System & Operating System — Sorting, Searching, and Graphs, NEC licence examination syllabus (Nepal Engineering Council).

Undirected and Directed Graphs

The single most versatile data structure in computer science — maps, social networks, and dependency chains all boil down to graphs.

A graph is a set of vertices (nodes) connected by edges. In an undirected graph, an edge between A and B works both ways equally (like a Facebook friendship). In a directed graph, edges have a specific direction (like a Twitter "follow," which doesn't have to be mutual).

💡 One-liner: give one real-world example each for undirected (Facebook friendship) and directed (Twitter follow, or a task dependency chain) graphs.

The vocabulary questions actually test

📐 Terms worth being exact about

DegreeHow many edges touch a vertex. A directed graph splits this into in-degree and out-degree, and the distinction is what topological sorting runs on.

Path / cycleA route along edges; a cycle returns to where it started. "Acyclic" means no cycles exist — the A in DAG.

ConnectedEvery vertex reachable from every other. In a directed graph, strongly connected means reachable following edge directions, which is a stricter condition.

WeightedEdges carry costs. Shortest-path questions need weights; traversal questions do not.

The DAG — directed, acyclic — deserves singling out, because a startling number of real problems are exactly this shape: task scheduling, build dependencies, course prerequisites, spreadsheet recalculation. A cycle in any of them means a contradiction (A must precede B, which must precede A), which is why detecting one is usually the point of the algorithm rather than an edge case.

How the direction changes the count

An undirected edge between A and B is one edge, but appears in both A's and B's adjacency lists — so the sum of all degrees is twice the number of edges. In a directed graph each edge is stored once, contributing to one vertex's out-degree and another's in-degree.

💡 That factor of two is a routine exam trap: "an undirected graph has 10 vertices each of degree 4 — how many edges?" The answer is (10 × 4) / 2 = 20, not 40. Every edge is counted twice, once from each end.

Syllabus points

Graph terminology; directed vs undirected

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.