Graphs

Outline

• Introduction to Graphs
• Graphs and Representation
• BFS (Breath-First Search)
• DFS (Depth-First Search)
  • in-order
  • post-order
  • pre-order

• Topological Order
• SCC (Strongly Connected Components)
• MST
  • Prim
  • Kruskal

Introduction to Graphs

Introduction to Graphs

• The graph is a non-linear data structure.

• It contains a set of points known as

  • nodes (or vertices) and

  • a set of links known as edges (or Arcs).

Introduction to Graphs

• Here edges are used to connect the vertices. A graph is defined as follows.
• Generally, a graph $G$ is represented as $G=(V,E)$, where
  • $V$ is set of vertices and
  • $E$ is set of edges.

Introduction to Graphs - Example

• The following is a graph with 5 vertices ($V$) and 6 edges ($E$).
• This graph G can be defined as

Graph Terminology

Graph Terminology

Vertex

Individual data element of a graph is called as Vertex. Vertex is also known as node. In above example graph, $A, B, C, D, E$ are known as vertices.

Graph Terminology

Edge

• An edge is a connecting link between two vertices.
• Edge is also known as Arc.
• An edge is represented as

• For example, in above graph the link between vertices $A$ and $B$ is represented as

Graph Terminology

Edge

• In example graph, there are $7$ edges

Graph Terminology

Edge

• Edges are three types.

  • Undirected Edge
  • Directed Edge
  • Weighted Edge

Graph Terminology

Edge

Undirected Edge

• An undirected egde is a bidirectional edge. If there is undirected edge between vertices $A$ and $B$ then edge $(A,B)$ is equal to edge $(B,A)$

Graph Terminology

Edge

Directed Edge

• A directed egde is a unidirectional edge. If there is directed edge between vertices A and B then edge $(A,B)$ is not equal to edge $(B,A)$.

Graph Terminology

Edge

Weighted Edge

• A weighted egde is a edge with value (cost) on it.

Graph Terminology

Undirected Graph

• A graph with only undirected edges is said to be undirected graph.

Graph Terminology

Directed Graph

• A graph with only directed edges is said to be directed graph.

Graph Terminology

Mixed Graph

• A graph with both undirected and directed edges is said to be mixed graph.

Graph Terminology

End vertices or Endpoints

• The two vertices joined by edge are called end vertices (or endpoints) of that edge.

• In graph theory, a vertex with degree 1 is called an end vertex (plural end vertices)

Graph Terminology

Origin

• If a edge is directed, its first endpoint is said to be the origin of it.

Graph Terminology

Destination

• If a edge is directed, its first endpoint is said to be the origin of it and the other endpoint is said to be the destination of that edge.

Graph Terminology

Adjacent

• If there is an edge between vertices $A$ and $B$ then both $A$ and $B$ are said to be adjacent. In other words, vertices A and B are said to be adjacent if there is an edge between them.

Graph Terminology

Incident

• Edge/Arc is said to be incident on a Vertex/Node if the Vertex/Node is one of the endpoints of that Edge/Arc.

• An incidence is a pair $(B, e1)$ where $B$ is a vertex and $e1$ is an edge incident to $B$

• Two distinct incidences $(B, e1)$ and $(v,e2)$ are adjacent if and only if $B = v$, $e1 = e2$ or $BB' = e1$ or $e2$.

Graph Terminology

Outgoing Edge

• A directed edge is said to be outgoing edge on its origin vertex.

Graph Terminology

Incoming Edge

• A directed edge is said to be incoming edge on its destination vertex.

Graph Terminology

Degree

• Total number of edges connected to a vertex is said to be degree of that vertex.

Graph Terminology

Indegree

• Total number of incoming edges connected to a vertex is said to be indegree of that vertex.

Graph Terminology

Outdegree

• Total number of outgoing edges connected to a vertex is said to be outdegree of that vertex.

Graph Terminology

Parallel edges or Multiple edges

• If there are two undirected edges with same end vertices and two directed edges with same origin and destination, such edges are called parallel edges or multiple edges.

Graph Terminology

Self-loop

• Edge (undirected or directed) is a self-loop if its two endpoints coincide with each other.

Graph Terminology

Simple Graph

• A graph is said to be simple if there are no parallel and self-loop edges.

Graph Terminology

Complex Graph

• A graph is said to be complex if there are parallel or self-loop edges.

Graph Terminology

Path

