CMSC 341 Graphs Basic Graph Definitions A graph G V E consists of a finite set of vertices V and a set of edges E Each edge is a pair v w where v w V 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 2 Basic Graph Definitions cont d 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 3 Basic Graph Examples a a b e b e c d c d undirected graph directed graph 4 Basic Graph Definitions cont d Vertex v is adjacent to vertex w if and only if v w E Book calls this adjacent from Vertex v is adjacent from vertex w if and only if w v E An edge may also have weight or cost an associated value label a unique name The degree of a vertex u in an undirected graph is the number of vertices adjacent to u Degree is also called valence The indegree outdegree of a vertex u in a directed graph is the number of vertices adjacent to from u 5 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 A simple cycle is one in which the path is simple 6 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 7 a b g d c f e j i h 8 A Graph ADT Has some data elements vertices edges Has some operations getDegree u returns the degree of vertex u undirected graph getInDegree u returns the indegree of vertex u directed graph getOutDegree u returns the outdegree of vertex u directed graph getAdjacent u returns a list of the vertices adjacent from a vertex u directed and undirected graphs isAdjacentTo u v returns TRUE if vertex v is adjacent to vertex u FALSE otherwise directed and undirected graphs 9 Graph Traversals Like trees can be traversed breadth first or depth first Use stack for depth first traversal Use queue for breadth first traversal Unlike trees need to specifically guard against repeating a path from a cycle Can mark each vertex as visited when we encounter it and not consider visited vertices more than once 10 Breadth First Traversal Queue q new Queue graphvertex u for all v d v mark each vertex unvisited q enqueue startvertex start with any vertex d startvertex 0 mark visited while q isEmpty u q dequeue for each vertex w adjacent from u if d w w not marked as visited d w d u 1 mark visited q enqueue w 11 v1 v2 v3 v5 v4 12 Unweighted Shortest Path Problem Unweighted shortest path problem Given as input an unweighted graph G V E and a distinguished vertex s find the shortest unweighted path from s to every other vertex in G After running BFS algorithm with s as starting vertex the shortest path length from s to i is given by d i 13 Depth First Traversal dfs Graph G for each v V dfs v dfs Vertex v markVisited v for each vertex w adjacent from v if w is not marked as visited dfs w 14 DFS stack version Stack s new Stack GraphVertex u GraphVertex startvertex graph getStartVertex s push startvertex markVisited startvertex while s isEmpty u s Pop for each vertex w adjacent to u if w is not marked as visited markVisited w s push w 15 Depth First Traversal with Finish Times dfs Graph G for each v V d v 0 time 0 for each v V if d v 0 dfs v dfs Vertex v time time 1 d v time for each vertex w adjacent if d w 0 dfs w time time 1 f v time d discovery time global variable not discovered yet discover and mark v from v w not discovered v is finished 16 v1 v2 v3 v5 v4 17 Edge Types After DFS edges can be classified into the following types tree edges a discovered vertex v1 encounters an undiscovered vertex v2 the edge between them is a tree edge back edges a discovered vertex v1 encounters a discovered but unfinished vertex v 2 the edge between them is a back edge Graph has a cycle if and only if there is a back edge forward edges directed graphs only a discovered vertex v1 encounters a finished vertex v2 cross edges directed graphs only a discovered vertex v1 encounters a finished vertex v2 and d v1 d v2 18 Edge Types after DFS completion Condition Type of Edge v1 v2 If d v1 d v2 Tree f v1 f v2 Else if d v1 d v2 f v1 f v2 Back Else if d v1 d v2 f v1 f v2 Cross Else d v1 d v2 1 f v1 f v2 Forward 19 Utility of Discovery Finish Times A graph contains a cycle if and only if it contains a back edge Finish times can be used to do a topological sort of a digraph later Finish times can be used to find strongly connected components in a graph 20
View Full Document
Unlocking...