Graph
Data Structure
Graph
Definition: A graph G consists of two sets
a finite, nonempty set of vertices V(G)
a finite, possible empty set of edges E(G)
G(V,E) represents a graph
The number of vertices is written $V(n)$, and the number of edges is written $E(e)$
General graphs differ from trees
 need not have a root node
 no implicit parentchild relationship
 may be several (or no) paths from one vertex to another
Definition
For a Directed graph
$if\ u, v\ are\ two\ vertices,then\ <u, v> is\ an\ arc(edge), u\ is\ called\ as\ tail, v\ is\ called\ head$
$Example:$
$[u]\rightarrow[v]\ is\ called <u, v>, and\ [v]\rightarrow[u] is\ called <v, u>$
$$ [u]\rightarrow[v] $$
$$ [v]\rightarrow[u] $$
A directed graph is one in which each edge is a directed pair of vertices, $< u,v > \neq < v,u >$
For an undirected graph
An undirected graph is one in which the pair of vertices in an edge is unordered, $（u,v）= （v,u）$ $$ (u, v)=(v, u) $$
Complete graph
A complete graph is a graph that has the $maximum\ number\ of\ edges$; A complete graph is a graph in which $there\ is\ an\ edge\ between\ every\ pair\ of\ vertices$.
for a $undirected\ graph$ with $n\ vertices$, the maximum number of edges is $\frac {n(n1)}{2}(C_n^2)$
for a $directed\ graph$ with n vertices, the maximum number of edges is $n(n1)$
Sparse Graph and Dense Graph
If the edges of a graph is $e<n\log n$, the graph is called Sparse Graph ,otherwise, it is called as Dense Graph
Examples for Graph
Undirected graph
$$ V(G_1)={0,1,2,3}\ and\ E(G_1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} $$
$$ Graph \rightarrow G_1 $$
Directed graph
$$ V(G_2)={0,1,2}\ and\ E(G_2)={<0, 1>,<1, 0>,<1, 2>} $$
$$ Graph\rightarrow G_2 $$
Adjacent and Incident
If $(v_0 ,v_1 )$ is an edge in an $undirected\ graph$
$v_0$ and $v_1$ are $adjacent$
The edge $(v_0 , v_1)$ is $incident$ on vertices $v_0\ and\ v_1$
If $<v_0 , v_1>$ is an edge in a $directed\ graph$
$v_0$ is $adjacent\ to$ $v_1$ , and $v_1$ is $adjacent\ from$ $v_0$ .
The edge $<v_0 , v_1>$ is $incident$ on $v_0$ and $v_1$
Weighted graph(network)
There is some cost or weight associated with each edge
Subgraph
A subgraph of $G$ is a graph $G’$ such that $V(G’)$ is a subset of $V(G)$ and $E(G’)$ is a subset of $E(G)$ $$ V(G)\supseteq V(G’) $$
$$ E(G)\supseteq E(G’) $$
Degree
The degree of a vertex (TD: Total Degree) is the number of edges incident to that vertex
Indegree and Outdegree(for a directed graph)
The indegree of a vertex v (ID) is the number of edges that have v as the head
The outdegree of a vertex v (OD) is the number of edges that have v as the tail
Conclusion:
if $d_i$ is the degree of a vertex $i$ in a graph $G$ with $n$ vertices and $e$ edges, the number of edges is $$ e=\frac{\sum_{i=1}^n d_i}{2} $$
Examples for degree
directed graph:
$$ 0\rightarrow in=1\ and\ out=1 $$
$$ 1\rightarrow in=1\ and\ out=2 $$
$$ 2\rightarrow in=1\ and\ out=0 $$
Undirected graph:
$$ 0\rightarrow 2 $$
$$ [1,2]\rightarrow 3 $$
$$ [3, 4, 5, 6] \rightarrow 1 $$
Path
Definition
$A\ path\ from\ vertex\ v_p\ to\ v_q\ in\ a\ graph\ G\ is\ a\ sequence\ of\ vertices,$
$\rightarrow v_p , v_{i_1} , v_{i_2} , …, v_{i_n}, v_{q}\ such\ that (v_p , v_{i_1}), (v_{i_1} ,v_{i_2} ), …, (v_{i_n}, v_q) are\ edges\ in\ a\ graph$
Length of a path
The length of a path is the number of edges on it
Simple path
A simple path is a path in which all vertices are distinct
Simple Circle
A simple cycle is a path in which all vertices,except the first and the last, are distinct. The first and the last vertices are the same
Example of Graph
Traffic flow can be modeled by a graph
Each street intersection represents a vertex, each street is an edge
Edge costs could represent, among other things, a speed limit or capacity
We could ask for the shortest route or use this information to find the most likely location for bottleneck
ADT
Graph


