In mathematics, a graph isn't a chart with x and y axes. Instead, it's a way to model relationships between objects. Think of it like a map of connections. A graph consists of two simple things: nodes and edges.

Imagine a small group of friends. We can represent this as a graph where each person is a node, and a friendship is an edge connecting them.

Not all connections work the same way. Sometimes a relationship is mutual, and sometimes it's one-directional. This distinction gives us two basic types of graphs.

An undirected graph has edges that go both ways. If Alice is friends with Bob, Bob is also friends with Alice. The friendship is a two-way street. The graph of friends above is a perfect example of this.

A directed graph, on the other hand, has edges with a specific direction, often shown as arrows. Think of social media. If Charlie follows Dana on a platform, it doesn't necessarily mean Dana follows Charlie back. The relationship is one-way.

We can add another layer of detail: weights. An unweighted graph just shows that a connection exists. A weighted graph assigns a value, or "weight," to each edge. This weight can represent anything from distance and time to cost or strength of a connection.

For example, a map of cities can be a weighted graph where the weight of each edge is the distance of the road connecting two cities.

We have specific terms to describe the relationships between nodes. If two nodes are connected by an edge, they are adjacent. In the city map above, City B is adjacent to City A, City C, and City D.

We can also measure how connected a node is by its degree. The degree of a node is simply the number of edges connected to it. In the same city map, City B has a degree of 3.

For directed graphs, it's a bit more detailed. We count two types of degrees:

• In-degree: The number of edges pointing to a node.
• Out-degree: The number of edges pointing away from a node.

In our directed social media graph, Dana has an in-degree of 2 (from Alice and Charlie) and an out-degree of 0.

To work with graphs in a program, we need a structured way to store them. The two most common methods are the adjacency matrix and the adjacency list.

An adjacency matrix is a grid of numbers. Each row and column corresponds to a node. A 1 (or the edge's weight) in the cell where a row and column intersect means there's an edge between those two nodes. A 0 means there isn't.

An adjacency list is a collection of lists. For each node, we list all the other nodes it's connected to. For a weighted graph, we'd also store the weight alongside each neighbor.

Here is the adjacency list for the same city map:

Each representation has its own strengths. Adjacency matrices are quick for checking if an edge exists between two specific nodes, while adjacency lists are more space-efficient for graphs with few edges.

Now that you know the fundamentals, let's test your understanding.