Graphs
Graphs
• It is a collection of vertices and edges
• Represented as: G = (V,E)
• Directed Edge:
• Ordered pair of vertices (u,v)
• First vertex u is the origin
• Second vertex v is the destination
• Example: One way traffic road
• Undirected Edge:
• Unordered pair of vertices (u,v)
• Example: Railway lines
• Directed Graphs (Digraphs)
Indegree = The no of edges coming towards the vertex
Outdegree = The no. of edges going out from the vertex
Example: Route network
• Undirected Graphs
Degree of vertex = The no of edges connected to a vertex
Example: Flight network
• When an edge connects two vertices, they are called adjacent to each
other and edge is incident on both of them
• A graph with no cycles is called a tree.
A tree is Acyclic Connected Graph
• Self loop is an edge that connects vertex to itself
• Two edges are parallel if they connect same pair of vertices
• A path is a sequence of adjacent vertices.
Simple path has no repeated vertex in it
• A cyclic path has same first and last vertex
Connected and Non-connected graphs
• Non Connected Graphs:
These are divided into 2 or more components
Component 1 Component 2
Connected and Non-connected graphs
• Articulation Point:
Point from where removing an edge makes graph non-connected is
called articulation point
Connected Graphs
• In undirected graph both D and F are articulation points
• In digraph only source vertex is considered articulation point
• Directed Acyclic Graph (DAG)
It is a directed graph with no cycles
• Strongly Connected Graphs
Every node can be reached from every node
• Topological Ordering
• Bipartite Graphs
Graph whose vertices can be divided into 2 sets such that all edges
connect a vertex in one set with a vertex in another set
• Weighted Graphs
Weights are assigned to each edge
• Complete Graphs
A graph with all possible edges is called a complete graph
Applications of Graphs
• Representing relationship between components in electronic circuit
• Transportation network, highway network, flight network
• Computer network: LAN, Internet, Web
• Databases: For representing ER (Entity Relationship) diagrams,
dependency tables
Graph Representation
• Adjacency Matrix
• Adjacency List
• Adjacency Set
Adjacency Matrix
• We use a V*V matrix with Boolean values (0,1)
• The value Adj[u,v] is set to 1 if there is an edge from vertex u vertex v
• For undirected graph
We need to set both Adj[u,v] and Adj[v,u] as 1
• For directed graph
We need to set only Adj[u,v] as 1 if there exist a directed edge
between the two vertices
Adjacency Matrix of Digraph
A B C D
A 0 1 1 0
B 0 0 0 0
C 0 0 0 0
D 1 1 1 0
Adjacency Matrix of Undirected Graph
A B C D
A 0 1 1 1
B 1 0 1 1
C 1 1 0 1
D 1 1 1 0
Adjacency List
• All vertices connected to a vertex v are listed on an adjacency list for
that vertex v
Adjacency Set
• It is similar to adjacency list
• Disjoint sets [Union-Find] are used instead of Linked-Lists
Graph Traversal
• Depth First Search (DFS)
• Breadth First Search (BFS)
DFS
• Works similar to pre-order traversal of tree
• This algorithm also uses stack (for backtracking)
DFS Algorithm
1. Mark all the nodes as unvisited
2. Push the starting node onto the stack
3. Repeat steps 4 and 5 until stack is empty
4. Pop the top of the stack and mark it visited
5. Push all the adjacent nodes of popped node if their status is
unvisited
6. Exit
DFS
DFS
DFS
BFS
• Works similar to Level-order traversal in tree
• This algorithm uses queue
• This algorithm maintains flag for the visited vertex
BFS Algorithm
1. Mark all the nodes unvisited
2. Put the starting node in the queue
3. Repeat step 4 and 5 until all nodes are visited
4. Remove the node from the queue and mark its status as visited
5. Insert all the adjacent nodes of the deleted node if their status is
unvisited
6. Exit
BFS
BFS
Note
• You could also follow the algorithm mentioned in Schaum’s
• [Link]
• [Link]
• The above links have similar algorithm to Schaum’s if anybody doesn’t
have book