What is a Graph (Data Structure)?

A graph is a data structure made of nodes (also called vertices) connected by edges. It's ideal for modeling relationships — social networks, road maps, web links, and task dependencies all map naturally onto graphs.

Key Concepts:

• Vertex (node): An entity (a person, city, page)
• Edge: A connection between two vertices
• Directed vs. undirected: Edges may have a direction (one-way) or not
• Weighted: Edges can carry a value (distance, cost)

How It's Represented:

• Adjacency list: Each node stores its neighbors (space-efficient)
• Adjacency matrix: A grid marking which nodes connect (fast lookups)

Common Algorithms:

• BFS: Breadth-first search, explores level by level
• DFS: Depth-first search, explores as deep as possible
• Dijkstra's: Shortest path with weighted edges
• Topological sort: Order tasks respecting dependencies

FAQ

What's the difference between a graph and a tree?

A tree is a special kind of graph with no cycles and a single path between any two nodes. Graphs are more general and can have cycles and many connections.

When should I use a graph?

Whenever your problem is about relationships or connections — recommendations, routing, dependency resolution, network analysis — a graph is often the natural model.