1 of 34

TNK104 Applied Optimization

Graph Algorithms, Part 1

Lecture 2

based on the slides provided by Nikolaos Pappas

Tatiana Polishchuk,

Associate Professor,

Linköping University, KTS

https://www.itn.liu.se/~tatpo46/

​

2 of 34

Basic Terminology

2

TNK104 Applied Optimization I

Undirected graphs:

  • Each edge is an unordered pair of two different vertices
  • Two vertices are adjacent if they have an edge
  • Vertex degree: number of edges of the vertex

Example

Degree = 3

Graph G = (V, E)

3 of 34

Basic Terminology (cont’d)

3

TNK104 Applied Optimization I

  • Path:

4 of 34

Basic Terminology (cont’d)

4

TNK104 Applied Optimization I

  • Path: a sequence of vertices such that every two consecutive vertices of the sequence is an edge
  • Simple path:

5 of 34

Basic Terminology (cont’d)

5

TNK104 Applied Optimization I

  • Path: a sequence of vertices such that every two consecutive vertices of the sequence is an edge
  • Simple path: no repetition of any vertex
  • Cycle:

6 of 34

Basic Terminology (cont’d)

6

TNK104 Applied Optimization I

  • Path: a sequence of vertices such that every two consecutive vertices of the sequence is an edge
  • Simple path: no repetition of any vertex
  • Cycle: as the name says …
  • Acyclic: no cycles (= forest for undirected graphs)
  • Connected graph:

7 of 34

Basic Terminology (cont’d)

7

TNK104 Applied Optimization I

  • Path: a sequence of vertices such that every two consecutive vertices of the sequence is an edge
  • Simple path: no repetition of any vertex
  • Cycle: as the name says …
  • Acyclic: no cycles (= forest for undirected graphs)
  • Connected graph: there is at least one path between every vertex pair
  • Complete graph:

8 of 34

Basic Terminology (cont’d)

8

TNK104 Applied Optimization I

  • Path: a sequence of vertices such that every two consecutive vertices of the sequence is an edge
  • Simple path: no repetition of any vertex
  • Cycle: as the name says …
  • Acyclic: no cycles (= forest for undirected graphs)
  • Connected graph: there is at least one path between every vertex pair
  • Complete graph: there is an edge between every vertex pair
  • Subgraph: “part of” a graph

​

9 of 34

Basic Terminology (cont’d)

  • A tree is an undirected graph T such that
    • T is connected
    • T has no cycles

​

  • A forest is an undirected graph without cycles

​

  • The connected components of a forest are trees

9

Tree

Forest

10 of 34

Basic Terminology (cont’d)

10

TNK104 Applied Optimization I

Directed graphs:

  • Each edge (now aka arc) is an ordered pair of two different vertices
  • Vertex degree: need of distinguishing between out-degree and in-degree
  • Path, cycle, and strong connectivity are defined in respect of arc direction

​

Weighted graphs (now let’s put some values on edges/arcs):

  • Each edge has a value specifying its “weight” (length, cost, capacity, etc.)

11 of 34

Graphs: applications

11

Application of Graph Theory in Google Maps (watch youtube video 4 min)

12 of 34

12

13 of 34

Implementing a Graph

  • To program a graph data structure, what information would we need to store?
    • For each vertex?
    • For each edge?

​

13

X

U

V

W

Z

Y

a

c

b

e

d

f

g

h

i

j

14 of 34

Implementing a Graph

  • What kinds of questions would we want to be able to answer (quickly?) about a graph G?
    • Where is vertex v ?
    • Which vertices are adjacent to vertex v ?
    • What edges touch vertex v ?
    • What are the edges of G ?
    • What are the vertices of G ?
    • What is the degree of vertex v ?

14

X

U

V

W

Z

Y

a

c

b

e

d

f

g

h

i

j

15 of 34

Graph Representation

  • There are different ways to represent a graph
  • List of edges
  • For each node – a list of adjacent nodes
  • Adjacency matrix

15

16 of 34

Graph Representation

16

17 of 34

Edge List: Pros and Cons

Graph Representation

  • advantages
    • easy to loop/iterate over all edges

​

  • disadvantages
    • hard to tell if an edge exists from A to B
    • hard to tell how many edges a vertex touches (its degree)

​

17

18 of 34

Graph Representation

18

19 of 34

Graph Representation

19

20 of 34

Adjacency Matrix: Pros and Cons

Graph Representation

  • advantages
    • fast to tell whether edge exists between any two vertices i and j (and to get its weight)

​

  • disadvantages
    • consumes a lot of memory on sparse graphs (ones with few edges)
    • redundant information for undirected graphs

20

21 of 34

