SIMPLE
Explore
• A graph is a non-linear data structure.
• Graph is a collection of nodes V connected by edges E.
– Nodes also called vertices, singular is vertex
– Edges also called arcs
– Each node contains an element
– Each edge connects two nodes together (or possibly the same node to itself) and may
contain an edge attribute
Mathematically :
G=(V,E) (G is an ordered pair of V and E)
V(G): set of vertices
E(G): a set of edges
Graph & it’s
Application
Explore
A graph is a non-linear data structure that consists of vertices (or nodes) connected by edges (or
arcs) where edges may be directed or undirected1. Graphs are used to represent relationships
between different entities and are a powerful tool for representing and analyzing complex
relationships between objects or entities1. Here are some applications of graphs in Data
Structures and Algorithms (DSA):
1. Network Monitoring: Graphs can be used to monitor network traffic in real-time,
allowing network administrators to identify potential bottlenecks, security threats, and
other issues2.
2. Transportation Systems: Google maps uses graphs for building transportation systems,
where intersections of two (or more) roads are considered to be a vertex and the road
connecting two vertices is considered to be an edge3.
3. Social Networks: In Facebook, users are considered to be the vertices and if they are
friends then there is an edge running between them. Facebook’s Friend suggestion
algorithm uses graph theory3.
4. Web Pages: In World Wide Web, web pages are considered to be the vertices. There is
an edge from a page u to other page v if there is a link of page v on page u3.
5. Operating Systems: In Operating System, we come across the Resource Allocation
Graph where each process and resources are considered to be vertices3.
6. Neural Networks: Graphs are used in Neural Networks where vertices represent neurons
and edges represent the synapses between them1.
7. Problem Solving: Graphs are used in problem-solving scenarios such as completing
Sudoku problems, finding the shortest path, and detecting cycles14.
These are just a few examples, and the applications of graphs in DSA are vast and varied.
Graph (n-1)
A graph is a non-linear data structure that consists of vertices (or nodes) and edges. The edges
are lines or arcs that connect any two nodes in the graph1.
If you’re referring to a graph with n-1 edges, it’s likely you’re talking about a tree. In a
connected graph, if the number of edges is one less than the number of vertices (i.e., n-1), the
graph is a tree. A tree is a special type of graph that doesn’t contain any cycles and is fully
connected1.
Terminology:
• Trees are special cases of graphs!!
• Tree
– If N nodes then N-1 edges.
– 1 edge for each parent-child
– All nodes must be reachable from root
• Graph
– No rules for connection among nodes.
– Edges can connect nodes in any possible way
Complete Graph:
• A complete graph is a graph that has the maximum number of edges
– for undirected graph with n vertices, the maximum number of edges is n(n-1)/2
• 4(4-1)/2 = 4(3)/2 = 12/2 = 6
– for directed graph with n vertices, the maximum number of edges is n(n-1)
• 4(4-1) = 4(3) = 12
Tree (traversing)
• A Tree is a non-linear data structure in which items are arranged in a sorted sequence.
• It is used to represent hierarchical (parent-child) relationship existing amongst several data
items.
1. Node: An entity that contains a key or value and pointers to its child nodes2.
2. Edge: The link between any two nodes2.
3. Root: The topmost node of a tree2.
4. Height of a Node: The number of edges from the node to the deepest leaf2.
5. Depth of a Node: The number of edges from the root to the node2.
6. Height of a Tree: The height of the root node or the depth of the deepest node2.
7. Degree of a Node: The total number of branches of that node2.
8. Forest: A collection of disjoint trees2.
Traversing of Binary Tree:
• A traversal of a tree T is a systematic way of accessing or visiting all the node of T.
• There are three standard ways of traversing a binary tree T with root R.
• These are :
1. Preorder (M L R) / (N L R)
2. Inorder (L M R) / (L N R)
3. Postorder (L R M) / (L R N)
LINKED LIST OPERATIONS
Inserting :
QUEUE with Operations:
Stack Operations:
Sorting Algorithm:
BUBBLE SORT: