What is a graph?

A graph is a data structure made up of vertices (nodes) and edges that connect those vertices.

Definition: A graph is a set of vertices V and a set of edges E, where each edge connects two vertices: G = (V, E)

---

#Types of graphs

• Undirected graph - edges have no direction (the connection is mutual). Example: friendship on a social network.
• Directed graph (digraph) - edges have a direction (arrows). Example: follows on Instagram.

---

#Types of connections

• Weighted graph - edges have a weight (cost, distance, time).
• Unweighted graph - all edges are equivalent.

---

#Ways to represent a graph

1. Adjacency matrix - a table where cell [i][j] shows whether (and with what weight) an edge exists between vertices i and j.
2. Adjacency list - each vertex stores a list of its neighboring vertices.

---

#Applications

• Social networks (connections between people)
• Navigation (paths between points)
• Recommendation systems
• Analysis of connections and routes

Summary: a graph is a universal model of any relationships between objects.