21

TNK104 Applied Optimization I

Graph Representation Example

​

Adjacency matrix + Adjacency lists

22 of 34

Traversal

22

TNK104 Applied Optimization I

Depth-first search: visit all vertices

prefer to go “deeper” if possible in visiting the vertices

​

See YT video in the Self-Study Material

What is the time complexity of the algorithm?

23 of 34

Traversal

23

TNK104 Applied Optimization I

Depth-first search: visit all vertices

prefer to go “deeper” if possible in visiting the vertices

​

See YT video in the Self-Study Material

What is the time complexity of the algorithm? O(V)

​

Breadth-first search: See Self-Study Material

24 of 34

24

TNK104 Applied Optimization I

Topological Sort

Given a directed acyclic graph G = (V, E), visit and print the vertices in an order such that each vertex v is printed before any vertex with (v, u) ∈ E

Observation: At least one vertex has in degree = 0 in a directed acyclic graph

A possible solution is v4 , v8 , v3 , v2 , v1 , v5 , v7 , v6

Can you think of some application?

25 of 34

Topological Sort (cont’d)

25

TNK104 Applied Optimization I

Time complexity?

26 of 34

Topological Sort (cont’d)

26

TNK104 Applied Optimization I

Time complexity?

​

Linear O(V+E)

27 of 34

Shortest Path

27

TNK104 Applied Optimization I

  • Find a path from one vertex (aka source) to another vertex (aka destination) with minimum total weight (length, cost…)
  • Find minimum-weight paths from the source to all other vertices
  • Typically defined on directed (and connected) graphs
  • Special case: unweighted shortest path (length = number of edges)

28 of 34

Shortest Path Tree

28

TNK104 Applied Optimization I

Consider the problem of finding shortest paths from v5 to all other vertices for the example graph

By the way: Is the solution always a tree?

Solution:

29 of 34

Solution Representation of the Shortest Path Tree

29

TNK104 Applied Optimization I

30 of 34

Principles of Dijkstra’s Algorithm

Initially: Let the shortest path tree T = (V 0, E0) be ({s}, ∅), where s denotes the source

​

​

30

TNK104 Applied Optimization I

31 of 34

Dijkstra’s Algorithm

31

TNK104 Applied Optimization I

Let’s “decode” by executing it …

Time complexity?

32 of 34

Dijkstra’s Algorithm

32

TNK104 Applied Optimization I

Greedy algorithm (detailed in lect 3)

​

Efficient: complexity O(V^2) (depends on implementation of the priority queue)

​

But! Does not work with negative weights (see examples in the self-study material)

​

Alternative: Bellman-Ford (dynamic programming approach)

​

robust, but less efficient: O(EV)

33 of 34

Shortest Path Variants

33

TNK104 Applied Optimization I

  • Single-destination shortest paths > reverse single-source SP
  • Single-pair shortest paths > Dijkstra’, Bellman Ford’
    • same running time as for single-source SP
  • Shortest path in DAG > uses topsort > O (V+E)

application: critical path (longest path)

  • All-pairs shortest paths > V times single-source SP > O (V^3)
    • can we do better?
    • check Dynamic Programming approach, Floyd-Warshall alg
  • Special case: unweighted shortest path (length = number of edges)

> BFS works well

34 of 34

Self-Study Material

​

Textbook: Section 22 Elementary Graph Algorithms,

Section 24 Single-Source Shortest Paths (*25 All-Pairs SP)

  • Representations of graphs
  • Breadth-first search (BFS)
  • Shortest Paths, Dijkstra’ algorithm, Bellman Ford’
  • Depth-first search (DFS)
  • Topological sort (TS)

​

MIT OCW video lectures:

# 13 https://youtu.be/s-CYnVz-uh4

# 14 https://youtu.be/AfSk24UTFS8

# 17 https://youtu.be/xhG2DyCX3uA

Cycle detection https://youtu.be/tg96sZqhXyU

Youtube videos:

Algorithms https://youtu.be/6hfOvs8pY1k , Graph applications https://youtu.be/_AFqdsqIs-A

Complexity https://youtu.be/zUUkiEllHG0, https://youtu.be/u2DLlNQiPB4

BFS https://youtu.be/xlVX7dXLS64 DFS https://youtu.be/PMMc4VsIacU, https://youtu.be/7fujbpJ0LB4

TopSort https://youtu.be/eL-KzMXSXXI, https://youtu.be/cIBFEhD77b4

Dijkstra’ https://youtu.be/EFg3u_E6eHU, https://youtu.be/pSqmAO-m7Lk

​

Bellman Ford’ https://youtu.be/lyw4FaxrwHg

​

​

​

​

​