Definition of Graph Data Structure
A graph can be defined as a pictorial representation of a set of objects that may be connected to each other by links.
The intersection point of these objects is known as Vertex, and the link between two vertices is called an Edge.
Definition: A graph G consists of a set V of Vertices and a set E of Edges. The graph G = (V, E) where V is a finite and non-empty set of vertices and E is a set of pairs of vertices called edges.
Therefore,
- V (G) is the set of vertices, read as V of G
- E (G) is the set of edges, read as E of G.
Graph Data Structure Example
In this pictorial representation of a graph, the nodes are named A, B, C.
In the above graph, V denotes the vertices and E denotes the edges.
V = { A, B, C, D, E }
E = { AB, AC, AE, DE, BD }
Note. In an undirected graph, pair of vertices representing any edge is unordered. Thus, (v, w) and (w, v) represent the same edge.
Note. In a Directed graph, the order of pair of vertices is necessary, the direction is indicated by an arrow. Thus, (v, w) is not the same as (w, v).
Graph Terminologies
Vertex
The intersection point of two objects in a graph is called the vertex. Each node in a graph is represented as a vertex.
Edge
An edge represents a path between two vertices or a line between two vertices.
Adjacent Vertices
Vertex v1 is said to be adjacent to a vertex v2 if there is an edge (v1, v2) or (v2, v1).
Path
A path from vertex w is a sequence of vertices, which are adjacent to the next. In the example, 1, 2, and 3 is a path, and 1, 4, and 6 is also a path.
Cycle
A cycle is also a path in which the first and last vertices of a graph are the same. For example, if we start to travel from vertex A, after following a certain path we must reach the A vertex.
1, 2, 3, 4, 1 is a cycle in the graph above.
Connected Graph
A graph G is called connected if there exists a path from any vertex to any other vertex.
Degree
The number of edges incident on a vertex is its degree. The degree of vertex u is written as degree (u). If a degree (u) = 0, that means the vertex u does not belong to any edge and is called Isolated Vertex.
Complete Graph
A graph is said to be complete or fully connected if there is a path from every vertex to every other vertex. A complete graph G with n vertices will have n (n-1)/2 edges.
Weighted Graph
If every edge in the graph is assigned some weight or value then it is called a weighted graph.
The weight of the edge is a positive value that may be representing the distance or cost of moving along the edge.
Tree
A graph can be a tree if it has two properties:
- If it is connected.
- If there are no cycles.
Graph Representation
As we know, the graph is a mathematical structure that has various applications both in mathematics as well as in computer applications.
In computer science, graphs can be represented by three main data types of data structures such as Adjacent Matrix, Adjacency List, and Multi List representation.
- Adjacent Matrix
- Adjacency List
- Multi List
1 Adjacency Matrix
The adjacency matrix for a graph with n vertices is an n x n matrix of bits, such that
Aij = 1, if there is an edge from Vi to Vj
Aij = 0, if there is no edge.
2 Adjacency List
In the adjacency lists, we store a graph as a linked list structure. Here we store all the vertices in a list and then for each vertex, we have a linked list of its adjacent vertices.
3 Multi List
In multi-list representation of graphs, there are two parts, a director of nodes information and a set of a linked list of edge information.
For each node of the graph, there is one entry in the node directory.
Graph Traversal
The visiting of all the nodes in a graph is known as graph traversal. To access the data of the graph, and insert the new data into the graph we have two important graph traversal algorithms such as:
- Breadth First Traversal ( BFS ).
- Depth First Traversal ( DFS ).
Breadth First Traversal (BFS)
In BFS traversal, one node is selected as the start position it is visited and marked, then all unvisited nodes adjacent to the next node are visited and marked in some sequential order.
And the unvisited nodes immediately adjacent to these nodes are visited and marked and so on until the entire graph has been traversed.
See full article here, Breadth First Traversal (BFS)
Depth First Traversal (DFS).
Depth-first traversal algorithm proceeds level by level, DFS follows first a path from the starting node to an ending node, then another path from the start to the end, until all the nodes are visited.
See full article here, Depth First Traversal (DFS)
Application of Graphs
A graph is a mathematical structure that is used in various aspects of daily life:
- Google Map is one of the application of graphs.
- Graphs have applications in Geography
- Graphs are used in Chemistry
- Graphs are fundamental of Engineering
- Also used in Computer Science
- Graphs are used in Graphics
- Used in Solving Games
- Puzzles can be solved using graphs.
Graph History
Historically, graph theory was originated in the Konigsberg bridge problem. The Prussian city of Konigsberg was built along the Preger River and occupied both banks and two islands.
The problem was to seek a route that would enable one to cross all seven bridges in the city exactly once and return to their starting point.
Leonhard Euler, a mathematician, developed some concepts in solving this problem and these concepts formed the basis of the graph theory.