Transcript GRAPH - Yola

GRAPHS
Graph









The Graph Abstract Data Type
Graph Application
Graph Types
Path and Subgraph in Graph
Graph Connection types
Graph Operations
Graph Method
Graph Storage Structures
Graph implementations
The Graph Abstract Data Type

A graph is a way of representing relationships that
exist between pairs of objects.
a
graph is a set of objects, called vertices .
 together with a collection of pairwise connections
between them .
a
graph G is simply a set V of vertices
 and a collection E of pairs of vertices from V, called edges
The Graph Abstract Data Type


Graphs is a data structure that differ from all the
others in one major concept , each node may have
multiple predecessors as well as multiple successors .
Graphs are very useful structure . They can be used
to solve complex routing problems ,such as :
 designing
and routing airlines among the air ports they
serve .
 route messages over a computer network from one node
to another .
Graph Applications

Graphs have applications :
a host of different domains
 Mapping
 Transportation
 electrical engineering
 computer networks.

Graph Types

Directed Graph



An edge (u, v) is said to be directed from u to v if the pair
(u, v) is ordered, with u preceding v.
It contains ordered pair where (u,v) is not equal (v,u).
Undirected Graph
 An
edge (u, v) is said to be undirected if the pair (u, v) is not
ordered.
 It contain unordered pair as {u,v} and {u,v} is equal {v,u}.

mixed graph.
A
graph that has both directed and undirected edges is
often called a mixed graph.
Graph Types
Example:
World wide web
Example:
Social Network “Facebook”
Graph




The two vertices joined by an edge are called the
end vertices (or endpoints) of the edge.
If an edge is directed, its first endpoint is its origin
and the other is the destination of the edge.
Two vertices u and v are said to be adjacent if there
is an edge whose end vertices are u and v
An edge is said to be incident on a vertex if the
vertex is one of the edge's endpoints.
Graph cont.




The outgoing edges of a vertex are the directed
edges whose origin is that vertex.
The incoming edges of a vertex are the directed
edges whose destination is that vertex.
The degree of a vertex v, denoted deg(v), is the
number of incident edges of v.
The in-degree and out-degree of a vertex v are the
number of the incoming and outgoing edges of v,
and are denoted indeg(v) and outdeg(v),
respectively.
Graph cont.




Neighbors
 Two vertices are said to be neighbors if an edge directly
connects them
Path
 A sequence of vertices in which each vertex is adjacent to
the other
Cycle
 A path that start and ends with the same vertex
Loop
 A single Arc that begins and ends with the same vertex
subgraph of a graph G is a graph H whose vertices and edges
are subsets of the vertices and edges of G
Path and Subgraph

Directed Simple Path:
 (BOS, NW 35, JFK, AA 1387, DFW)

Directed Simple Cycle:


(LAX, UA 120, ORD, UA 877, DFW, AA 49, LAX)
Sub Graph

vertices ( BOS, JFK, and MIA) , and edges ( AA 903 and DL 247 )
Connectivity
12
Definition: An directed graph is strongly connected if
there is a path from a to b and from b to a whenever a and
b are vertices in the graph.

Definition: An directed graph is weakly connected if
there is a path between any two vertices in the underlying
undirected graph.

Connectivity
13
Example: Are the following directed graphs strongly or
weakly connected?

a
b
Weakly connected, because, for example, there is no path
from b to d.
d
c
a
b
d
c
Strongly connected, because there are paths between all
possible pairs of vertices.
Graph connection types cont.
Disjoint
A graph is disjoint if it not connected
b
c
a
d
e
Graph operations



Add Vertex
Insert a new vertex in the graph
When a vertex is added it is disjoint , it is not
connected to any other vertices in the list .
B
A
B
A
C
E
AddVertix
C
E
Graph operations cont.


Delete Vertex
Removes a vertex from the graph .When a vertex is
deleted , all connecting edges are removed .
B
A
B
C
E
C
E
A
Graph operations cont.



Add edge
Connect a vertex to a destination vertex .
If the graph is a digraph , then one of the edges
must be the source and the other is the destination .
B
A
B
A
C
E
C
E
Graph operations cont.



Find Vertex
Traverse the graph looking for a specified vertex.
If the vertex is found , its data are returned . If it is
not founded , an error is indicated .
Graph Methods

vertices():
 Return
an iterable collection of all the vertices of the
graph.

edges():
 Return
an iterable collection of all the edges of the
graph.
areAdjacent(v,w):
Test whether vertices v and w are adjacent.
 replace(v,x):


Replace the element stored at vertex v with x.
Graph Methods

replace(e,x):


insertVertex(x):


Insert and return a new undirected edge with end vertices v and
w and storing element x.
removeVertex(v):


Insert and return a new vertex storing element x.
insertEdge(v, w,x):


Replace the element stored at edge e with x.
Remove vertex v and all its incident edges and return the element
stored at v.
removeEdge(e):

Remove edge e and return the element stored at e.
Graph Storage Structures




To represent a graph , we need to store two sets :
The vertices of the graph
The edges or arcs .
The two common structures used to store these sets
are array and linked list .
Graph implementations

Uses a vector ( one –dimensional array ) for the
vertices and a matrix (two - dimensional array) to
store the edges .
Graph implementations


Uses a two- dimensional ragged array to store the
edges .
The vertex list is a singly linked list of the vertices in
the list .
Adjacency Matrix
Adjacency List