Data Structure

Siper

DSAlg-Graph.pptx

Home >Computer Science homework help >Data Structure

MCIS 6214 - Data Structure and Algorithms Graph

MCIS 2018

Program Design Including Data Structures, Seventh Edition

Objectives

In this chapter, you will:

Learn about graphs

Become familiar with the basic terminology of graph theory

Discover how to represent graphs in computer memory

Explore graphs as ADTs

Examine and implement various graph traversal algorithms

Learn how to implement the shortest path algorithm

Examine and implement the minimal spanning tree algorithm

Program Design Including Data Structures, Seventh Edition

Introduction

Königsberg bridge problem:

The river Pregel flows around the island Kneiphof and then divides into two branches

Program Design Including Data Structures, Seventh Edition

Introduction (cont’d.)

Starting at one land area, can you cross all bridges exactly once and return to the start?

In 1736, Euler represented the problem as a graph and answered the question: No

Program Design Including Data Structures, Seventh Edition

Introduction (cont’d.)

Over the past 200 years, graph theory has been applied to a variety of problems, including:

Model electrical circuits, chemical compounds, highway maps, etc.

Analysis of electrical circuits, finding the shortest route, project planning, linguistics, genetics, social science, etc.

Program Design Including Data Structures, Seventh Edition

Graph Definitions and Notations

a  X: a is an element of the set X

Subset (Y  X): every element of Y is also an element of X

Intersection (A  B): contains all the elements in A and B

A  B = x | x  A and x  B

Union (A  B): set of all the elements that are in A or in B

A  B = x | x  A or x  B

Graph Definitions and Notations (cont’d.)

A  B: set of all the ordered pairs of elements of A and B

A  B = (a, b) | a  A, b  B

Graph G: G = (V, E)

V is a finite nonempty set of vertices of G

E  V  V

Elements in E are the pairs of elements of V

E is called set of edges

Program Design Including Data Structures, Seventh Edition

Graph Definitions and Notations (cont’d.)

Directed graph or digraph: elements of E(G) are ordered pairs

Undirected graph: elements not ordered pairs

If (u, v) is an edge in a directed graph

Origin: u

Destination: v

Subgraph H of G: if V(H)  V(G) and E(H)  E(G)

Every vertex and edge of V is in G

Program Design Including Data Structures, Seventh Edition

https://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf

In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

Graph Definitions and Notations (cont’d.)

Program Design Including Data Structures, Seventh Edition

Graph Definitions and Notations (cont’d.)

Program Design Including Data Structures, Seventh Edition

Graph Definitions and Notations (cont’d.)

Adjacent: there is an edge from one vertex to the other; i.e., (u, v)  E(G)

Incident: if edge e = (u, v) then e is incident on u and v

Loop: edge incident on a single vertex

Parallel edges: associated with the same pair of vertices

Simple graph: has no loops or parallel edges

Program Design Including Data Structures, Seventh Edition

Graph Definitions and Notations (cont’d.)

Path: sequence of vertices u1, u2, ..., un such that u = u1, un = v, and (ui, ui + 1) is an edge for all i = 1, 2, ..., n − 1

Connected vertices: there is a path from u to v

Simple path: path in which all vertices, except possibly the first and last, are distinct

Cycle: simple path in which the first and last vertices are the same

Program Design Including Data Structures, Seventh Edition

Graph Definitions and Notations (cont’d.)

Connected: path exists from any vertex to any other vertex

Component: maximal subset of connected vertices

In a connected graph G, if there is an edge from u to v, i.e., (u, v)  E(G), then u is adjacent to v and v is adjacent from u

Strongly connected: any two vertices in G are connected

Program Design Including Data Structures, Seventh Edition

Graph Representation

To write programs that process and manipulate graphs

Must store graphs in computer memory

A graph can be represented in several ways:

Adjacency matrices

Adjacency lists

Program Design Including Data Structures, Seventh Edition

Adjacency Matrix

G: graph with n vertices (n  0)

V(G) = v1, v2, ..., vn

Adjacency matrix (AG of G): two-dimensional n  n matrix such that:

Adjacency matrix of an undirected graph is symmetric

Program Design Including Data Structures, Seventh Edition

Adjacency Lists

G: graph with n vertices (n  0)

V(G) = v1, v2, ..., vn

Linked list corresponding to each vertex, v,

Each node of linked list contains the vertex, u, such that (u,v)  E(G)

Each node has two components, such as vertex and link

Program Design Including Data Structures, Seventh Edition

Adjacency Lists (cont’d.)

Program Design Including Data Structures, Seventh Edition

Operations on Graphs

Operations commonly performed on a graph:

Create the graph

Clear the graph

Makes the graph empty

Determine whether the graph is empty

Traverse the graph

Print the graph

Program Design Including Data Structures, Seventh Edition

Operations on Graphs (cont’d.)

The adjacency list (linked list) representation:

For each vertex, v, vertices adjacent to v are stored in linked list associated with v

In a directed graph, vertices adjacent to v are called immediate successors

To manage data in a linked list, use class unorderedLinkedList

Program Design Including Data Structures, Seventh Edition

Graphs as ADTs

