What is a graph?
• A data structure that consists of a set of nodes (vertices) and a set of
edges that relate the nodes to each other
• The set of edges describes relationships among the vertices
Example: graph G can be defined as G = ( V , E ) Where V = {A,B,C,D,E} and
E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.
Types of a graph
Directed vs. undirected graphs
• When the edges in a graph have a direction, the graph
is called directed –(V1,V2),(V2,V3) & (V3,V1)
• When the edges in a graph have no direction, the graph is
called undirected –(V1,V2),(V2,V3) & (V3,V1)
Graph terminology (cont.)
Cyclic Graph
• If a graph contains at least one graph cycle, it is considered
to be cyclic.
Acyclic Graph
• When there are no cycles in a graph, it is called an acyclic
graph.
Cyclic
Acyclic
Graph
Graph
Graph terminology (cont.)
Weighted Graph
• Graph G= (V, E) is called a labeled or weighted graph
because each edge has a value or weight representing the
cost of traversing that edge.
Graph terminology (cont.)
Degree
• The number of edges incident on a vertex determines its degree. The
degree of the vertex is written as degree (v). The in degree of the
vertex V is the number of edges entering into vertex V. Similarly the
out degree of the vertex V is the number of edges existing fro that
vertex V.
Graph implementation
Representations of Graph
Here are the two most common ways to represent a graph :
• Adjacency Matrix
• Adjacency List
Array-based implementation
Adjacency Matrix
Graph implementation (cont.)
• Linked-list implementation
• A 1D array is used to represent the vertices
• A list is used for each vertex v which contains the vertices which are adjacent from v
(adjacency list)
Representation of Undirected
Graph to Adjacency list:
Graph implementation (cont.)
• Linked-list implementation
• A 1D array is used to represent the vertices
• A list is used for each vertex v which contains the vertices which are adjacent from v
(adjacency list)
Representation of Directed Graph to
Adjacency list:
Adjacency Matrix and List-Pros and Cons
Matrix:
Pros:
• Simple to implement
• Easy and fast to tell if a pair (i,j) is an edge: simply check if A[i][j] is 1 or 0
Cons:
• No matter how few edges the graph has, the matrix takes O(n2) in memory
LIST:
Pros:
• Saves on space (memory): the representation takes as many memory words as there are nodes and edge.
Cons:
• It can take up to O(n) time to determine if a pair of nodes (i,j) is an edge: one would have to search the linked list
L[i], which takes time proportional to the length of L[i].
Review Questions
1. Draw a directed graph with five vertices and seven edges. Exactly one of the
edges should be a loop, and do not have any multiple edges.
2. Draw an undirected graph with five edges and four vertices. The vertices
should be called v1, v2, v3 and v4--and there must be a path of length three
from v1 to v4. Draw a squiggly line along this path from v1 to v4.
3. Draw the edge lists that correspond to the graph from the previous question.
4. What are the benefits of using an external iterator as opposed to an internal
iterator?
