A Directed Graph (or Digraph) is a graph where edges have a direction, going from one vertex (source) to another (destination). The edge (u, v) means there's a connection from u to v, but not necessarily from v to u. This models one-way relationships like web links, dependencies, or following relationships on social media.
Key concepts include in-degree (edges coming in) and out-degree (edges going out), DAGs (Directed Acyclic Graphs) used for dependency resolution, and topological sorting for ordering tasks with dependencies.
Add Vertex: Enter a label and click "Add Vertex".
Add Directed Edge: Select source → destination. The arrow shows direction.
Select Vertex: Click on a vertex to select it (yellow highlight).
DFS/BFS: Follows outgoing edges only (respects direction).
In-Degree: Green badge shows edges coming INTO the vertex.
Out-Degree: Red badge shows edges going OUT of the vertex.
Topological Sort: Linear ordering where for every edge (u,v), u comes before v. Only works on DAGs.
Cycle Detection: Uses DFS coloring (white/gray/black) to detect back edges indicating cycles.
Strongly Connected Components: Kosaraju's or Tarjan's algorithm finds maximal strongly connected subgraphs.
Shortest Path: Dijkstra's algorithm works on directed graphs with non-negative weights.
Reachability: BFS/DFS from source finds all vertices reachable via directed paths.
Web Page Links: Pages as vertices, hyperlinks as directed edges (PageRank algorithm).
Task Dependencies: Build systems, package managers use DAGs for dependency resolution.
Social Media: Twitter/Instagram follows are directed (A follows B ≠ B follows A).
State Machines: States as vertices, transitions as directed edges.
Course Prerequisites: Topological sort determines valid course ordering.
Git Commits: Commit history forms a DAG with parent-child relationships.
Add Vertex: Insert a new node into the graph.
Add Edge: Create directed connection from source to destination vertex.
Remove Vertex: Delete vertex and all edges connected to it.
Remove Edge: Delete the directed edge between two vertices.
Get In-Degree: Count edges pointing into a vertex.
Get Out-Degree: Count edges pointing out from a vertex.
Topological Sort: Use DFS with post-order or Kahn's algorithm with in-degree tracking for DAGs.
Cycle Detection: Three-color DFS (white/gray/black); gray to gray edge indicates cycle.
Strongly Connected Components: Kosaraju's (two DFS) or Tarjan's (single DFS with low-link).
Shortest Path (Weighted): Dijkstra for non-negative, Bellman-Ford for negative weights.
Course Schedule: Model as directed graph; check for cycle or find topological order.
All Paths: DFS with backtracking to enumerate all paths between two vertices.
Transitive Closure: Floyd-Warshall or DFS from each vertex to find all reachable pairs.
/* Directed Graph implementation in C */
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct Node {
int vertex;
struct Node* next;
} Node;
typedef struct Graph {
int numVertices;
Node** adjLists;
int* visited;
} Graph;
Node* createNode(int v) {
Node* node = malloc(sizeof(Node));
node->vertex = v;
node->next = NULL;
return node;
}
Graph* createGraph(int vertices) {
Graph* graph = malloc(sizeof(Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(Node*));
graph->visited = malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Directed: only adds edge from src to dest
void addEdge(Graph* graph, int src, int dest) {
Node* node = createNode(dest);
node->next = graph->adjLists[src];
graph->adjLists[src] = node;
}
// Topological Sort using DFS
void topologicalSortUtil(Graph* graph, int v, int* stack, int* stackIndex) {
graph->visited[v] = 1;
Node* adj = graph->adjLists[v];
while (adj) {
if (!graph->visited[adj->vertex])
topologicalSortUtil(graph, adj->vertex, stack, stackIndex);
adj = adj->next;
}
stack[(*stackIndex)++] = v;
}
void topologicalSort(Graph* graph) {
int* stack = malloc(graph->numVertices * sizeof(int));
int stackIndex = 0;
for (int i = 0; i < graph->numVertices; i++)
if (!graph->visited[i])
topologicalSortUtil(graph, i, stack, &stackIndex);
printf("Topological Order: ");
while (stackIndex > 0)
printf("%d ", stack[--stackIndex]);
}
int main() {
Graph* graph = createGraph(6);
addEdge(graph, 5, 2); addEdge(graph, 5, 0);
addEdge(graph, 4, 0); addEdge(graph, 4, 1);
addEdge(graph, 2, 3); addEdge(graph, 3, 1);
topologicalSort(graph);
return 0;
}