What Is a Graph?

Graph is probably the data structure that has the closest resemblance to our daily life. There are many types of graphs describing the relationships in real life. For instance, our friend circle is a huge “graph”.


A graph is a collection of nodes and edges that represents relationships:
  • Nodes are vertices that correspond to objects.
  • Edges are the connections between objects.
The graph edges sometimes have Weights, which indicate the strength (or some other attribute) of each connection between the nodes.

These definitions are general, as the exact meaning of the nodes and edges in a graph depends on the specific application. For instance, you can model the friendships in a social network using a graph. The graph nodes are people, and the edges represent friendships. The natural correspondence of graphs to physical objects and situations means that you can use graphs to model a wide variety of systems. For example:

Web page linking — The graph nodes are web pages, and the edges represent hyperlinks between pages.
Airports — The graph nodes are airports, and the edges represent flights between airports


Types of “graphs”:

There are many types of “graphs”. In this Explore Card, we will introduce three types of graphs: undirected graphs, directed graphs, and weighted graphs.

Undirected graphs:
 
The edges between any two vertices in an “undirected graph” do not have a direction, indicating a two-way relationship.
An undirected graph is a set of nodes and a set of links between the nodes. Each node is called a vertex, each link is called an edge, and each edge connects two vertices. The order of the two connected vertices is unimportant. An undirected graph is a finite set of vertices together with a finite set of edges.


Directed graphs:

The edges between any two vertices in a “directed graph” graph are directional.
svg viewer

In the example on the right, the graph can be traversed from vertex A to B, but not from vertex B to A.






Weighted graphs:

Each edge in a “weighted graph” has an associated weight. The weight can be of any metric, such as time, distance, size, etc. The most commonly seen “weighted map” in our daily life might be a city map.
A weighted graph is a graph in which each branch is given a numerical weight. A weighted graph is therefore a special type of labeled graph in which the labels are numbers (which are usually taken to be positive).
 

Dijkstra's Algorithm:

Let's assume that the nodes of the undirected graph in our first figure represent cities, and the edges represent the roads that connect those cities. Because the graph is undirected, we can assume that the roads are bi-directional or two-way. We can use Dijkstra's algorithm to find the shortest path from city A to all the other cities. 



*******Thanks For Visiting*********