A graph is a collection of nodes (vertices) and edges that connect pairs of nodes.
• It is a non-linear data structure.
• It is used to create a pairwise relationship between objects.
» Vertex:
A vertex (also called a node or a point) is a basic unit in a graph. It represents an object in the system that is being modeled.
» Edge:
An edge (also called a link or a line) is a connection between two vertices in a graph. It represents a relationship between the two objects that the vertices represent.
Note: A Graph, when viewed as an Abstract Data Type (ADT), is a mathematical and abstract representation that defines the structure and operations associated with graphs. In the context of an ADT, a Graph typically consists of a set of vertices (nodes) and a set of edges connecting pairs of vertices.
» Formally, a graph is denoted as a pair G(V, E).
Where V represents the finite set vertices and E represents the finite set edges.
• Therefore, we can say a graph includes non-empty set of vertices V and set of edges E.
Example
‣ Suppose, a Graph G=(V,E),
where Vertices, V={a,b,c,d}
Edges, E={{a,b},{a,c},{b,c},{c,d}}
Applications of Graph:
Graphs have a wide range of applications across various domains due to their ability to model relationships and connections between entities.
Some key applications of graphs include:
- Social Networks
- Routing and Networking
- Transportation Systems
- Database Management
- Computer Networks
- Game Development
Directed Graph:
A directed graph, or digraph, is a graph in which the edges have a direction. This means that each edge points from one vertex to another vertex.
Undirected Graph:
An undirected graph, on the other hand, is a graph in which the edges do not have a direction. This means that each edge connects two vertices, but it does not matter which vertex the edge is pointing from.
Graph Terminologies:
Linear data structure:
A linear data structure is a type of data structure where elements are arranged sequentially, and each element has a unique predecessor and successor, except for the first and last elements.
Examples of Linear Data Structures: Arrays, Linked Lists, Stacks, Queues.
Non-linear data structure:
A non-linear data structure is a type of data structure where elements are not arranged in a sequential manner. There is no one-to-one relationship between elements.
Examples of Non-Linear Data Structures: Trees, Graphs.
Cyclic Graph:
A cyclic graph, also known as a cyclic or non-acyclic graph, is a graph that contains at least one cycle. In graph theory, a cycle is a path of edges and vertices that starts and ends at the same vertex, forming a closed loop.
Acyclic Graph:
An acyclic graph, also known as a non-cyclic or acyclic graph, is a graph that does not contain any cycles. In an acyclic graph, it is not possible to traverse a path of edges and vertices and return to the starting point without retracing any edge.
Directed Acyclic Graph:
A directed acyclic graph (DAG) is a specific type of acyclic graph where edges have a direction, and there are no cycles. In a DAG, it is impossible to follow the direction of the edges and revisit a vertex, forming a closed loop.
