Scribd
Upload
3 views3 pages

Data Structure Graphs Complete Notes

This document provides a beginner-friendly overview of graphs, a key data structure used in various applications like Google Maps and social media. It covers definitions, types of graphs, their representation, traversal methods (BFS and DFS), important algorithms, and real-life applications. Additionally, it includes time complexity for graph operations and offers tips for understanding graphs.

Uploaded by

badatyabibhu8
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Data Structure Graphs Complete Notes

This document provides a beginner-friendly overview of graphs, a key data structure used in various applications like Google Maps and social media. It covers definitions, types of graphs, their representation, traversal methods (BFS and DFS), important algorithms, and real-life applications. Additionally, it includes time complexity for graph operations and offers tips for understanding graphs.

Uploaded by

badatyabibhu8
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structure - Graphs (Beginner Friendly

Complete Notes)

A graph is one of the most important topics in Data Structures. Graphs are used in Google Maps, social media,
networking, AI, gaming, and many real-world applications. This PDF explains graphs from the beginning in simple
English.

1. What is a Graph?

A Graph is a non-linear data structure made of:

• Vertices (Nodes) → Points in the graph


• Edges → Connections between nodes

Example:
A --- B
||
C --- D

Here:
Vertices = A, B, C, D
Edges = AB, AC, BD, CD

2. Types of Graphs

Undirected Graph: Connection works both ways.


Example: A — B

Directed Graph (Digraph): Connection has direction.


Example: A → B

Weighted Graph: Edges have values or costs.


Example: Distance between cities.

Unweighted Graph: No weights on edges.

Cyclic Graph: Contains a cycle.

Acyclic Graph: No cycles.

3. Degree of a Vertex

Degree means the number of edges connected to a vertex.

Example:
If node A is connected to B, C, and D, then Degree(A) = 3
In Directed Graph:
• In-degree = incoming edges
• Out-degree = outgoing edges

4. Graph Representation

Graphs are mainly represented in two ways:

1. Adjacency Matrix
A 2D matrix is used.

Example:

A B C
A 0 1 1
B 1 0 0
C 1 0 0

2. Adjacency List
Each node stores a list of connected nodes.

Example:
A → B, C
B→A
C→A

5. Graph Traversal

Traversal means visiting all nodes of a graph.

There are two important traversal methods:

1. BFS (Breadth First Search)


• Uses Queue
• Visits level by level
• Useful for shortest path

Example Order:
A→B→C→D

2. DFS (Depth First Search)


• Uses Stack or Recursion
• Goes deep first

Example Order:
A→B→D→C

6. Important Graph Algorithms


• Dijkstra Algorithm → Shortest path

• Floyd Warshall → All pair shortest path

• Prim's Algorithm → Minimum Spanning Tree

• Kruskal's Algorithm → Minimum Spanning Tree

• Topological Sorting → Used in scheduling

7. Real Life Applications of Graphs

• Google Maps and Navigation

• Facebook and Instagram friend connections

• Computer Networks

• Airline Routes

• Recommendation Systems

• Gaming and AI

8. Time Complexity

Operation Complexity
BFS O(V + E)
DFS O(V + E)
Adjacency Matrix Space O(V²)
Adjacency List Space O(V + E)

9. Quick Summary

• Graph = Nodes + Edges


• BFS uses Queue
• DFS uses Stack/Recursion
• Graphs are used in networking, maps, and social media
• Adjacency Matrix and Adjacency List are common representations

Tip for Understanding Graphs:


First understand nodes and edges clearly. Then practice drawing small graphs on paper and perform BFS and DFS
manually. That is the easiest way to learn graphs.

You might also like