4.1.5 Introduction to Graphs
A Graph is a data structure that consists of a set of vertices (or nodes) connected by edges. Graphs are used to represent networks of connections, where each connection is a relationship between two vertices. These vertices can represent anything, like cities, people, or even abstract concepts, and the edges represent the relationships or pathways between them.
Imagine you are mapping out all the cities in Pakistan and the roads that connect them. Each city is a vertex, and each road between two cities is an edge. Unlike a tree, a graph does not have a single "root" and does not follow a hierarchical structure. In a graph, any two vertices can be connected, creating a complex web of relationships.
Example: In a social network, each person can be connected to many others, forming a graph. There is no single starting point, and people (vertices) can have multiple connections (edges) that do not follow a strict parent-child relationship like in a tree.
Difference from a Tree: While both graphs and trees are used to represent relationships between objects, a tree is a special kind of graph with some important differences:
- A Tree is hierarchical, meaning it has a single root node from which all other nodes branch out. In contrast, a Graph does not necessarily have a hierarchy or a root.
- In a Tree, there is exactly one path between any two nodes, ensuring no cycles (loops). However, in a Graph, there can be multiple paths between nodes, and cycles are allowed.
- Trees are often used to represent structured data like family trees or organizational charts. Graphs are more flexible and can represent a broader range of connections, such as networks, web links, or transport systems.