Graphs: Terminology and Definitions

Question 1

What is graph?

Answer 1

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|

Question 2

Edge Types

Answer 2

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

Question 3

A graph may be:

Answer 3

– 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

Question 4

Edge components (information)

Answer 4

• Edges may be labeled

- They may have weights, costs, color associated with it

Question 5

Weighted Undirected graph

Answer 5

EX: a network of airports

Question 6

Weighted graph

Answer 6

It has weights associated with the edges. Numerical weights are sometimes referred to as cost

Question 7

Why and when to use graphs over trees?

Answer 7

• 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

Question 8

Endpoints (or end vertices) of an edge

Answer 8

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)

Question 9

Adjacent vertices

Answer 9

Two vertices connected by an edge are adjacent

Question 10

Degree of a vertex

Answer 10

It is the number of edges starting or ending at that vertex

Question 11

Degree in directed graphs

Answer 11

Out-degree: number of edges starting at that vertex

In-degree: number of edges ending at that vertex

Question 12

A path

Answer 12

A sequence of edges (or of adjacent vertices)

Question 13

The length of a path

Answer 13

The number of edges on that path

Question 14

A simple path

Answer 14

A path where all its vertices and edges are distinct

Question 15

A cycle

Answer 15

A path beginning and ending at the same vertex

Question 16

A simple cycle

Answer 16

A cycle which does not pass through any vertex more than once

Question 17

A loop

Answer 17

An edge whose endpoints are the same vertex

Question 18

Labeled graph

Answer 18

• Labels are associated with each edge or each vertex (numbers)
• Weighted: weights are associated with edges

Question 19

Directed/Undirected graph

Answer 19

-All edges are directed/undirected

Question 20

Regular graph

Answer 20

All vertices have the same degree

Question 21

Data Structures for vertices

Answer 21

– Hash table (generally preferred)
– Array
– List
– Binary search tree

Question 22

Data Structures for edges

Answer 22

– Adjacency list

– Adjacency Matrix

Question 23

Adjacency list

Answer 23

• 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

Question 24

Adjacency Matrix

Answer 24

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

Question 25

Adjacency List vs. Adjacency matrix

Answer 25

• Given graph G=(V,E), the running time of an algorithm it’s often expressed in terms of: – |V| and |E|

Question 26

Adjacency List vs. Adjacency matrix Storage and length

Answer 26

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)

Question 27

Adjacency List vs. Adjacency matrix running time

Answer 27

* 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

Question 28

Traversing Algorithms

Answer 28

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

Question 29

Graph Traversal Algorithms

Answer 29

Breadth-first search (BFS) | Depth-first search (DFS)

Question 30

Breadth-first search (BFS)

Answer 30

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

Question 31

Breadth-first search (BFS) running time

Answer 31

• 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

Question 32

BFS Algorithm | Time=O(V+E)

Answer 32

``` 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) ```

Question 33

Depth-first search (DFS)

Answer 33

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)

Question 34

DFS vs. BFS

Answer 34

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

Question 35

DFS Technique

Answer 35

• 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

Question 36

DFS Algorithm Pseudocode O(V+E)

Answer 36

``` 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 ```

Question 37

Edge Classification

Answer 37

* 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

Question 38

Tree Edge

Answer 38

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.

Question 39

Back Edge

Answer 39

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.

Question 40

Forward Edge

Answer 40

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.

Question 41

Cross Edge

Answer 41

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.

Question 42

Edge classification facts

Answer 42

• 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

Question 43

Cycle detection

Answer 43

A directed graph G contains a cycle if and only if a DFS of G yields a back edge

Question 44

Applications of DFS

Answer 44

* 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