What is a Graph Data Structure?

In today's world, we are connected to other people, places, or things in some way or the other. If we step back and start sketching diagrams, we can see graphs everywhere and they represents relationships. A Graph consists of nodes (also called vertices) and edges. Let's look at a couple of examples.

Phone Network Graph
phone-graph
phone-graph-vertices
phone-graph-edges

In Figure 1.a, a network of phone numbers represent a graph. Each phone number in the graph (Figure 1.b) represents a vertex. Since this phone network graph has more than one phone number, they are collectively known as vertices. The relationship between the vertices is represented by the edge in a graph(Figure 1.c). A graph can contain more than 1 edge . The presence of an edge between phone numbers 323-006 and 123-001 represents a call between these two numbers.

Social Graph
social-graph
social-graph-vertices
social-graph-edges

In Figure 2.a, a group of friends connected on Facebook represent a graph. Kim, Amy, Anna and Dave are represented by a vertex in a graph(Figure 2.b). An edge connecting Kim and Anna represents a friendship between them(Figure 2.c) . Absence of an edge between Kim and Dave shows that they are not connected to each other as friends.

Flight Route Graph
flight-graph
flight-graph-vertices
flight-graph-edges

In Figure 3.a, the flight route between various cities can be represented using graph. Delhi, New York City and San Francisco are represented by a vertex in a graph(Figure3.b). An edge between two vertices such as Delhi and San Francisco shows that there exists a flight route between these two cities represented as vertices(Figure 3c).