TCS1044\TCS1093 NOTES
CHAPTER 8 : GRAPH
Introduction
Graphs are very useful structures. They can be used to solve complex routing problems, such
as designing and routing airlines among the airports they serve. Similarly, they can be used to
route messages over a computer network from one node to another.
Basic Concepts
A graph is a collection of nodes, called vertices and a collection of segments, called lines,
connecting pairs of vertices. In other words, a graph consists of two sets, a set of vertices and
a set of lines.
Graphs may be either directed or undirected. A directed graph or digraph is a graph in
which each line has a direction (arrow head) to its successor. The lines in a directed graph
are known as arcs. In a directed graph, the flow along the arcs between two vertices can
follow only the indicated direction.
An undirected graph is a graph in which there is no directions (arrow head) on any of the
lines, which are know as edges. In an undirected graph, the flow between two vertices can go
in either direction
Figure 1
A path is a sequence of vertices in which each vertex is adjacent to the next node. In Figure
1, {A, B, C, E} is one path and {A, B, E, F} is another. Both directed and undirected graphs
have paths. In an undirected graph you may travel in either direction.
Two vertices in a graph are said to be adjacent vertices (or neighbors) if there is a path of
length 1 connecting them. In Figure 1 (a), B is adjacent to A whereas E is not adjacent to D;
on the hand, D is adjacent to E. In Figure 1 (b), E and D are adjacent but D and F are not.
A cycle is a path consisting of at least three vertices that starts and ends with the same
vertex. In Figure 1 (b), B, C, D, E, B is a cycle.
A loop is a special case of a cycle in which a single are begins and ends with the same
vertex. In a loop the end points of the line are the same.
Figure 2
1
TCS1044\TCS1093 NOTES
Two vertices are said to be connected if there is a path between them. A graph is said to be
connected if, there is a path from any vertex to any other vertex. A directed graph is strongly
connected if there is a path from each vertex to every other vertex in the digraph. A directed
graph is weakly connected if at least two vertices are not connected. A graph is a disjoint
graph if it is not connected.
Figure 3
The degree of vertex is the number of lines incident to it. The outdegree of a vertex in a
digraph is the number of arcs leaving the vertex; indegree is the number of arcs entering the
vertex.
Operations
1. Insert Vertex
Insert vertex operation adds a new vertex to a graph. After a vertex is inserted, it must be
connected.
Figure 4: Insert Vertex
2. Delete Vertex
Delete vertex operation removes a vertex from the graph. When a vertex is deleted, all
connecting edges are also removed.
Figure 5: Delete Vertex
2
TCS1044\TCS1093 NOTES
3. Add Edge
Add edge operation connects a vertex to a destination vertex. If a vertex requires multiple
edges, add an edge must be called once for each adjacent vertex. To add an edge, two
vertices must be specified. If the graph is a digraph, one of the vertices must be specified
as the source and one as the destination.
Figure 6: Add Edge
4. Delete Edge
Delete edge operation removes one edge from a graph.
Figure 7: Delete Edge
5. Find Vertex
Find vertex operation traverses a graph, looking for a specified vertex. If the vertex is
found, its data returned, if it is not found, an error is indicated.
Figure 8: Find Vertex
6. Traverse Graph
a. Depth-first Traversal
Depth-first traversal of a tree
3
TCS1044\TCS1093 NOTES
Depth-first traversal of a graph
b. Breadth-first Traversal
Breadth-first traversal of a tree
Breadth-first traversal of a graph
4
TCS1044\TCS1093 NOTES
Adjacency Matrix
Adjacency List