Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Types of Graph
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Types of Graphs

Graphs can vary based on how their edges behave, whether they carry weights, and how their nodes are connected. Understanding graph types is key to choosing the right algorithm for your problem.

1. Undirected Graph

  • Edges have no direction.
  • If there’s an edge between A and B, you can go from A to B and also from B to A.
  • These graphs represent two-way relationships.

Example: A friendship network – if Alice is friends with Bob, Bob is also friends with Alice.

Image

2. Directed Graph

  • Edges point in one direction.
  • An edge from A to B only allows movement from A to B, not the other way.
  • Also called a digraph.

Example: Web links – one page may link to another, but not necessarily the reverse.

Image

3. Weighted Graph

  • Each edge has a value (weight) that represents distance, cost, time, etc.
  • Used when connections have varying importance or size.

Example: A road map where each road has a distance or travel time.

Image

4. Unweighted Graph

  • All edges are treated equally.
  • Edges don’t carry additional values—every connection is the same.

Example: A family tree or organizational chart where relationships just "exist" or "don’t".

Image

5. Cyclic Graph

  • Contains at least one cycle—a path that starts and ends at the same node.
  • The cycle must have at least three distinct nodes (to avoid looping back on a single edge).

Example: A social network loop where you can return to your starting friend by following friend connections.

Image

6. Acyclic Graph

  • Contains no cycles—you can’t return to the same node once you've left it.

There are two important cases:

  • Undirected Acyclic Graph

    • If it’s also connected, it is called a Tree.
    • A group of trees is called a Forest.

  • Directed Acyclic Graph (DAG)

    • A graph with directed edges and no cycles.
    • Can be topologically sorted, meaning nodes can be arranged linearly to respect the direction of edges.

Example of DAG: Task scheduling – task A must happen before task B.

Acyclic Graph
Acyclic Graph

7. Connected Graph

  • Every vertex is reachable from every other vertex.
  • Applies to undirected graphs.

Example: A network where all devices are linked directly or indirectly.

Connected Graph
Connected Graph

8. Disconnected Graph

  • At least one node cannot be reached from another.
  • The graph is made up of separate connected components.

Example: Two social groups with no connections between them.

Disconnected Graph
Disconnected Graph

9. Strongly Connected Graph

  • Applies to directed graphs.
  • A graph is strongly connected if there is a path from every node to every other node and back.

Example: In a city road system, if every one-way street still allows you to reach all other streets and return.

Strongly Connected Graphs
Strongly Connected Graphs
Graph TypeDirectionWeightsCycles AllowedExample
Undirected?OptionalYes/NoFriendship network
Directed?OptionalYes/NoWeb links
Weighted? / ??Yes/NoRoad map
Unweighted? / ??Yes/NoFamily tree
Cyclic? / ?Optional?Group of people forming a circle
Acyclic (Tree/DAG)? / ?Optional?Task scheduling, directory tree
Connected?OptionalYes/NoFully linked network
Disconnected? / ?OptionalYes/NoMultiple separate subgraphs
Strongly Connected?OptionalYes/NoFully reachable city map (one-way)

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible