13 Graphs

Bilgisayar Mühendisliği Bölümü

DATA STRUCTURES AND ALGORITHMS Lecture Notes 12 Graphs Spring 2008

GIT – Computer Engineering Department

Chapter Outline







Graph Terminology The Graph ADT and Edge Class Implementing the Graph ADT Traversals of Graphs Application of Graph Traversals Algorithms Using Weighted Graphs

GIT – Computer Engineering Department

2

What is a Graph
A graph is a set of vertices and a set of edges that connect pairs of distinct vertices.
Mathematically, a graph is a tuple G = (V, E) where – V : set of vertices /nodes – E : set of edges / links , E ⊂ V×V • each edge is a pair (v,w ), where v,w Є V

– vertex w is adjacent to v iff (v,w) Є E


A graph may be directed or undirected. – If the pairs, (v,w ) are ordered, then the graph is directed • directed graphs are sometimes refered as digraphs

– In an undirected graph, (u, v) ∈ E iff (v, u) ∈ E • the edges of an undirected graph are unordered pairs; (u, v) and (v, u) are the same edge.

GIT – Computer Engineering Department

3

Example
Visually we represent the vertices as points (or labeled circles) and the edges as lines joining the vertices
Ex: An undirected graph G = (V, E) where V = {A, B, C, D, E} E = {{A, B}, {A, D}, {C, E}, {D, E}}

D

GIT – Computer Engineering Department

A

B

E

C

4

A Directed Graph
Ex: A directed graph G = (V, E) where V = {A, B, C, D, E} E = {(A, B), (B, A), (B, E), (D, A), (E, A), (E, D), (E, C)}

D

A

B

E

C

The numbering of the vertices, and their physical arrangement are not important.

GIT – Computer Engineering Department

5

Weighted Graph Ann Arbor Chicago

(Not To Scale)

50

260 40 148

180

60

Fort Wayne

Detroit Toledo 120

155

120

Cleveland 130 Pittsburgh 320 150 180

Philadelphia

180 Indianapolis

Columbus

GIT – Computer Engineering Department

6

Path in a Graph
A path is a sequence of vertices in which each successive vertex is adjacent to its predecessor – w1, w2, …, wN where (wi, wi+1) Є E for 1≤i

The length of a path is the number of edges on the path, which is equal to N-1 – if path contains no edges, length is 0


A simple path is a path such that all vertices are distinct – except the first and last, they could be same


A cycle is a simple path in which the first and final vertices are the same. – A simple path with length ≥ 1 where w1 = wN – Cycle is simple, if the path is simple – In an undirected graph edges should be distinct for simple cycle


A directed graph is acyclic if it has no cycles – A directed acyclic graph is refered to DAG GIT – Computer Engineering Department

7

Example of a Path Ann Arbor Chicago

(Not To Scale)

50

260 40 148

180

60

Fort Wayne

Detroit Toledo 120

155

120

Cleveland 130 Pittsburgh 320 150 180

Philadelphia

180 Indianapolis

Columbus

GIT – Computer Engineering Department

8

Example of a Cycle Ann Arbor Chicago

(Not To Scale)

50

260 40 148

180

60

Fort Wayne

Detroit Toledo 120

155

120

Cleveland 130 Pittsburgh 320 150 180

Philadelphia

180 Indianapolis

Columbus

GIT – Computer Engineering Department

9

Connected Graph
An undirected graph is connected if there is a path between each pair of vertices
A directed graph is strongly connected if there is a directed path between each pair of vertices
A directed graph is weakly connected if the underlying undirected graph is connected – undirected path between each pair of vertices


A complete graph is a graph in which there is an edge between every pair of vertices
A graph that is not connected, consists of connected components

GIT – Computer Engineering Department

10

Disconnected Graph 0

7

8

9

10

11

12

6 1

2

3 4 5

GIT – Computer Engineering Department

11

