Learn Graph Introduction — Free DSA Tutorial

What is a Graph

A graph is a structure made of vertices (also called nodes) and edges connecting pairs of them, used to model relationships between objects — unlike a tree, a graph has no required hierarchy and can contain cycles, multiple paths, or disconnected pieces.

Example: What is a Graph

#include <iostream>
using namespace std;
int main() {
	int vertices = 5;
	int edges[][2] = {{0,1},{1,2},{2,0},{3,4}};
	cout << "Graph: " << vertices << " vertices, " << 4 << " edges, contains a cycle (0-1-2-0)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int vertices = 5;
		int[][] edges = {{0,1},{1,2},{2,0},{3,4}};
		System.out.println("Graph: " + vertices + " vertices, " + edges.length + " edges, contains a cycle (0-1-2-0)");
	}
}

vertices = 5
edges = [(0,1),(1,2),(2,0),(3,4)]
print(f"Graph: {vertices} vertices, {len(edges)} edges, contains a cycle (0-1-2-0)")

#include <stdio.h>
int main() {
	int vertices = 5;
	int edges[4][2] = {{0,1},{1,2},{2,0},{3,4}};
	printf("Graph: %d vertices, 4 edges, contains a cycle (0-1-2-0)", vertices);
	return 0;
}

Vertices and Edges

Vertices represent the individual entities being modeled — people, cities, web pages, tasks — while edges represent a relationship or connection between two of those entities, such as a friendship, a road, a link, or a dependency.

Example: Vertices and Edges

#include <iostream>
using namespace std;
int main() {
	string people[] = {"Alice", "Bob", "Carol"};
	cout << people[0] << " -- friendship --> " << people[1];
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] people = {"Alice", "Bob", "Carol"};
		System.out.println(people[0] + " -- friendship --> " + people[1]);
	}
}

people = ["Alice", "Bob", "Carol"]
print(f"{people[0]} -- friendship --> {people[1]}")

#include <stdio.h>
int main() {
	char* people[] = {"Alice", "Bob", "Carol"};
	printf("%s -- friendship --> %s", people[0], people[1]);
	return 0;
}

Directed Graph

A directed edge points from one specific vertex to another, meaning the relationship only goes one way (like a one-way street or a follows relationship on social media) — traveling from the destination back to the source isn't implied.

Example: Directed Graph

#include <iostream>
using namespace std;
int main() {
	cout << "Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice");
	}
}

print("Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice")

#include <stdio.h>
int main() {
	printf("Alice follows Bob (directed edge Alice->Bob) does not mean Bob follows Alice");
	return 0;
}

Undirected Graph

An undirected edge connects two vertices symmetrically, with the relationship holding equally in both directions (like a mutual friendship or a two-way road) — there's no distinction between source and destination.

Example: Undirected Graph

#include <iostream>
using namespace std;
int main() {
	cout << "Alice -- friend -- Bob: the edge holds equally in both directions";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Alice -- friend -- Bob: the edge holds equally in both directions");
	}
}

print("Alice -- friend -- Bob: the edge holds equally in both directions")

#include <stdio.h>
int main() {
	printf("Alice -- friend -- Bob: the edge holds equally in both directions");
	return 0;
}

Graph Uses

Graphs are used to model an enormous range of real systems: road networks, computer networks, social connections, task dependencies, and much more — recognizing when a problem is really 'objects and relationships between them' is usually the sign a graph is the right model.

Example: Graph Uses

#include <iostream>
using namespace std;
int main() {
	string uses[] = {"road networks", "computer networks", "social connections", "task dependencies"};
	for (string u : uses) cout << u << "; ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String[] uses = {"road networks", "computer networks", "social connections", "task dependencies"};
		for (String u : uses) System.out.print(u + "; ");
	}
}

uses = ["road networks", "computer networks", "social connections", "task dependencies"]
print("; ".join(uses))

#include <stdio.h>
int main() {
	char* uses[] = {"road networks", "computer networks", "social connections", "task dependencies"};
	for (int i = 0; i < 4; i++) printf("%s; ", uses[i]);
	return 0;
}

Graph Introduction

What is a Graph

Vertices and Edges

Directed Graph

Undirected Graph

Graph Uses

Chapter Quiz — Complete all 10 topics to unlock

Login to run this code