What's the difference between a weighted and an unweighted graph?

A weighted graph assigns a value or weight to each edge, while an unweighted graph does not.

In more detail, a graph in computer science is a data structure that is defined by two components: a set of vertices (or nodes) and a set of edges. Each edge connects a pair of vertices. In an unweighted graph, all edges are equal and there's no specific cost associated with moving from one vertex to another. This means that if you're trying to find a path from one point to another, any path with the shortest number of edges is a valid solution.

On the other hand, a weighted graph assigns a numerical value, or 'weight', to each edge. This weight can represent a variety of different things depending on the problem at hand. For example, in a graph representing a road network, the weights could represent the distance or travel time between different locations. In this case, the shortest path between two points would be the one with the smallest total weight, not necessarily the one with the fewest edges.

Weighted graphs are often used in algorithms that solve real-world problems, such as finding the shortest path in a navigation system, or the least expensive set of purchases in a shopping problem. Unweighted graphs, while simpler, can still be useful in situations where the only important factor is the presence or absence of a connection between nodes, such as in social network analysis or in studying the structure of the internet.

In terms of implementation, both types of graphs can be represented using similar data structures, such as adjacency matrices or adjacency lists. However, for a weighted graph, these structures will also need to store the additional weight information for each edge. This can make weighted graphs slightly more complex to work with, but also more powerful and flexible for solving a wider range of problems.