Graphs: Terminology and Definitions Flashcards
What is graph?
A graph is a mathematical structure consisting of two types of elements
• G = (V,E) where
– V is a set of nodes called vertices
——>The order of a graph is the number of its vertices, i.e. |V|
– E is a collection of edges that connect pairs of vertices
——-> The size of a graph is the number of its edges, i.e. |E|
Edge Types
Directed Edge: – Ordered pair of vertices (u,v) – First vertex u is the origin – Second vertex v is the destination EX: u -------> v
Undirected Edge:
– Unordered pair of vertices (u,v)
EX: u ——– v
A graph may be:
– Undirected, i.e. there is no distinction between two vertices associated with each edge
EX: edge (3,2) is the same as edge (2,3)
()Directed, i.e. the edges are directed from one vertex to the other
EX: edge (1,2) goes from node 1 to node 2,
1 –> 2
Edge components (information)
- Edges may be labeled
- They may have weights, costs, color associated with it
Weighted Undirected graph
EX: a network of airports
Weighted graph
It has weights associated with the edges. Numerical weights are sometimes referred to as cost
Why and when to use graphs over trees?
- Tree can be considered a limited type of graph
- Trees are useful for describing hierarchical information, but they can only describe information where the parent/child relationship is upheld
- To describe information that doesn’t meet this criteria we use graphs
Endpoints (or end vertices) of an edge
Two or more edges having a vertex v as at least one of their endpoints are called edges incident to v
EX: (6, 10), (4,10)
Adjacent vertices
Two vertices connected by an edge are adjacent
Degree of a vertex
It is the number of edges starting or ending at that vertex
Degree in directed graphs
Out-degree: number of edges starting at that vertex
In-degree: number of edges ending at that vertex
A path
A sequence of edges (or of adjacent vertices)
The length of a path
The number of edges on that path
A simple path
A path where all its vertices and edges are distinct
A cycle
A path beginning and ending at the same vertex
A simple cycle
A cycle which does not pass through any vertex more than once
A loop
An edge whose endpoints are the same vertex
Labeled graph
- Labels are associated with each edge or each vertex (numbers)
- Weighted: weights are associated with edges
Directed/Undirected graph
-All edges are directed/undirected
Regular graph
All vertices have the same degree
Data Structures for vertices
– Hash table (generally preferred)
– Array
– List
– Binary search tree
Data Structures for edges
– Adjacency list
– Adjacency Matrix
Adjacency list
- It consists of an array A of |V| lists, one for each vertex in V
- The vertices in each adjacency list are typically stored in arbitrary order
Adjacency Matrix
It is a two dimensional array A of dimensions n×n (n is
the number of vertices in G) , where:
–If the graph is directed, then the element a(i,j) is 1 if and only if there is a directed edge from vertex i to vertex j.
– If the graph is undirected, then the element a(i, j) and a(j, i) are 1 if and only if there is an edge from vertex i to vertex j
a(i, j) = 1 if (i, j)∈E 0 if (i, j)∉E
Adjacency List vs. Adjacency matrix
• Given graph G=(V,E), the running time of an algorithm it’s often expressed in terms of:
– |V| and |E|
Adjacency List vs. Adjacency matrix Storage and length
Storagerequired:
– Adjacency list
—->If G is a directed graph, the sum of the lengths of all
adjacency lists is |E|
—-> If G is an undirected graph, the sum of the lengths of all
adjacency lists is 2|E|
—->In both cases the memory required is O(V + E)
– Adjacency matrix
—–>O(V^2)
Adjacency List vs. Adjacency matrix running time
- Running time for operations such as inserting an edge, determining if an edge exists, and deleting an edge
- Adjacency list all take potentially O(V)
- Adjacency matrix all take O(1)
•If time is of the essence and these operations predominate, then a matrix may be the best choice
Traversing Algorithms
traverse means to visit the vertices in some systematic order
ü Preorder - visit each node before its children
ü Postorder - visit each node after its children
ü Indorder - BST only, visit left subtree, node, right subtree
Graph Traversal Algorithms
Breadth-first search (BFS)
Depth-first search (DFS)
Breadth-first search (BFS)
General technique for traversing a graph
• Archetype for many graph algorithms:
– Dijkstra’s shortest path algorithm
– Prim’s minimum spanning tree algorithm
Idea: Given a graph G and a source vertex s, BFS systematically explores the edges of G to “discover” every vertex that is reachable from s
Breadth-first search (BFS) running time
• Time=O(V+E)
– O(V) because every vertex dequeued at most once
– O(E) because for every vertex dequeued we examine (u, v)
• directed graph every edge examined at most once
• undirected graph every edge examined at most twice
BFS Algorithm
Time=O(V+E)
BFS(G, s)
for each u ∈ V - {s} do
u.dist ← ∞ s.dist ← 0
Initialize empty queue Q
ENQUEUE (Q, s)
while Q is not empty do
u ← DEQUEUE(Q)
for each v ∈ Adj[u] do
if v.dist = ∞ then
v.dist ← u.dist + 1
ENQUEUE (Q, v)Depth-first search (DFS)
It is a strategy for exploring a graph
Useful for the following problems:
….Testing whether a graph is connected
…Computing a path between two vertices or equivalently reporting that no such path exists
…..Computing a cycle or equivalently reporting that no such cycle exists
….Uses a backtracking technique (try each possibility until one is found)
DFS vs. BFS
DFS uses a strategy that searches “deeper” in the graph whenever possible, unlike BFS which discovers all vertices at distance k from the source before discovering any vertices at distance k+1
DFS Technique
• Depth-first search is like exploring a maze
– Follow path until you get stuck
….Backtrack until you reach an unexplored neighbor
– Recursively explore
– Careful not to repeat a vertex
DFS Algorithm Pseudocode O(V+E)
DFS(V, E)
for each u ∈ V do
u.color ← WHITE
time ← 0
for each u ∈ V do
if u.color = WHITE then
DFS-VISIT(u)
DFS-VISIT(u)
u.color ← GRAY
time ← time + 1
u.i ← time
for each v ∈ Adj[u] do
if v.color = WHITE then
DFS-VIST(v)
u.color ← BLACK
time ← time + 1
u.f ← time
Edge Classification
- The edge we traverse as we execute DFS can be classified into four types: tree, back, forward, and cross edges
- The classification of edge(u,v) depends on whether we have visited v before in the DFS and if so, the relationship between u and v
Tree Edge
As we traverse the edge(u, v) if v is visited for the first time, then the edge is a tree edge
(u,v) is a tree edge if v was first discovered by exploring edge (u,v). A tree edge always describes a relation between a node and one of its direct descendants. This indicates that u.i < v.i, (u’s discovery time is less than v’s discovery time), so a tree edge points from a “low” to a “high” node.
Back Edge
As we traverse the edge(u, v) if v has already been visited:
If v is an ancestor of u, then(u, v) is a back edge
Back edges are those edges (u,v) connecting a vertex v to an ancestor u. Self-loops are considered to be back edges. Back edges describe descendant-to-ancestor relations, as they lead from “high” to “low” nodes.
Forward Edge
As we traverse the edge(u, v) if v has already been visited:
If v is an descendant of u, then(u, v) is a forward edge
Forward edges are those edges (u,v) connecting a vertex u to a descendant v in a depth-first tree. Forward edges describe ancestor-to-descendant relations, as they lead from “low” to “high” nodes.
Cross Edge
As we traverse the edge(u, v) if v has already been visited:
If v is neither an ancestor or descendant of u, then(u, v) is a cross edge
Cross edges link nodes with no ancestor-descendant relation and point from “high” to “low” nodes.
Edge classification facts
• If G is undirected, DFS produces only tree and back edges
• G is a directed acyclic graph if and only if DFS yields no back edges
–Directed acyclic graph (DAG) is a directed graph with no cycles
Cycle detection
A directed graph G contains a cycle if and only if a DFS of G yields a back edge
Applications of DFS
- Topological sort
- DFS can be used to perform a topological sort of a directed acyclic graph
- A topological sort of a DAG is a linear ordering of all its vertices such that if DAG contains an edge (u, v), then u appears before v in ordering