• A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other vertex such that each edge is incident to its predecessor and successor vertex.

Graph Representations

Graph Representations

• Graph data structure is represented using following representations
  • Adjacency Matrix
  • Incidence Matrix
  • Adjacency List

Graph Representations

Adjacency Matrix

• In this representation, the graph is represented using a matrix of size total number of vertices by a total number of vertices.
• That means a graph with 4 vertices is represented using a matrix of size 4X4.
• In this matrix, both rows and columns represent vertices.
  • This matrix is filled with either 1 or 0.
  • Here,
    • 1 represents that there is an edge from row vertex to column vertex and
    • 0 represents that there is no edge from row vertex to column vertex.

Graph Representations

Adjacency Matrix

• Undirected Graph

Graph Representations

Adjacency Matrix

• Directed Graph

Graph Representations

Incidence Matrix

• In this representation, the graph is represented using a matrix of size total number of vertices by a total number of edges.
• That means graph with 4 vertices and 6 edges is represented using a matrix of size 4X6.
• In this matrix, rows represent vertices and columns represents edges.
• This matrix is filled with 0 or 1 or -1.
  • Here,
    • 0 represents that the row edge is not connected to column vertex,
    • 1 represents that the row edge is connected as the outgoing edge to column vertex and
    • -1 represents that the row edge is connected as the incoming edge to column vertex.

Graph Representations

Incidence Matrix

Graph Representations

Adjacency List

• In this representation, every vertex of a graph contains list of its adjacent vertices.

Graph Representations

Adjacency List

• Linked List Implementation

Graph Representations

Adjacency List

• Reference Array Implementation

Graph Representations - Review

Graph Representations - Review

• The standard two ways to represent a graph $G=(V,E)$
  • As a collection of adjacency-lists
  • As an adjacency-matrix
• Adjacency-list representation is usually preferred
• Provides a compact way to represent sparse graphs
  • Those graphs for which $|E| << |V|^2$

Graph Representations - Review

• Adjacency-matrix representation may be preferred
  • for dense graphs for which $|E|$ is close to $|V|^2$
  • when we need to be able to tell quickly if there is an edge connecting two given vertices

Adjacency-List Representation - Review

• An array $Adj$ of $|V|$ lists, one for each vertex $u \in V$
• For each $u \in V$ the adjacency-list $Adj[u]$ contains (pointers to) all vertices $v$ such that $(u,v) \in E$
• That is, $Adj[u]$ consists of all vertices adjacent to $u$ in $G$
• The vertices in each adjacency-list are stored in an arbitrary order

Adjacency-List Representation - Review

• If $G$ is a directed graph
  • The sum of the lengths of the adjacency lists $=|E|$
• If $G$ is an undirected graph
  • The sum of the lengths of the adjacency lists $=2|E|$
  • since an edge $(u,v)$ appears in both $Adj[u]$ and $Adj[v]$

Undirected Graphs Representations - Review

Directed Graphs Representations - Review

Adjacency List Representation (continued) - Review

• Adjacency list representation has the desirable property
  • it requires $O(max(V,E)) = O(V+E)$ memory
  • for both undirected and directed graphs
• Adjacency lists can be adopted to represent weighted graphs
  • each edge has an associated weight typically given by a weight function $w: E \rightarrow R$
• The weight $w(u, v)$ of an edge $(u, v) \in E$ is simply stored with
  • vertex $v$ in $Adj[u]$ or with
  • vertex $u$ in $Adj[v]$ or both

Adjacency List Representation (continued) - Review

• A potential disadvantage of adjacency list representation
  • there is no quicker way to determine if a given edge $(u, v)$ is present in G than to search $v$ in $Adj[u]$ or $u$ in $Adj[v]$
• This disadvantage can be remedied by an adjacency matrix representation at the cost of using asymptotically more memory

Adjacency Matrix Representation - Review

• Assume that, the vertices of $G=(V, E)$ are numbered as $1,2,\dots,|V|$
• Adjacency matrix rep. consists of a $|V|\times|V|$ matrix $A=(a_{ij}) \backepsilon$

• Requires $\Theta(V^2)$ memory independent of the number of edges $|E|$
• We define the transpose of a matrix $A=(a_{ij})$ to be the matrix
  • $A^T = (a_{ij})^T$ given by $a_{ij}^T = a_{ji}$
• Since in an undirected graph, $(u,v)$ and $(v,u)$ represent the same edge $A = A^T$ for an undirected graph
• That is, adjacency matrix of an undirected graph is symmetric
• Hence, in some applications, only upper triangular part is stored

Adjacency Matrix Representation - Review

• Adjacency matrix representation can also be used for
  • weighted graphs

• Adjacency matrix may also be preferable for
  • reasonably small graphs
• Moreover, if the graph is unweighted
  • rather than using one word of memory for each matrix entry adjacency matrix representation uses one bit per entry

Introduction to Graphs - Review

$G=(V,E)$

• Adjency List Complexity $O(degree \ of \ u)$ $(u,v) \in E$
• Sparse Matrix $\rightarrow$ $|E|<|V^2|$
• Dense Matrix $\rightarrow$ $|E| \ close \ to \ |V^2|$
• Space Complexity $\Theta(|V|+|E|)$

Introduction to Graphs - Review

• Many definitions for directed and undirected graphs are the same although certain terms have slightly different meanings
• If $(u,v) \in E$ in a directed graph $G=(V,E)$, we say that $(u,v)$ is incident from or leaves vertex $u$ and is incident to or enters vertex $v$
• If $(u,v) \in E$ in an undirected graph $G=(V,E)$, we say that $(u,v)$ is incident on vertices $u$ and $v$
• If $(u,v)$ is an edge in a graph $G=(V,E)$, we say that vertex $v$ is adjacent to vertex $u$
• When the graph is undirected,the adjacency relation is symmetric
• When the graph is directed
  • the adjacency relation is not necessarily symmetric
  • if $v$ is adjacent to $u$, we sometimes write $u \rightarrow v$

Introduction to Graphs - Review

• The degree of a vertex in an undirected graph is the number of edges incident on it
• In a directed graph,
  • out-degree of a vertex: number of edges leaving it
  • in-degree of a vertex: number of edges entering it
  • degree of a vertex: its in-degree + its out-degree
• A path of length $k$ from a vertex $u$ to a vertex $u'$ in a graph $G=(V,E)$ is a sequence $\langle v_0,v_1,v_2,\dots,v_k \rangle$ of vertices such
  • that $v_0=u$,$v_k=u'$ and $(v_{i-1},v_i) \in E$, for $i=1,2,\dots,k$
• The length of a path is the number of edges in the path

Introduction to Graphs - Review

• If there is a path $p$ from $u$ to $u'$, we say that $u'$ is reachable from $u$ via $p: u \xrightarrow[]{p} u'$
• A path is simple if all vertices in the path are distinct
• A subpath of path $p= \langle v_0,v_1,v_2,\dots,v_k \rangle$ is a contiguous subsequence of its vertices
• That is, for any $0 \leq i \leq j \leq k$, the subsequence of vertices $\langle v_i, v_{i+1},\dots, v_j \rangle$ is a subpath of $p$
• In a directed graph, a path $\langle v_0,v_1,\dots, v_k\rangle$ forms a cycle if $v_0=v_k$ and the path contains at least one edge
• The cycle is simple if, in addition, $v_0,v_1,\dots,v_k$ are distinct
• A self-loop is a cycle of length 1

Introduction to Graphs - Review

Two paths $\langle v_0,v_1,v_2,\dots,v_k\rangle$ & $\langle v_0',v_1',v_2',\dots,v_k'\rangle$ form the same cycle if there is an integer $j$ such that $v_i' = v_{(i+j)\ \text{mod} \ k }$ for $i=0,1,\dots,k-1$

• The path $p_1 = \langle 1, 2, 4, 1\rangle$ forms the same cycles as the paths
  • $p_2= \langle 2, 4, 1, 2 \rangle$ and $p_3= \langle 4, 1, 2, 4\rangle$
• A directed graph with no self-loops is simple
• In an undirected graph a path $\langle v_0,v_1,\dots,v_k\rangle$ forms a cycle
  • if $v_0=v_k$ and $v_1,v_2,\dots,v_k$ are distinct
• A graph with no cycles is acyclic

Introduction to Graphs - Review

• An undirected graph is connected
  • if every pair of vertices is connected by a path
• The connected components of a graph are the
  • equivalence classes of vertices under the
  • "is reachable from" relation
• An undirected graph is connected if it has exactly one component,
  • i.e., if every vertex is reachable from every other vertex

Introduction to Graphs - Review

• A directed graph is strongly-connected
  • if every two vertices are reachable from each other
• The strongly-connected components of a digraph are the
  • equivalence classes of vertices under the
  • "are mutually reachable" relation
• A directed graph is strongly-connected
  • if it has only one strongly-connected component

Introduction to Graphs - Review

• Two graphs $G=(V,E)$ and $G'=(V',E')$ are isomorphic
  • if there exists a bijection $f : V \rightarrow V'$ such that
  • $(u, v) \in E \iff (f (u), f (v)) \in E'$
• That is, we can relabel the vertices of $G$ to be vertices of $G'$ maintaining the corresponding edges in $G$ and $G'$

Introduction to Graphs - Review

• A graph $G'=(V', E')$ is a subgraph of $G=(V,E)$ if
  • $V \subseteq V$ and $E' \subseteq E$
• Given a set $V' \subseteq V$, the subgraph of $G$ induced by $V'$ is the graph
  • $G'=(V', E')$ where $E'=\{(u,v) \in E: u,v \in V'\}$

Introduction to Graphs - Review

• Given an undirected graph $G=(V,E)$, the directed version of $G$ is the directed graph $G'=(V', E')$, where
  • $(u,v)\in E'$ and $(v,u) \in E' \iff (u,v) \in E$
• That is, each undirected edge $(u,v)$ in $G$ is replaced in $G'$ by two directed edges $(u,v)$ and $(v,u)$
• Given a directed graph $G=(V,E)$, the undirected version of G is the undirected graph $G'=(V',E')$, where
  • $(u,v) \in E' \iff u \neq v$ and $(u,v) \in E$
• That is the undirected version contains the edges of G
  • "with their directions removed" and with self-loops eliminated

Introduction to Graphs - Review

• i.e., $(u,v)$ and $(v,u)$ in $G$ are replaced in $G'$ by the same edge $(u,v)$
• In a directed graph $G=(V,E)$, a neighbor of a vertex $u$ is any vertex that is adjacent to $u$ in the undirected version of $G$
• That, is $v$ is a neighbor of $u \iff$ either $(u,v)\in E$ or $(v,u) \in E$

• $v$ is a neighbor of $u$ in both cases
• In an undirected graph, $u$ and $v$ are neighbors if they are adjacent

Introduction to Graphs - Review

• Several kinds of graphs are given special names
  • Complete graph: undirected graph in which every pair of vertices is adjacent
  • Bipartite graph: undirected graph $G=(V,E)$ in which $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ such that
    • $(u,v) \in E$ implies either $u \in V_1$ and $v \in V_2$ or $u \in V_2$ and $v \in V_1$

Introduction to Graphs - Review

• Forest: acyclic, undirected graph
• Tree: connected, acyclic, undirected graph
• Dag: directed acyclic graph
• Multigraph: undirected graph with multiple edges between vertices and self-loops

Introduction to Graphs - Review

• Hypergraph: like an undirected graph, but each hyperedge,
  • rather than connecting two vertices,
  • connects an arbitrary subset of vertices

Free Trees

Free Trees

• A free tree is a connected, acyclic, undirected graph
• We often omit the adjective "free" when we say that a graph is a tree
• If an undirected graph is acyclic but possibly disconnected it is a forest

Theorem (Properties of Free Trees)

• The following are equivalent for an undirected graph $G=(V,E)$

1. $G$ is a free tree
2. Any two vertices in $G$ are connected by a unique simple-path
3. $G$ is connected, but if any edge is removed from E the resulting graph is disconnected
4. $G$ is connected, and $|E| = |V|-1$
5. $G$ is acyclic, and $|E| = |V| - 1$
6. $G$ is acyclic, but if any edge is added to $E$, the resulting graph contains a cycle

Properties of Free Trees $(1 \Rightarrow 2)$

1. G is a free tree
2. Any two vertices in G are connected by a unique simple-path

Properties of Free Trees $(1 \Rightarrow 2)$

• Since a tree is connected, any two vertices in $G$ are connected by a simple path
  • Let two vertices $u,v \in V$ are connected by two simple paths $p_1$ and $p_2$
  • Let $w$ and $z$ be the first vertices at which $p_1$ and $p_2$ diverge and re-converge
  • Let $p'_1$ be the subpath of $p_1$ from $w$ to $z$
  • Let $p'_2$ be the subpath of $p_2$ from $w$ to $z$
  • $p'_1$ and $p'_2$ share no vertices except their end points
  • The path $p'_1 || p'_2$ is a cycle (contradiction)

Properties of Free Trees $(1 \Rightarrow 2)$

• $p'_1$ and $p'_2$ share no vertices except their end points
• $p'_1 || p'_2$ is a cycle (contradiction)
• Thus, if $G$ is a tree, there can be at most one path between two vertices

Properties of Free Trees $(2 \Rightarrow 3)$

2. Any two vertices in $G$ are connected by a unique simple-path
3. $G$ is connected, but if any edge is removed from $E$ the resulting graph is disconnected

Properties of Free Trees $(2 \Rightarrow 3)$

• If any two vertices in $G$ are connected by a unique simple path, then $G$ is connected
  • Let $(u,v)$ be any edge in $E$. This edge is a path from $u$ to $v$. So it must be the unique path from $u$ to $v$
• Thus, if we remove $(u,v)$ from $G$, there is no path from $u$ to $v$
• Hence, its removal disconnects $G$

Properties of Free Trees $(3 \Rightarrow 4)$

• Before proving $3 \Rightarrow 4$ consider the following
• Lemma: any connected, undirected graph $G=(V,E)$
  • satisfies $|E| \geq |V|-1$
• Proof: Consider a graph $G'$ with $|V|$ vertices and no edges.
  • Thus initially there are $|C|=|V|$ connected components
    • Each isolated vertex is a connected component
  • Consider an edge $(u,v)$ and let $C_u$ and $C_v$ denote the connected-components of $u$ and $v$

Properties of Free Trees (Lemma)$

• If $C_u \neq C_v$ then $(u,v)$ connects $C_u$ and $C_v$ into a
  • connected component $C_{uv}$
• Otherwise $(u,v)$ adds an extra edge to the
  • connected component $C_u = C_v$
• Hence, each edge added to the graph reduces the
  • number of connected components by at most $1$
• Thus, at least $|V|-1$ edges are required to reduce the number of components to $1$
  • $Q.E.D$

Properties of Free Trees $(3 \Rightarrow 4)$

3. $G$ is connected, but if any edge is removed from $E$ the resulting graph is disconnected
4. $G$ is connected, and $|E|=|V|-1$

Properties of Free Trees $(3 \Rightarrow 4)$

• By assuming (3), the graph $G$ is connected
• We need to show both $|E| \geq |V|-1$ and $|E| \leq |V|-1$ in
  • order to show that $|E| = |V|-1$
• $|E| \geq |V|-1$: valid due previous lemma
• $|E| \leq |V|-1$: (proof by induction)
• Basis: a connected graph with $n=1$ or $n=2$ vertices has $n-1$ edges
• IH: suppose that all graphs $G'=(V',E')$ satisfying (3) also
  • satisfy $|E'| \leq |V'|-1$

Properties of Free Trees $(3 \Rightarrow 4)$

• Consider $G=(V,E)$ that satisfies (3) with $|V|= n \geq 3$
• Removing an arbitrary edge $(u,v)$ from $G$ separates the graph into 2 connected graphs $G_u=(V_u,E_u)$ and $G_v=(V_v,E_v)$ such that $V = V_u \cup V_v$ and $E=E_u \cup E_v$
• Hence, connected graphs $G_u$ and $G_v$ both satisfy (3) else $G$ would not satisfy $(3)$
• Note that $|V_u|$ and $|V_v| < n$ since $|V_u| + |Vv| = n$
• Hence, $|E_u| \leq |V_u|-1$ and $|E_v| \leq |V_v|-1$ (by IH)
• Thus, $|E| = |E_u| + |E_v| + 1 \leq (|V_u|-1) + (|V_v|-1) + 1$
  • $\Rightarrow |E| \leq |V|-1$
  • $Q.E.D$

Properties of Free Trees $(4 \Rightarrow 5)$

4. $G$ is connected, and $|E|=|V|-1$
5. $G$ is acyclic, and $|E|=|V|-1$

Properties of Free Trees $(4 \Rightarrow 5)$

• Suppose that $G$ is connected, and $|E|=|V|-1$, we must
  • show that $G$ is acyclic
• Suppose $G$ has a cycle containing $k$ vertices $v_1, v_2,\dots, v_k$
• Let $G_k=(V_k,E_k)$ be subgraph of $G$ consisting of the cycle

• If $k < |V|$, there must be a vertex $v_{k+1} \in V-V_k$ that is adjacent to some vertex $v_i \in V_k$, since $G$ is connected

Properties of Free Trees $(4 \Rightarrow 5)$

• Define $G_{k+1}=(V_{k+1},E_{k+1})$ to be subgraph of $G$ with $V_{k+1}=V_k \cup v_{k+1}$ and $E_{k+1} = E_k \cup (v_{k+1},v_i)$

• If $k+1 < |V|$, we can similarly define $G_{k+2} =(V_{k+2},E_{k+2})$ to be the subgraph of $G$ with
  • $V_{k+2}= V_{k+1} \cup v_{k+2}$ and $E_{k+2} = E_{k+1} \cup (v_{k+2},v_j)$
  • for some $v_j \in V_{k+1}$ where $|V_{k+2}|=|E_{k+2}|$

Properties of Free Trees $(4 \Rightarrow 5)$

• We can continue defining $G_{k+m}$ with $|V_{k+m}|=|E_{k+m}|$ until we obtain $G_n = (V_n,E_n)$ where
  • $n=|V|$ and $V_n=|V|$ and $|V_n|=|E_n|=|V|$
• Since $G_n$ is a subgraph of $G$, we have
  • $E_n \subseteq E \Rightarrow |E| \geq |E_n|=|V|$ which contradicts the assumption $|E|=|V|-1$
• Hence $G$ is acyclic
  • $Q.E.D$

Properties of Free Trees $(5 \Rightarrow 6)$

5. $G$ is acyclic, and $|E| = |V| - 1$
6. $G$ is acyclic, but if any edge is added to $E$, the resulting graph contains a cycle

Properties of Free Trees $(5 \Rightarrow 6)$

• Suppose that $G$ is acyclic and $|E| = |V| - 1$
• Let $k$ be the number of connected components of $G$
• $G_1=(V_1,E_1),G_2=(V_2,E_2),\dots,G_k=(V_k,E_k)$ such that
  • $\overset{k}{\underset{i=1}{\cup}}V_i=V;V_i \cap V_j = \empty; 1 \leq i,j \leq k$ and $i \neq j$
  • $\overset{k}{\underset{i=1}{\cup}}E_i=E;E_i \cap E_j = \empty; 1 \leq i,j \leq k$ and $i \neq j$
• Each connected component $G_i$ is a tree by definition.

Properties of Free Trees $(5 \Rightarrow 6)$

• Since $(1 \Rightarrow 5)$ each component $G_i$ is satisfies
  • $|E_i| = |V_i| -1$ for $i =1,2, \dots,k$
• Thus
  • $\sum \limits_{i=1}^{k} |E_i| = \sum \limits_{i=1}^{k} |V_i| - \sum \limits_{i=1}^{k} 1$
  • $|E|=|V|-k$
• Therefore, we must have $k=1$

Properties of Free Trees $(5 \Rightarrow 6)$

• That is $(5) \Rightarrow G$ is connected $\Rightarrow G$ is a tree
• Since $(1 \Rightarrow 2)$
  • any two vertices in $G$ are connected by a unique simple path
• Thus,
  • adding any edge to $G$ creates a cycle

Properties of Free Trees $(6 \Rightarrow 1)$

6. $G$ is acyclic, but if any edge is added to $E$, the resulting graph contains a cycle
7. $G$ is a free tree

Properties of Free Trees $(6 \Rightarrow 1)$

• Suppose that $G$ is acyclic but if any edge is added to $E$ a cycle is created
• We must show that $G$ is connected due to the definition
• Let $u$ and $v$ be two arbitrary vertices in $G$
• If $u$ and $v$ are not already adjacent
  • adding the edge $(u,v)$ creates a cycle in
  • which all edges but $(u,v)$ belong to $G$

Properties of Free Trees $(6 \Rightarrow 1)$

• Thus there is a path from $u$ to $v$, and since $u$ and $v$ are chosen arbitrarily $G$ is connected

Elementary Graph Algorithms

Online Visual Animations

Online Visual Animations

• Graph Structures

• https://visualgo.net/en/graphds?slide=1

• Single-Source Shortest Paths (SSSP)

  • https://visualgo.net/en/sssp?slide=1

• Minimum Spanning Tree (MST)

  • https://visualgo.net/en/mst?slide=1

• Convex Hull

  • https://visualgo.net/en/convexhull?slide=1

Online Visual Animations

• Data Structure Visualizations (University of Sout Florida-USF)
  • https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Online Visual Animations

• Common Graph Algorithms
  • https://algorithm-visualizer.org/

Graph Tools

Graph Tools

• Graphviz Tools
  • https://graphviz.org/download/
• Graphviz (short for Graph Visualization Software) is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts having the file name extension "gv". It also provides libraries for software applications to use the tools. Graphviz is free software licensed under the Eclipse Public License.

Graph Tools

• Graphviz Tools
  • https://graphviz.org/download/
  • https://graphviz.org/doc/info/command.html
  • https://graphviz.org/docs/outputs/svg/
  • http://magjac.com/graphviz-visual-editor/
  • https://graphs.grevian.org/graph
• Graphviz Tutorials
  • https://graphs.grevian.org/example#example-1
  • https://graphs.grevian.org/reference

Graphviz Gallery

Family Tree

• https://graphviz.org/Gallery/directed/kennedyanc.html

  UML

• https://graphviz.org/Gallery/directed/UML_Class_diagram.html

  Data Structure

• https://graphviz.org/Gallery/gradient/datastruct.html

• https://graphviz.org/Gallery/directed/datastruct.html

Graphviz Gallery

Neural Network (Keras)

• https://graphviz.org/Gallery/directed/neural-network.html

  Linux Kernel Diagram

• https://graphviz.org/Gallery/directed/Linux_kernel_diagram.html

Graphviz Tools and Binaries

• Graphviz consists of a graph description language named the DOT language[4] and a set of tools that can generate and/or process DOT files:

Graphviz Layout Engines

dot

a command-line tool to produce layered drawings of directed graphs in a variety of output formats, such as (PostScript, PDF, SVG, annotated text and so on).

Visit: https://graphviz.org/docs/layouts/dot/

Graphviz Layout Engines

neato

useful for undirected graphs. "spring model" layout, minimizes global energy. Useful for graphs up to about 1000 nodes

Visit : https://graphviz.org/docs/layouts/neato/

Graphviz Layout Engines

fdp

useful for undirected graphs. "spring model" which minimizes forces instead of energy

Visit : https://graphviz.org/docs/layouts/fdp/

Graphviz Layout Engines

sfdp

multiscale version of fdp for the layout of large undirected graphs

Visit : https://graphviz.org/docs/layouts/sfdp/

Graphviz Layout Engines

twopi

for radial graph layouts. Nodes are placed on concentric circles depending their distance from a given root node

Visit : https://graphviz.org/docs/layouts/twopi/

Graphviz Layout Engines

circo

circular layout. Suitable for certain diagrams of multiple cyclic structures, such as certain telecommunications networks

Visit : https://graphviz.org/docs/layouts/circo/

Graphviz Layout Engines

osage

osage draws clustered graphs. Suitable for certain diagrams of multiple cyclic structures, such as certain telecommunications networks

Visit : https://graphviz.org/docs/layouts/osage/

Graphviz Layout Engines

patchwork

patchwork draws clustered graphs using a squarified treemap layout.

Visit : https://graphviz.org/docs/layouts/patchwork/

Graphviz Layout Engines

dotty (DEPRECATED)

a graphical user interface to visualize and edit graphs.

Graphviz Tools

lefty (DEPRECATED)

a programmable (in a language inspired by EZ[5]) widget that displays DOT graphs and allows the user to perform actions on them with the mouse. Therefore, Lefty can be used as the view in a model–view–controller GUI application that uses graphs.

Graphviz Tools

gml2gv - gv2gml

convert to/from GML, another graph file format.

Graphviz Tools

graphml2g

convert a GraphML file to the DOT format.

Graphviz Tools

gxl2gv - gv2gxl

convert to/from GXL, another graph file format.

Graphviz Tools

for more information visit

• https://graphviz.org/documentation/#tool-manual-pages

Graphviz API

• Visit
  • https://graphviz.org/documentation/#sample-programs-using-graphviz

Graph Tools

• Plantuml Tools (https://plantuml.com/download)
  • PlantUML is an open-source tool allowing users to create diagrams from a plain text language. Besides various UML diagrams, PlantUML has support for various other software development related formats (such as Archimate, Block diagram, BPMN, C4, Computer network diagram, ERD, Gantt chart, Mind map, and WBD), as well as visualisation of JSON and YAML files.

Graph Tools

• Plantuml Tutorials
  • Visit OOP Plantuml Course Notes

Graph Tools

• Plantuml Graphs and References
  • https://plantuml.com/use-case-diagram
  • https://plantuml.com/deployment-diagram
  • https://plantuml.com/component-diagram
  • https://plantuml.com/mindmap-diagram
  • https://plantuml.com/object-diagram
  • https://plantuml.com/state-diagram
  • https://plantuml.com/wbs-diagram
  • https://plantuml.com/json
  • https://plantuml.com/yaml

Graph Tools

• Plantuml API
  • https://plantuml.com/api

Graph Tools

• Microsoft Graph Layout
• MSAGL is a .NET tool for graph layout and viewing.
• It was developed in Microsoft by Lev Nachmanson, Sergey Pupyrev, Tim Dwyer and Ted Hart.
• MSAGL is available as open source.
  • Demo Project
    • https://github.com/ucoruh/microsoft-graph-layout-cs-demo
  • Library
    • https://github.com/microsoft/automatic-graph-layout
  • Website
    • https://www.microsoft.com/en-us/research/project/microsoft-automatic-graph-layout/

Elementary Graph Algorithms

Elementary Graph Algorithms

• Graph Traversal

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

• Strongly connected components (SCC)

  • Kosaraju's algorithm
  • Tarjan's algorithm

Elementary Graph Algorithms

• Topological sort

  • DFS version
  • BFS version (Kahn's algorithm)

• Minimum spanning tree

  • Kruskal's algorithm
  • Prim's algorithm

Elementary Graph Algorithms

• Cycle Detection
  • DFS
  • BFS
• Bipartite Graph Check
  • DFS
  • BFS

Breadth-first search (BFS)

Graph Traversal

Breadth-first search (BFS)

• Breadth-first search (BFS) is a graph traversal algorithm that starts at a vertex and explores as far as possible along each branch before backtracking.

Graph Traversal

Breadth-first search (BFS)

• Graph $G=(V, E)$, directed or undirected with adjacency list repres.
• GOAL: Systematically explores edges of G to
  • discover every vertex reachable from the source vertex $s$
  • compute the shortest path distance of every vertex
    • from the source vertex $s$
  • produce a breadth-first tree (BFT) $G_\pi$ with root $s$
    • BFT contains all vertices reachable from $s$
    • the unique path from any vertex $v$ to $s$ in G constitutes a shortest path from $s$ to $v$ in $G$
• IDEA: Expanding frontier across the breadth -greedy-
  • propagate a wave $1$ edge-distance at a time
  • using a FIFO queue: $O(1)$ time to update pointers to both ends

Graph Traversal

Breadth-first search (BFS)

• Maintains the following fields for each $u \in V$
  • $color[u]:$ color of $u$
    • $WHITE$ : not discovered yet
    • $GRAY$ : discovered and to be or being processed
    • $BLACK$ : discovered and processed
  • $\pi[u]$: parent of $u$ ($NIL$ of $u = s$ or $u$ is not discovered yet)
  • $d[u]$: distance of $u$ from $s$

$Processing \ a \ vertex = scanning \ its \ adjacency \ list$

Graph Traversal

Breadth-first search (BFS) Algorithm

Graph Traversal

Breadth-first search (BFS)

• In this algorithm, we use a queue to store the vertices that are yet to be visited.

• Complexity of following part is $O(V)$

Graph Traversal

Breadth-first search (BFS)

• We enqueue the first vertex and mark it as visited.

• Complexity of following part is $O(1)$

Graph Traversal

Breadth-first search (BFS)

• We dequeue a vertex u and mark it as visited.

• We enqueue all the adjacent vertices of u.

• Complexity of following part is $O(E)$

Graph Traversal

Breadth-first search (BFS)

• Complexity of BFS is $O(V+E) = O(V)+O(E)+O(1)$

Graph Traversal

Breadth-first search (BFS) Complete Algorithm

Graph Traversal

Breadth-first search (BFS) Example-1

• s is the source vertex.

Graph Traversal

Breadth-first search (BFS) Example-1

• STEP-1

Graph Traversal

Breadth-first search (BFS) Example-1

• STEP-2

Graph Traversal

Breadth-first search (BFS) Example-1

• STEP-3

Graph Traversal

Breadth-first search (BFS) Example-1

• STEP-4

Graph Traversal

Breadth-first search (BFS) Example-1

• STEP-5

Graph Traversal

Breadth-first search (BFS) Example-1

• STEP-6

Graph Traversal

Breadth-first search (BFS) Example-1

• STEP-7