Graph Implementation
Adjacency Matrix (Array)
Definition
The adjacency matrix of G is a twodimensional n by n array, say $A[n] [n]$ $$ A[i][j]=\begin{cases} 1\ if\ <V_i,V_j> \in E\ or\ (V_i,V_j)\in E\newline 0\ otherwise \end{cases} $$
For a weighted graph
$$ A[i][j]=\begin{cases} W(i, j)\ when\ i\neq j\ and\ <V_i,V_j> \in E\ or\ (V_i,V_j)\in E\newline \infty\ otherwise \end{cases} $$
Example
For a graph
$$ \begin{pmatrix} 0& 1& 0\newline 1& 0& 1\newline 0& 0& 0 \end{pmatrix} $$
For a weight graph
The weight of the edge from vertex i to vertex j is used instead of 1 in the adjacency matrix $$ \begin{pmatrix} \infty& 1& \infty& 4\newline \infty& \infty& 9& 2\newline 3& 5& \infty& 8\newline \infty& \infty& 6& \infty \end{pmatrix} $$
Notice
The adjacency matrix for an undirected graph is symmetric
The adjacency matrix for a digraph need not be symmetric
Merits of Adjacency Matrix
From the adjacency matrix, to determine the connection of vertices is easy
For a undirected graph, the degree of a vertex i is $\sum_{j=1}^n A[i][j]$
For a directed graph
The sum of 1 in row i of the adjacency matrix is yields the outdegree of the $i^{th}$ vertex $$ \begin{bmatrix} a_1&a_2&a_3&\dots&a_n \end{bmatrix} $$ The sum of the entries in the $i^{th}$ column is its in degree $$ \begin{bmatrix} a_1\newline a_2\newline a_3\newline \vdots\newline a_n \end{bmatrix} $$
Code


Create a graph


Adjacency List
If a graph does not have many edges, the adjacency matrix will be sparse
such representation is a waste of space
use an array of pointers to linked rowlists
adjacencylist representation for graphs
Description of Adjacency List
Each row in adjacency matrix is represented as an adjacency list
The graph is represented by an array or vector v[1],v[2],…,v[n], one element for each vertex in the graph
Each v[i] stores the data stored in vertex i together with a linked list of the numbers of all vertices adjacent from vertex i
Example:
Merits and Demerits of Adjacency List
degree of a vertex in an undirected graph – # of nodes in adjacency list
outdegree of a vertex in a directed graph – # of nodes in its adjacency list
indegree of a vertex in a directed graph – traverse the whole data structure
Inverse adjacency list
Linked table is entry edge
code


Traversing Graph
Some applications require visiting every vertex in a graph exactly once.
The application may require that vertices should be visited in some special order based on graph topology
DFS: DepthFirst Search
BFS: BreadthFirst Search
DepthFirst Search(DFS)
Basic idea

Start from a given vertex v and visit it.

Visit the first neighbor w of v. Then visit the first neighbor of w that has not already been visited, etc.

If a node with no unexamined neighbors, then backup to the last visited node and examine its remaining neighbors.

The search continues until all nodes of the graph have been examined.
Example
$$ \begin{bmatrix} V1 &V2 &V4 &V8 &V3 &V6 &V7 &V5 \end{bmatrix} $$
Algorithm
Difficulties：

How to determine whether v has been visited?

How to search the neighbor of v？
Solutions：

Using an array visited[n]. When i th vertex has been visited, visited[i]=TRUE.

Varying by different data structure:
• Adjacency Matrix
• Adjacency List
DFS uses backtracking. Recursion is a natural technique for such problems
a stack is automatically maintained to make backtracking possible
DFS

Visit the start vertex v.

For each vertex w adjacent to v do:
• If w has not been visited, apply the DepthFirst Search (DFS) algorithm with w as the start vertex.
Code


