CMSC 341 Graphs Basic Graph Definitions A graph G V E consists of a finite set of vertices V and a finite set of edges E Each edge is a pair v w where v w V 8 3 2007 V and E are sets so each vertex v V is unique and each edge e E is unique Edges are sometimes called arcs or lines Vertices are sometimes called nodes or points UMBC CMSC 341 Graphs 2 Graph Applications Graphs can be used to model a wide range of applications including Intersections and streets within a city Roads trains airline routes connecting cities countries Computer networks Electronic circuits 8 3 2007 UMBC CMSC 341 Graphs 3 Basic Graph Definitions 2 A directed graph is a graph in which the edges are ordered pairs That is u v v u u v V Directed graphs are sometimes called digraphs An undirected graph is a graph in which the edges are unordered pairs That is u v v u A sparse graph is one with few edges That is E O V A dense graph is one with many edges That is E O V 2 8 3 2007 UMBC CMSC 341 Graphs 4 Undirected Graph 1 2 5 3 4 All edges are two way Edges are unordered pairs V 1 2 3 4 5 E 1 2 2 3 3 4 2 4 4 5 5 1 8 3 2007 UMBC CMSC 341 Graphs 5 Directed Graph 1 2 5 3 4 All edges are one way as indicated by the arrows Edges are ordered pairs V 1 2 3 4 5 E 1 2 2 4 3 2 4 3 4 5 5 4 5 1 8 3 2007 UMBC CMSC 341 Graphs 6 A Single Graph with Multiple Components 1 8 3 2007 6 2 5 3 4 7 UMBC CMSC 341 Graphs 8 9 7 Basic Graph Definitions 3 Vertex w is adjacent to vertex v if and only if v w E For undirected graphs with edge v w and hence also w v w is adjacent to v and v is adjacent to w An edge may also have weight or cost an associated value label a unique name The degree of a vertex v is the number of vertices adjacent to v Degree is also called valence 8 3 2007 UMBC CMSC 341 Graphs 8 Basic Graph Definitions 4 For directed graphs vertex w is adjacent to vertex v if and only if v w E Indegree of a vertex w is the number of edges v w OutDegree of a vertex w is the number of edges w v 1 1 2 5 2 5 3 4 3 4 Paths in Graphs A path in a graph is a sequence of vertices w1 w2 w3 wn such that wi wi 1 E for 1 i n The length of a path in a graph is the number of edges on the path The length of the path from a vertex to itself is 0 A simple path is a path such that all vertices are distinct except that the first and last may be the same A cycle in a graph is a path w1 w2 w3 wn w V such that there are at least two vertices on the path w1 wn the path starts and ends on the same vertex if any part of the path contains the subpath wi wj wi then each of the edges in the subpath is distinct i e no backtracking along the same edge A simple cycle is one in which the path is simple A directed graph with no cycles is called a directed acyclic graph often abbreviated as DAG 8 3 2007 UMBC CMSC 341 Graphs 10 Paths in Graphs 2 How many simple paths from 1 to 4 and what are their lengths 1 1 2 5 2 5 3 4 3 4 Connectedness in Graphs An undirected graph is connected if there is a path from every vertex to every other vertex A directed graph is strongly connected if there is a path from every vertex to every other vertex A directed graph is weakly connected if there would be a path from every vertex to every other vertex disregarding the direction of the edges A complete graph is one in which there is an edge between every pair of vertices A connected component of a graph is any maximal connected subgraph Connected components are sometimes simply called components 8 3 2007 UMBC CMSC 341 Graphs 12 Disjoint Sets and Graphs Disjoint sets can be used to determine connected components of an undirected graph For each edge place its two vertices u and v in the same set i e union u v When all edges have been examined the forest of sets will represent the connected components Two vertices x y are connected if and only if find x find y 8 3 2007 UMBC CMSC 341 Graphs 13 Undirected Graph Disjoint Set Example 1 6 2 5 3 4 7 8 9 Sets representing connected components 1 2 3 4 5 6 7 8 9 8 3 2007 UMBC CMSC 341 Graphs 14 DiGraph Strongly Connected Components 8 3 2007 a b g d c f e j i UMBC CMSC 341 Graphs h 15 A Graph ADT Has some data elements Has some operations Vertices and Edges getDegree u Returns the degree of vertex u outdegree of vertex u in directed graph getAdjacent u Returns a list of the vertices adjacent to vertex u list of vertices that u points to for a directed graph isAdjacentTo u v Returns TRUE if vertex v is adjacent to vertex u FALSE otherwise Has some associated algorithms to be discussed 8 3 2007 UMBC CMSC 341 Graphs 16 Adjacency Matrix Implementation Uses array of size V V where each entry i j is boolean TRUE if there is an edge from vertex i to vertex j FALSE otherwise store weights when edges are weighted Very simple but large space requirement O V 2 Appropriate if the graph is dense Otherwise most of the entries in the table are FALSE For example if a graph is used to represent a street map like Manhattan in which most streets run E W or N S each intersection is attached to only 4 streets and E 4 V If there are 3000 intersections the table has 9 000 000 entries of which only 12 000 are TRUE 8 3 2007 UMBC CMSC 341 Graphs 17 Undirected Graph Adjacency Matrix 1 8 3 2007 2 5 3 4 UMBC CMSC 341 Graphs 18 Directed Graph Adjacency Matrix 1 8 3 2007 2 5 3 4 UMBC CMSC 341 Graphs 19 Weighted Directed Graph Adjacency Matrix 1 8 2 2 5 6 5 7 2 3 8 3 2007 3 4 UMBC CMSC 341 Graphs 20 Adjacency Matrix Performance Storage requirement O V 2 Performance getDegree u isAdjacentTo u v getAdjacent u 8 3 2007 UMBC CMSC 341 Graphs 21 Adjacency List Implementation If the graph is sparse then keeping a list of adjacent vertices …