We implement graphs as an abstract data type (ADT), including functions to:

Create/clear the graph

Print the graph

Traverse the graph

Determine the graph’s size

Program Design Including Data Structures, Seventh Edition

Graph Traversals

Traversing a graph is similar to traversing a binary tree, except that:

A graph might have cycles

Might not be able to traverse the entire graph from a single vertex

Most common graph traversal algorithms:

Depth first traversal

Breadth first traversal

Program Design Including Data Structures, Seventh Edition

Depth First Traversal

Depth first traversal at a given node, v:

Mark node v as visited

Visit the node

for each vertex u adjacent to v

if u is not visited

start the depth first traversal at u

This is a recursive algorithm

Program Design Including Data Structures, Seventh Edition

Depth First Traversal (cont’d.)

Depth-first ordering of vertices:

0, 1, 4, 3, 2, 5, 7, 8, 6, 9

Breadth-first ordering of vertices:

0, 1, 3, 4, 2, 5, 7, 8, 6, 9

Program Design Including Data Structures, Seventh Edition

Breadth First Traversal

Breadth first traversal of a graph

Similar to traversing a binary tree level by level

Nodes at each level are visited from left to right

Starting at the first vertex, the graph is traversed as much as possible

Then go to next vertex not yet visited

Use a queue to implement the breadth first search algorithm

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm

Weight of the edge: nonnegative real number assigned to the edges connecting two vertices

Weighted graph: every edge has a nonnegative weight

Weight of the path P

Sum of the weights of all edges on the path P

Also called the weight of v from u via P

Source: starting vertex in the path

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Shortest path: path with the smallest weight

Shortest path algorithm

Called the greedy algorithm, developed by Dijkstra

G: graph with n vertices, where n ≥ 0

V(G) = {v1, v2, ..., vn}

W: two-dimensional n × n matrix

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Shortest path algorithm:

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Graph after first iteration of Steps 3, 4, and 5

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Graph after second iteration of Steps 3, 4, and 5

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Graph after third iteration of Steps 3, 4, and 5

Program Design Including Data Structures, Seventh Edition

Shortest Path Algorithm (cont’d.)

Graph after fourth iteration of Steps 3, 4, and 5

Program Design Including Data Structures, Seventh Edition

Minimal Spanning Tree

Company needs to shut down a maximum number of connections and still be able to fly from one city to another

Program Design Including Data Structures, Seventh Edition

Minimal Spanning Tree (cont’d.)

Program Design Including Data Structures, Seventh Edition

Minimal Spanning Tree (cont’d.)

(Free) tree: simple graph such that if u and v are two vertices in T, then there is a unique path from u to v

Rooted tree: tree in which a particular vertex is designated as a root

Weighted tree: tree in which a weight is assigned to the edges

Weight of T: sum of the weights of all the edges in T, denoted by W(T)

Program Design Including Data Structures, Seventh Edition

Minimal Spanning Tree (cont’d.)

Spanning tree of graph G: if T is a subgraph of G such that V(T) = V(G)

All the vertices of G are in T

Figure 20-14 shows three spanning trees of the graph shown in Figure 20-13

Theorem: a graph G has a spanning tree if and only if G is connected

Minimal spanning tree: spanning tree in a weighted graph with the minimum weight

Program Design Including Data Structures, Seventh Edition

Minimal Spanning Tree (cont’d.)

Two well-known algorithms to find a minimal spanning tree:

Kruskal’s algorithm

Prim’s algorithm

Builds the tree iteratively by adding edges until a minimal spanning tree is obtained

Start with a designated vertex, called the source vertex

At each iteration, a new edge that does not complete a cycle is added to the tree

Program Design Including Data Structures, Seventh Edition

Minimal Spanning Tree (cont’d.)

Program Design Including Data Structures, Seventh Edition

Prim’s Algorithm to Find a Minimal Spanning Tree

Program Design Including Data Structures, Seventh Edition

Prim’s Algorithm to Find a Minimal Spanning Tree (cont’d.)

Program Design Including Data Structures, Seventh Edition

Summary

A graph G is a pair, G = (V, E)

In an undirected graph G = (V, E), the elements of E are unordered pairs

In a directed graph G = (V, E), the elements of E are ordered pairs

H is a subgraph of G if every vertex of H is a vertex of G and every edge is an edge in G

Two vertices in an undirected graph are adjacent if there is an edge between them

Program Design Including Data Structures, Seventh Edition

Summary (cont’d.)

Loop: an edge incident on a single vertex

Simple graph: no loops and no parallel edges

Simple path: all the vertices, except possibly the first and last vertices, are distinct

Cycle: a simple path in which the first and last vertices are the same

An undirected graph is connected if there is a path from any vertex to any other vertex

Program Design Including Data Structures, Seventh Edition

Summary (cont’d.)

Shortest path algorithm gives the shortest distance for a given node to every other node in the graph

In a weighted graph, every edge has a nonnegative weight

A tree in which a particular vertex is designated as a root is called a rooted tree

A tree T is called a spanning tree of graph G if T is a subgraph of G such that V(T) = V(G)

Program Design Including Data Structures, Seventh Edition