Algorithm Analysis
Let G=(V,E) be a graph with n vertices and e edges
$Adjacency\ list:\ O(n+e)$
$Adjacency\ matrix:\ O(n^2)$
BreadFirst Search(BFS)
Basic idea

Start from a given vertex v and visit it.

Visit all neighbors of v.

Then visit all neighbors of first neighbor w of v.

Then visit all neighbors of second neighbor x of v, etc
Example
$$ \begin{bmatrix} V1 &V2 &V3 &V4 &V6 &V7 &V8 &V5 \end{bmatrix} $$
Algorithm
BFS visits nodes level by level
While visiting each node on a given level
store it
so that, we can return to it after completing this level
so that nodes adjacent from it can be visited
Because the first node visited on a given level should be the first one to which we return, a queue is an appropriate data structure for storing the nodes
BFS

Visit the start vertex v.

Initialize a queue to contain only the start vertex.

While the queue is not empty do:
• Remove a vertex v from the queue.
• For all vertices w adjacent to v do:
– If w has not been visited then
i. Visit w. ii. Add w to the queue.
Code


Algorithm Analysis
Let G=(V,E) be a graph with n vertices and e edges
$Adjacency\ list:\ O(n+e)$
$Adjacency\ matrix:\ O(n^2)$
For adjacency matrix unweighted directed Graph in C++
$$ A[i][j]=\begin{cases} 1\ if\ <V_i,V_j> \in E\ or\ (V_i,V_j)\in E\newline 0\ otherwise \end{cases} $$
Graph


DFS


BFS


Connectivity
Definition
Connected
An undirected graph is connected if there is a path from every vertex to every other vertex
Strongly connected
A directed graph with this property is called strongly connected
Weakly connected
If a directed graph is not strongly connected, but the underlying graph(without direction to the arcs)is connected, then the graph is said to be weakly connected.
Minimal Cost Spanning Trees
Spanning Trees
Definition
A spanning tree is any tree that consists solely of edges in G and that includes all the vertices(Contains all the vertices in the graph, but only enough n1 edges to form a tree)
$$ E(G):T(tree\ edges)+N(nontree\ edges)\newline T:set\ of\ edges\ used\ during\ search\newline N:set\ of\ remaining\ edges\newline $$ A spanning tree is a minimal connected subgraph, G’, of G such that V(G’)=V(G) and G’ is connected
Example
Possible spanning trees
DFS and BFS
Either DFS or BFS can be used to create a spanning tree
When DFS is used, the resulting spanning tree is known as a depth first spanning tree
When BFS is used, the resulting spanning tree is known as a breadth first spanning tree
Nontree edge
While adding a nontree edge into any spanning tree, this will create a cycle
Minimal Cost Spanning Trees
Definition
The cost of a spanning tree of a weighted undirected graph is the sum of the costs of the edges in the spanning tree
A Minimal Cost Spanning Tree (MST) is a spanning tree of least cost
Algorithm for Minimal Cost Spanning Tree
$Prim$
$Kruskal$
Prim algorithm
Let Graph $G = {V, E}$, the minimum cost spanning tree be $T={U, T_E }$ and $U=V, T_E\subseteq E\newline$.
$Initially\rightarrow U={u_0 }, T_E=\empty$
Adding edges and vertices to T one at a time

Select the least cost edge $(u,v)$ that $u\in U\ and\ v\notin U$. Adding $v\ to\ U\ and\ (u,v)\ to\ T_E$

It continues, until n1 edges have been selected and U=V


Kruskal algorithm
Build a Minimum cost Spanning Tree (MST) T by adding edges to T one at a time
Select the edges for inclusion in T in nondecreasing order of the cost
An edge is added to T if it does not form a cycle
Since G is connected and has $n > 0$ vertices, exactly n1 edges will be selected


Code


Time Complexity Analysis
$Prim’s\ algorithm:O(n^2)\newline$
Regardless of the number of edges in the graph, it is suitable to find the minimum spanning tree of dense nets
$Kruskal’s\ algorithm:O(e\log e)\ (Merge\ Sort\ for\ edges)\newline$
Regardless of the number of vertices in the graph, it is suitable to find the minimum spanning tree of sparse nets
Application of Graph
Application of Directed Acyclic (Acycline) Graph

Topological Sort

