Transcript chapter11NGraph

Graphs
Upon completion you will be able to:
• Understand and use basic graph terminology and concepts
• Define and discuss basic graph and network structures
• Design and implement graph and network applications
• Design and implement applications using the graph ADT
• Define and discuss Dijkstra's shortest path algorithm
Data Structures: A Pseudocode Approach with C, Second Edition
1
11-1 Basic Concepts
A graph is a collection of nodes, called vertices, and a collection
of segments, called lines or edges, connecting pairs of vertices.
In Basic Concepts we develop the terminology and structure for
graphs. In addition to the graph definitions, discussion points
include:
• Directed and Undirected Graphs
• Cycles and Loops
• Connected and Disjoint Graphs
Data Structures: A Pseudocode Approach with C, Second Edition
2
• A directed graph or digraph for short, is a graph in which line has a
direction (arrow head) to its successor. The lines in a directed graphs
are known as arcs.
•An undirected graph is a graph in which there is no direction on the
lines, known as edges.
Data Structures: A Pseudocode Approach with C, Second Edition
3
•Two vertices in a graph are said to be adjacent vertices if there exists an edge that
directly connects them.
•A path is a sequence of vertices in which each vertex is adjacent to the next one. It
does not make any difference whether or not the graph is directed, it may still have
paths. In an undirected graph, you may travel in either directions. Simple path is a
path such that all its vertices and edges are distinct.
•A cycle is a path consisting of at least three vertices that starts and ends with the
same vertex.
•A loop is a special case of a cycle in which a single arc begins and ends with the
same vertex. In a loop, the end points of the edge are the same.
Data Structures: A Pseudocode Approach with C, Second Edition
4
•Two vertices are said to be connected if there is a path between them. A graph is said to
be connected if, suppressing direction, there is a path from any vertex to any other vertex.
•A directed graph is strongly connected if there is a path from each vertex to every other
vertex in the digraph.
•A directed graph is weakly connected when there are at least two vertices that are not
connected.
• A graph is disjoint if it is not connected.
•The degree of a vertex is the number of lines incident to it.
• The outdegree of a vertex in a digraph is the number of arcs leaving the vertex.
• The indegree is the number of arcs entering the vertex.
Data Structures: A Pseudocode Approach with C, Second Edition
5
11-2 Operations
We define and discuss the six primitive graph operations
required to maintain a graph.
• Insert Vertex
• Delete Vertex
• Add Edge
• Delete Edge
• Find Vertex
• Traverse Graph
Data Structures: A Pseudocode Approach with C, Second Edition
6
Data Structures: A Pseudocode Approach with C, Second Edition
7
Data Structures: A Pseudocode Approach with C, Second Edition
8
Data Structures: A Pseudocode Approach with C, Second Edition
9
Data Structures: A Pseudocode Approach with C, Second Edition
10
Data Structures: A Pseudocode Approach with C, Second Edition
11
Data Structures: A Pseudocode Approach with C, Second Edition
12
1. We begin by pushing the 1st vertex, A, into the stack.
2. We then loop, popping the stack and after processing the vertex,
pushing all of the adjacent vertices into the stack. To process X at
step 2, we pop X from the stack, process it and then push G and H
into the stack giving the stack contents for step 3 to process H and G.
3. When the stack is empty, the traversal is complete.
Data Structures: A Pseudocode Approach with C, Second Edition
13
Data Structures: A Pseudocode Approach with C, Second Edition
14
1. We begin by enqueuing vertex, A, in the queue.
2. We then loop, dequeuing the queue and processing the vertex from
the front of the queue. After processing the vertex, we place all of
its adjacent vertices into the queue. We are then ready for the next
step.
3. When the queue is empty, the traversal is complete.
Data Structures: A Pseudocode Approach with C, Second Edition
15
11-3 Graph Storage Structures
To represent a graph, we need to store two sets. The first set
represents the vertices of the graph, and the second set
represents the edges or arcs. The two most common structures
used to store these sets are arrays and linked lists.
• Adjacency Matrix
• Adjacency List
Data Structures: A Pseudocode Approach with C, Second Edition
16
Data Structures: A Pseudocode Approach with C, Second Edition
17
Data Structures: A Pseudocode Approach with C, Second Edition
18
11-6 Networks
A network is a graph whose lines are weighted. It is also known
as a weighted graph. Included in this section are two graph
applications that process networks.
• Minimum Spanning Tree
• Shortest Path Algorithm
Data Structures: A Pseudocode Approach with C, Second Edition
19
Data Structures: A Pseudocode Approach with C, Second Edition
20
Data Structures: A Pseudocode Approach with C, Second Edition
21
Data Structures: A Pseudocode Approach with C, Second Edition
22
Minimum Spanning Tree


A spanning tree is a tree that contains all
of the vertices in a graph.
A minimum spanning tree is a spanning
tree in which the total weight of the lines
are guaranteed to be the minimum of all
possible trees in the graph. If the weights
are unique, then there will be only one
minimum spanning tree.
Data Structures: A Pseudocode Approach with C, Second Edition
23
Algorithm of MST (Prim Algoritm)
1. Insert the first vertex (pick any
vertex) into the tree
2. From every vertices already in the
tree, examine the edges that
connected to all adjacent vertices
not in the tree.
Select the edge with the minimum
weight to a vertex not currently in
the tree.
Insert that minimum-weight edge
and the vertex into the tree.
3. Repeat step 2 until all vertices are
in the tree.
Data Structures: A Pseudocode Approach with C, Second Edition
24
Data Structures: A Pseudocode Approach with C, Second Edition
25
(continued)
Data Structures: A Pseudocode Approach with C, Second Edition
26