Relationship Between Graphs and Trees
A tree is a special case of a graph.
Any connected graph which does not contain cycles can be considered a tree.
Any node can be chosen to be the root.

GIT – Computer Engineering Department

12

Application of Graphs
Determine network connectivity.
Schedule courses in accordance with prerequisite requirements.
Finding the shortest (or least cost) path. – Network routing – Travel planning

GIT – Computer Engineering Department

13

Example: Airport system
Each airport is a vertex
Two vertices are connected by an egde if there is a nonstop flight from the airports that are represented by the vertices
Such a graph is directed
The edge could have a weight, representing time, distance or cost of flight. – It might have longer or cost more to fly in different directions


Make sure that the airport system is strongly connected – It is always possible to fly from any airport to any other

GIT – Computer Engineering Department

14

Example: Traffic Flow 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

GIT – Computer Engineering Department

15

Abstract Representation of a Graph
We will consider the vertices to be the integers from 0 to |V|-1.
Operations on a graph: – Create a graph of n vertices. No edges. – Insert an edge – Remove an edge – Query the existence of an edge – Iterate over the vertices adjacent to a given vertex

GIT – Computer Engineering Department

16

Design of the Graph class Function

Behavior

int get_num_v() const bool is_directed() const virtual void insert(const Edge&) = 0 virtual bool is_edge(int source, int dest) const = 0 virtual Edge get_edge(int source, int dest) const = 0 virtual iterator begin(int source) const = 0 virtual iterator end(int source) const = 0 void load_edges_from_file(std::istream&) static Graph* create_graph(std::istream&, bool, const std::string&)

Return the number of vertices. Return true if this is a directed graph. Insert a new edge into the graph. Determine whether there is an edge between two vertices. Return the edge between two vertices.

GIT – Computer Engineering Department

Return an iterator to the first edge adjacent to the specified vertex. Return an iterator one past the last edge adjacent to the specified vertex Load the edges of a graph from the data in an input file. Factory function to create a graph and load the data from an input file.

17