Critical Path
ShortestPath Algorithms
Topological Sort
Definition
An ordering of vertices in a Directed Acyclic Graph, such that if there is a path from $v_i$ to $v_j$ , then $v_j$ appears after $v_i$ in the ordering
Example
An advanced placement course in a college training program
Activity on Vertex(AOV)—Network
Vertices represent activity, and arcs represent directed graphs of priority relations between activities
Notice
Topological ordering is not possible if there is a cycle in the graph
A simple algorithm
steps

Compute the indegree of all vertices from the adjacency information of the graph

Find any vertex with no incoming edges

Print this vertex, and remove it and its edges

Apply this strategy to the rest of the graph
Time Complexity Analysis
$O(n^2)$
code


An improved algorithm
steps

Keep all the unassigned vertices of indegree 0 in a queue.

While queue is not empty
• Remove a vertex in the queue.
• Decrement the indegree of all adjacent vertices.
• If the indegree of an adjacent vertex becomes 0, enqueue the vertex

The topological ordering is the order in which the vertices dequeue
Time Complexity Analysis
$O(n+e)\newline$
code


Critical Path
AOE (Activity on Edge) Network
Vertex: Represents an event or a status
Edge: represents an activity. An edge (v, w) means that event v must be done before w may begin
Weight: Duration time of an activity
~There is only one vertex whose indegree is 0, and only one vertex whose outdegree is 0
~No cycle
~This type of a graph could be (and frequently) used to model projects
Questions
What is the earliest completion time for the project?
$\rightarrow The\ longest\ path\newline$
Which activities can be delayed, and by how long, without affecting the minimum completion time?
$\rightarrow Not\ critical\ activities\newline$
Elements
e(i): earliest start time of $a_i\newline$
l(i): latest start time of $a_i$ (without affecting the minimum completion time)
e(i)=l(i): $a_i$ is a critical activity, all the activities on the critical path are critical activities
ve(j): the earliest occurring time of $v_j\newline$
vl(j): the latest occurring time of $v_j$ (without affecting the minimum completion time)
$$ V_j\stackrel{a_i}{\longrightarrow}V_k\newline $$
If $a_i$ is represented by $<j,k>$, its duration time is $dut(<j,k>)\newline$
then $e(i) = ve(j), l(i) = vl(k)  dut(<j,k>)\newline$
Calculate

$From\ ve(0)=0: ve(j) = max(ve(i) + dut(<i,j>))\newline$

$vl(n1)=ve(n1), from\ the\ last\ one:vl(i) = min(vl(j)  dut(<i,j>))\newline$
Time Complexity Analysis
Suppose there are n events and e activities in AOE
$The\ Time\ Complexity\ of\ whole\ algorithm\ is\ O(n+e)\newline$
Shortest Paths Problems
Input: A graph with weights or costs associated with each edge
Output: The list of edges forming the shortest path
Sample problems:
Find shortest path between two named vertices
Find shortest path from S to all other vertices——SingleSource Shortest Paths
Find shortest path between all pairs of vertices——AllPairs Shortest Paths
Dijkstra idea
step
All vertexes are divided into 2 groups
S : the vertexes that have found the shortest path from $V_0$ to them
VS=T: The vertexes that have not calculated the distances
Adding vertex in T to S in nondecreasing order of distances
The distances from $V_0$ to vertexes in S is not longer than the distances from $V_0$ to any vertexes in T
algorithm
For G(V,E) is expressed in Adjacency Matrix

Initially, $S={v_0}$; An array D[n] to store the distance and D[i] is the shortest distance from $v_0\ to\ v_i$
If exist an edge $(v_0,v_i),D[i] = w(v_0 ,v_i)\newline$ If there is no such edge, then D[i]= +$\infty\newline$

Select the minimal D[j] from VS, then vertex $v_j$ is the destination of the currently shortest path, and D[j] is the shortest distance

Adding $v_j$ to S,and for all vertexes $v_k\in VS\newline$
$if\ D[j]+arcs[j][k]<D[k]\newline then\ D[k]=D[j]+arcs[j][k]\newline$
 Repeat processing (2),(3), until all vertexes are added into S
code


Time Complexity Analysis
For Dijkstra’s Algorithm, the Time complexity is $O(n^2)\newline$
For every vertex $u, v\in V, calculate\ d(u, v)\newline$
Time complexity is $O(n^3)\newline$