Abstract Graph in C++ /** Abstract class to specify a Graph ADT. A graph is a set of vertices and a set of edges. Vertices are represented by integers from 0 to n - 1. Edges are ordered pairs of vertices. */ class Graph { public: // Forward declaration of iterator class class iterator; // Constructor /** Construct a graph @param n The number of vertices @param d True if this is a directed graph */ Graph(int n, bool d) : num_v(n), directed(d) {} // Virtual Destructor virtual ~Graph() {}

GIT – Computer Engineering Department

18

Graph.h (2) // Accessors int get_num_v() const {return num_v;} bool is_directed() const {return directed;} virtual void insert(const Edge& edge) = 0; virtual bool is_edge(int source, int dest) const = 0; virtual Edge get_edge(int source, int dest) const = 0; virtual iterator begin(int source) const = 0; virtual iterator end(int source) const = 0; void load_edges_from_file(std::istream& in); static Graph* create_graph(std::istream& in, bool is_directed, const std::string& type);

GIT – Computer Engineering Department

19

Graph.h (3) // Definition of nested classes iter_impl and iterator protected: // Data fields /** The number of vertices */ int num_v; /** Flag to indicate whether this is a directed graph */ bool directed; }; // End class Graph

GIT – Computer Engineering Department

20

The Edge Class Data Field

Attribute

int dest int source double weight

The destination vertex The source vertex The weight.

Constructor

Behavior

Edge(int s, int d, double w = 1.0)

Constructs an Edge from s to d. Sets the weight to 1.0 if w is not specified. Constructs a dummy edge with source and destination set to -1 and weight to infinity. Copy constructor.

Edge()

Edge(const Edge&)

GIT – Computer Engineering Department

21

The Edge Class (2) Function

Behavior

bool operator==(const Edge& other)

Compare two Edges for equality. Edges are equal if their source and destination are equal. The weight is not considered. The negation of the equality operator. Returns the destination vertex. Returns the source vertex. Returns the weight. Returns a string representation of the edge. Overloaded ostream insertion operator.

bool operator!=(const Edge& other) int get_dest() const int get_source() const double get_weight() const string to_string() const ostream& operator<<(ostream&, const Edge&)

GIT – Computer Engineering Department

22

Concrete Representation of a Graph
Two methods of representing a graph are popular: – Adjacency Matrix – Adjacency List

GIT – Computer Engineering Department

23

Adjacency Matrix Representation
Use a two dimensional |V| × |V| matrix to represent a graph – For each edge (u,v) Є E we set A [u][v] = 1 – A [u][v] = 0 , otherwise


If the edge has a weight we set A[u][v] = weight we can use -∞ / ∞ to indicate nonexistent edges
Space requirement = θ(|V|2)
An adjacency matrix is an appropriate representation if the graph is dense: |E| = θ (|V|2) – is it true in most applications ?

GIT – Computer Engineering Department

24

Adjacency Matrix

0

1 0 0

2 4

3

GIT – Computer Engineering Department

1

1

2

1.0

4 1.0

1.0 1.0 1.0

1.0

2

1.0

3

1.0 1.0

4

3

1.0 1.0

1.0 1.0 1.0

25

Adjacency Matrix (directed graph)

0

1

0

2 0

1 1.0

2

3

1.0 1.0 1.0

2

3

4

GIT – Computer Engineering Department

5

4 5

5

1.0

1 3

4

1.0 1.0 1.0

26

Adjacency List Representation
A vector (array) of lists – one for each vertex. – Each list has the adjacent vertices


If the graph is not dense (is sparse) a better solution is adjacency list representation
The space requirement is O(|E|+|V|)

GIT – Computer Engineering Department

27

Adjacency List (Directed Graph)

GIT – Computer Engineering Department

28

Adjacency List Representation

GIT – Computer Engineering Department

29

Overview of Class Hierarchy

GIT – Computer Engineering Department

30

The create_graph function Graph* Graph::create_graph(istream& in, bool d, const std::string& type) { int n; in >> n; in.ignore(numeric_limits::max(), '\n'); // Skip rest of line Graph* return_value = NULL; if (type == "Matrix") return_value = new Matrix_Graph(n, d); else if (type == "List") return_value = new List_Graph(n, d); else throw std::invalid_argument("Unrecognized Graph Type"); return_value->load_edges_from_file(in); return return_value; }

GIT – Computer Engineering Department

31

The iterator class class iterator { public: Edge operator*() { return ptr_to_impl->operator*(); } iterator& operator++() { ++(*ptr_to_impl); return *this; } iterator operator++(int) { iterator temp(*this); ++(*ptr_to_impl); return temp;} bool operator==(const iterator& other) const { return *ptr_to_impl == *other.ptr_to_impl; } bool operator!=(const iterator& other) const { return !((*this) == other); } ~iterator() {delete ptr_to_impl;} iterator(const iterator& other) : ptr_to_impl(other.ptr_to_impl->clone()) {} iterator(iter_impl* p_impl) : ptr_to_impl(p_impl) {} private: /** Pointer to the implementation */ iter_impl* ptr_to_impl; }; // End iterator

GIT – Computer Engineering Department

32

The iter_impl class class iter_impl { public: virtual Edge operator*() = 0; virtual iter_impl& operator++() = 0; virtual bool operator==(const iter_impl&) const = 0; virtual iter_impl* clone() = 0; virtual ~iter_impl() {} };

GIT – Computer Engineering Department

33

Design of the List_Graph class Data Field

Attribute

vector<list<Edge> > edges

A vector of lists to contain the edges that originate with each vertex.

Constructor

Purpose

List_Graph(int n, bool d)

Constructs a graph with the specified number of vertices and directionality.

Public Member Functions

Behavior

iterator begin(int source) const

Returns an iterator to the edges that originate from a given vertex. Returns an iterator one past the last edge that originates from a given vertex. Gets the edge between two vertices.

iterator end(int source) const Edge get_edge(int source, int dest) const void insert(const Edge& e) bool is_edge(int source, int dest) const

GIT – Computer Engineering Department

Inserts a new edge into the graph Determines whether an edge exists from vertex source to vertex dest.

34

Design of the Graph class Function

Behavior

int get_num_v() const bool is_directed() const virtual void insert(const Edge&) = 0 virtual bool is_edge(int source, int dest) const = 0 virtual Edge get_edge(int source, int dest) const = 0 virtual iterator begin(int source) const = 0 virtual iterator end(int source) const = 0 void load_edges_from_file(std::istream&) static Graph* create_graph(std::istream&, bool, const std::string&)

Return the number of vertices. Return true if this is a directed graph. Insert a new edge into the graph. Determine whether there is an edge between two vertices. Return the edge between two vertices.

GIT – Computer Engineering Department

Return an iterator to the first edge adjacent to the specified vertex. Return an iterator one past the last edge adjacent to the specified vertex Load the edges of a graph from the data in an input file. Factory function to create a graph and load the data from an input file.

35

The is_edge and get_edge functions bool List_Graph::is_edge(int source, int dest) const { list<Edge>::const_iterator itr = find(edges[source].begin(), edges[source].end(), Edge(source, dest)); return itr != edges[source].end(); } Edge List_Graph::get_edge(int source, int dest) const { list<Edge>::const_iterator itr = find(edges[source].begin(), edges[source].end(), Edge(source, dest)); if (itr != edges[source].end()) return *itr; else return Edge(source, dest, numeric_limits<double>::infinity()); }

GIT – Computer Engineering Department

36

The insert function void List_Graph::insert(const Edge& edge) { edges[edge.get_source()].push_back(edge); if (!is_directed()) { edges[edge.get_dest()].push_back(Edge(edge.get_dest(), edge.get_source(), edge.get_weight())); } }

GIT – Computer Engineering Department

37

The begin and end functions Graph::iterator List_Graph::begin(int source) const { return Graph::iterator(new iter_impl(edges[source].begin())); } Graph::iterator List_Graph::end(int source) const { return Graph::iterator(new iter_impl(edges[source].end())); }

GIT – Computer Engineering Department

38

The List_Graph::iter_impl class class iter_impl : public Graph::iter_impl { private: // Constructor iter_impl(std::list<Edge>::const_iterator start) : current(start) {} public: Edge operator*() { return *current; } Graph::iter_impl& operator++() { ++current; return *this; } bool operator==(const Graph::iter_impl& other) const { const iter_impl* ptr_other = dynamic_cast(&other); if (ptr_other == NULL) return false; return current == ptr_other->current; } Graph::iter_impl* clone() { return new iter_impl(current); } GIT – Computer Engineering Department

39

The List_Graph::iter_impl class (2) private: // Data fields /** Iterator to the list of edges */ std::list<Edge>::const_iterator current; friend class List_Graph; }; // End iter_impl

GIT – Computer Engineering Department

40

Performance
Two implementations – Adjacency list – Adjacency matrix


Which one is better? – In terms of storage – In terms of time

GIT – Computer Engineering Department

41

Performance
Performance in terms of storage – Space requirement = θ(|V|2) in adjacency matrix – Space requirement = O(|E|+|V|) in adjacency list – Which one is better for sparse graphs? – What about the constant hidden in asymptotic notation?

GIT – Computer Engineering Department

42

Performance
Performance in terms of time – Depends on the algorithm – Ex: consider the following code for each vertex u in the graph for each vertex v adjacent to u do something with edge (u,v)

GIT – Computer Engineering Department

43

Performance
For adjacency list – An iteration over all vertices adjacent to a given vertex is O(|Ev|) – An algorithm that iterates over all of the edges by iterating over the vertices is O(|E|)


For adjacency matrix – Need to go over all vertices for each vertex u – θ(|V|2)

GIT – Computer Engineering Department

44

Performance – Ex: consider the following code for each vertex u in some subset of the vertices for each vertex v in some subset of the vertices if (u,v) is an edge do something with the edge

GIT – Computer Engineering Department

45

Observation About Adjacency List Representation


For adjacency list – The operation is_edge(int u, int v)

is O(|Ev|) where |Ev| is the number of edges originating from v – The total run time is O(|V| |E| )


For adjacency matrix – Same operation is done in constant time – The total run time is O(|V|2)

GIT – Computer Engineering Department

46

Which to Use?
Generally |E| < < |V|2 – i.e. the adjacency matrix is sparse.


Thus, for most applications, the adjacency list is preferred.
There are some algorithms, however, where the adjacency matrix is preferred.

GIT – Computer Engineering Department

47

Breadth First Search
Starting at a source vertex
Systematically explore the edges to “discover” every vertex reachable from s.
Produces a “breadth-first tree” – Root of s – Contains all vertices reachable from s – Path from s to v is the shortest path

GIT – Computer Engineering Department

48

Algorithm 1. Take a start vertex, mark it identified (color it gray), and place it into a queue. 2. While the queue is not empty 1. Take a vertex, u, out of the queue (Begin visiting u) 2. For all vertices v, adjacent to u, 1. If v has not been identified or visited 1. Mark it identified (color it gray) 2. Place it into the queue 3. Add edge u, v to the Breadth First Search Tree 3. We are now done visiting u (color it black)

GIT – Computer Engineering Department

49

Example 5 0 3

4 1

2 9 GIT – Computer Engineering Department

6 7

8 50

Example

GIT – Computer Engineering Department

51

Trace of Breadth First Search

Vertex Being Visited Queue Contents after Visit Visit Sequence 0 1 3 2 4 6 7 8 9 5

13 32467 2467 46789 67895 7895 895 95 5 empty

GIT – Computer Engineering Department

0 01 013 0132 01324 013246 0132467 01324678 013246789 0132467895

52

Breadth-First Search Tree vector parent [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

GIT – Computer Engineering Department

-1 0 1 0 1 4 1 1 2 2

53

Application of BFS
A Breadth First Search finds the shortest path from the start vertex to all other vertices based on number of edges.
We can use a Breadth First Search to find the shortest path through a maze.
This may be a more efficient solution than that found by a backtracking algorithm.

GIT – Computer Engineering Department

54

Recursive Solution to a Maze

GIT – Computer Engineering Department

55

Maze as a Graph 0 1

2

3 8 5

4

6

7

9

11 10

12

GIT – Computer Engineering Department

56

Breadth First Search Tree 0

1

2

4

8

12

7

11

GIT – Computer Engineering Department

6

5

9

3

10

57

Maze Solution 0 2

1

3 8 4

5

6

7

9

11 10

12 GIT – Computer Engineering Department

58

Implementing Breadth First Search
The breadth_first_search function will create the Breadth First Search tree by returning a vector that gives the parent of each vertex in the tree.
Generally we are interested in the path from the starting vertex to a given target vertex. – Using this array we can construct this path by entering the vertices into a stack and reversing their order.

GIT – Computer Engineering Department

59

Code for Breadth First Search vector breadth_first_search(const Graph& graph, int start) { int num_v = graph.get_num_v(); queue the_queue; vector parent(num_v, -1); vector identified(num_v, false); identified[start] = true; the_queue.push(start); /* While the queue is not empty */ while (!the_queue.empty()) { /* Take a vertex, current, out of the queue (Begin visiting current).*/ int current = the_queue.front(); the_queue.pop();

GIT – Computer Engineering Department

60

Code for Breadth First Search (2) /* For all vertices, neighbor, adjacent to current */ Graph::iterator itr = graph.begin(current); while (itr != graph.end(current)) { Edge edge = *itr; int neighbor = edge.get_dest(); /* If neighbor has not been identified */ if (!identified[neighbor]) { /* Mark it identified */ identified[neighbor] = true; /* Place it into the queue */ the_queue.push(neighbor); /* Insert the edge (current, neighbor) into the tree */ parent[neighbor] = current; } ++itr; } // Finished visiting current. } return parent;

GIT – Computer Engineering Department

61

Depth First Search
Start at some vertex
Follow a simple path discovering new vertices until you cannot find a new vertex.
Back-up until you can start finding new vertices.

GIT – Computer Engineering Department

62

Algorithm for DFS 1. Start at vertex u. Mark it visited (color gray) and set its discovery time. 2. For each vertex v adjacent to u 1. If v has not been visited 1. Insert u, v into DFS tree 2. Recursively apply this algorithm starting at v 3. Mark u finished (color it black) and set its finish time.
Note: for a Directed graph, a DFS may produce multiple trees – this is called a DFS forest

GIT – Computer Engineering Department

63

DFS Example 0

1

3 GIT – Computer Engineering Department

2

4

5

6 64

DFS Example

GIT – Computer Engineering Department

65

Trace of Depth-First Search Operation Visit 0 Visit 1 Visit 3 Visit 4 Finish 4 Finish 3 Finish 1 Visit 2 Visit 5 Visit 6 Finish 6 Finish 5 Finish 2 Finish 0

Adjacent Vertices 1234 034 014 013

Discovery Order 0 01 013 0134

Finish Order

4 43 431 056 26 25

GIT – Computer Engineering Department

01342 013425 0134256 4316 53165 531652 5316520

66

Depth-First Search Tree

GIT – Computer Engineering Department

67

Depth First Search Starter Function void depth_first_search(const Graph& graph, int start, vector& parent, vector& discovery_order, vector& finish_order) { int num_v = graph.get_num_v(); parent.clear(); parent.resize(num_v, -1); discovery_order.clear(); discovery_order.resize(num_v, -1); finish_order.clear(); finish_order.resize(num_v, -1); vector visited(num_v, false); int discovery_index = 0; int finish_index = 0; for (int i = 0; i < num_v; i++) { if (!visited[i]) { depth_first_search(graph, i, parent, discovery_order, finish_order, visited, discovery_index, finish_index); } } } GIT – Computer Engineering Department

68

Depth_First_Search Recursive Function void depth_first_search(const Graph& graph, int current, vector& parent, vector& discovery_order, vector& finish_order, vector& visited, int& discovery_index, int& finish_index) { visited[current] = true; discovery_order[discovery_index++] = current; /* For each vertex adjacent to the current vertex. */ for (Graph::iterator itr = graph.begin(current); itr != graph.end(current); ++itr) { int neighbor = (*itr).get_dest(); // if neighbor has not been visited if (!visited[neighbor]) { /* Insert (current, neighbor) into the depth- first search tree */ parent[neighbor] = current; // Recursively apply the algorithm starting at neighbor. depth_first_search(graph, neighbor, parent, discovery_order, finish_order, visited, discovery_index, finish_index); } } // Mark current finished finish_order[finish_index++] = current; } GIT – Computer Engineering Department

69

Application of DFS
A topological sort is an ordering of the vertices such that if (u, v) is an edge in the graph, then v does not appear before u in the ordering.
A Depth First Search can be used to determine a topological sort of a Directed Acyclic Graph (DAG)
An application of this would be to determine an ordering of courses that is consistent with the prerequisite requirements GIT – Computer Engineering Department

70

CIS Prerequisites

GIT – Computer Engineering Department

71

Topological Sort Algorithm
Observation: If there is an edge from u to v, then in a DFS u will have a finish time later than v.
Perform a DFS and record the finish times.
Order the vertices by decreasing finish time.

GIT – Computer Engineering Department

72

Shortest Path Problem
Shortest Path Problem :

Given as input a graph, G=(V,E), find the shortest path from vertex v to vertex w in G
Input is a weighted graph : associated with each edge (vi ,vj) is a cost ci,j to traverse the edge.
Cost of a path v1 v2 … vN (weighted path lenght ) is N −1

∑c

i ,i +1

i =1


Remember, unweighted path lenght is merely the number of edges on the path, N-1 GIT – Computer Engineering Department

73

Example - Directed Weighted Graph 1

100

10

2

5

50

30

3 GIT – Computer Engineering Department

20

60

10

4 74

Another Weighted Graph

GIT – Computer Engineering Department

75

Shortest Path Problem
Negative edges can cause problems!
Path from v5 to v4 has cost 1 but a shorter path exists by following the loop v5, v4, v2, v5, v4, has a cost -5
Shortest path is undefined if there is a negative cost cycle

GIT – Computer Engineering Department

76

Shortest Path Problem Currently there are no algorithms in which finding the path from s to one vertex is any faster (by more than a constant factor) than finding the paths from s to all other vertices

GIT – Computer Engineering Department

77

Finding the Shortest Paths Single Source Shortest Paths Problem :

Given as input – a graph, G=(V,E) and – a distinguished vertex, s

Find – the shortest paths from s to every other vertex in G

GIT – Computer Engineering Department

78

Finding the Shortest Paths
The famous computer scientist Edsger W. Dijkstra developed an algorithm to solve this problem.
This algorithm is an example of a greedy algorithm. – A greedy algorithm is one that attempts to find the locally optimal solution at each step

GIT – Computer Engineering Department

79

Dijkstra’s Algorithm
A tentative distance dv is kept for each vertex
This distance turns out to be the shortest path length from s to v using only known vertices as intermediates
We record pv, which is the last vertex to cause a change to dv
Dijkstra’s algorithm proceeds in stages
At each stage – select a vertex v, which has the smallest dv among all the unknown vertices – declare that shortest path from s to v is known – update the values of dw for each vertex w adjacent to v GIT – Computer Engineering Department

80

Dijkstra’s Algorithm 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.

Initialize S with the start vertex, s, and V–S with the remaining vertices. for all v in V – S Set p[v] to s if there is an edge (s, v) Set d[v] to w(s, v) else Set d[v] to ∞ while V – S is not empty for all u in V – S, find the smallest d[u] Remove u from V – S and add it to S for all v adjacent to u in V – S if d[u] + w(u, v) is < d[v] Set d[v] to d[u] + w(u, v) Set p[v] to u.

GIT – Computer Engineering Department

81

Dijkstra’s Algorithm

Example :
Assume that start node s is v1
First vertex selected is v1 – with path length 0


This vertex is marked known

GIT – Computer Engineering Department


Initial configuration of vectors in Dijkstra’s Algorithm

82

Stages of Dijkstra’s Algorithm

GIT – Computer Engineering Department

83

Stages of Dijkstra’s Algorithm

GIT – Computer Engineering Department

84

Stages of Dijkstra’s Algorithm

GIT – Computer Engineering Department

85

Stages of Dijkstra’s Algorithm

GIT – Computer Engineering Department

86

Stages of Dijkstra’s Algorithm

GIT – Computer Engineering Department

87

Stages of Dijkstra’s Algorithm

GIT – Computer Engineering Department

88

Analysis of Dijkstra’s Algorithm





Step 1 requires |V| steps. The loop at Step 2 will be executed |V| – 1 times The loop at Step 7 will be executed |V| – 1 times Within the loop at Step 7 – Steps 8 and 9 will search |V – S| items – Thus Step 7 is |V| -1 + |V| - 2 + … 1 = O(|V|2)

GIT – Computer Engineering Department

89

Improving Implementation of Dijkstra’s Algorithm
We use a tripple to contain d[u], u, p[u] and use d[u] as the key for comparison.
We can then place these triples into a priority queue and adapt the breadth-first-search algorithm.

GIT – Computer Engineering Department

90

Improved Dijkstra’s Algorithm 1. 2. 3. 4. 5. 6. 7.

Take the start vertex and place the triple (0, s, -1) into the priority queue. While the priority queue is not empty Take the triple with the smallest d[u] out of the queue. If u has not been visited Mark it visited and place (p[u], u) into the result. For all vertices, v, adjacent to u Compute d[v] = d[u] + w(u, v) and place (d[v], v, u) into the priority queue.

GIT – Computer Engineering Department

91

Analysis of revised algorithm
Assume that all edges get entered into the priority queue.
Thus the while loop is executed |E| times.
If we use a heap for the priority queue, each insert and removal is log |E|.
Thus we have O(|E| log |E|).

GIT – Computer Engineering Department

92

Minimum Spanning Tree
Let G = (V, E) be an un-directed weighted graph.
Wish to find an acyclic subset T ⊆ E such that w(T) = ∑(u,v) ∈T w(u,v)

is the minimum.
This is the minimum spanning tree.
A minimum spanning tree of an undirected graph G is a tree formed from graph edges that connects all the vertices of G at lowest total cost
A minimum spanning tree exists iff G is connected

GIT – Computer Engineering Department

93

Minimum Spanning Tree Second graph is the minimum spanning tree of first Number of edges in minimum spanning tree is |V| -1 Minimum spanning tree is a tree because it is acyclic and connected; it is spanning because it covers every vertex GIT – Computer Engineering Department

94

Prim’s Algorithm
One way to compute a minimum spanning tree is to grow the tree in successive stages.
In each stage – one node is picked as the root – we add an edge and thus an associated vertex to the tree


At any point of the algorithm, we have a set of vertices that have already been included in the tree
The algorithm then finds, at each stage, a new vertex to add to the tree by choosing the edge (u,v) – Cost of (u,v) is the smallest among all edges where u is in tree and v is not GIT – Computer Engineering Department

95

Prim’s Algorithm

GIT – Computer Engineering Department

96

Prim’s Algorithm
Prim’s algorithm is identical to Dijkstra’s algorithm for shortest path
We keep values – dv  weight of shortest edge connecting v to a known vertex – pv  last vertex to cause a change in dv

GIT – Computer Engineering Department

97

Prim’s Algorithm 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.

Initialize S with the start vertex, s, and V–S with the remaining vertices for all v in V – S if there is an edge (s, v) Set d[v] to w(s, v) Set p[v] to s else Set d[v] to ∞ Set p[v] to NULL while V – S is not empty for all u in V – S, find the smallest d[u] Remove u from V – S and add it to S Insert the edge (u, p[u]) into the spanning tree. for all v adjacent to u in V – S if w(u, v) < d[v] Set d[v] to w(u, v) Set p[v] to u.

GIT – Computer Engineering Department

98

Example

GIT – Computer Engineering Department

99

Building the MST

GIT – Computer Engineering Department

100

Analysis of Prim’s Algorithm
The outer loop is executed n-1 times, each time adding an edge
There are two inner loops: – one to find the minimum item in the remaining list, – and the other to update the distances from nodes inside the set S to nodes outside the set S.

GIT – Computer Engineering Department

101

Analysis of Prim’s Algorithm
These loops also run |V| times. – Thus the implementation is O(|V|2) assuming that the adjacency matrix representation of the graph is used.


If we could improve upon the find minimum and update distance operations to say log |V|, this could be improved to O(|E|log|V|).
Computer science researchers have developed advanced priority queue implementations that give O(|E| + |V| log |V|) or better performance

GIT – Computer Engineering Department

102