CMSC 341Basic Graph DefinitionsBasic Graph Definitions (cont’d)Basic Graph ExamplesSlide 5Paths in GraphsConnectedness in GraphsPowerPoint PresentationA Graph ADTGraph TraversalsBreadth-First TraversalSlide 12Unweighted Shortest Path ProblemDepth First TraversalDFS (stack version)Slide 16Slide 17Edge TypesEdge Types (after DFS completion)Utility of Discovery/Finish TimesCMSC 341Graphs2Basic Graph DefinitionsA 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.3Basic 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).4Basic Graph Examplesundirected graph directed graphabec dab ec d5Basic 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 nameThe 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.6Paths in GraphsA 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.7Connectedness in GraphsAn 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.8abcdgej if h9A Graph ADTHas some data elements–vertices–edgesHas 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)10Graph TraversalsLike 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.11Breadth-First TraversalQueue q = new Queue();graphvertex u;for all v, d[v] =  // mark each vertex unvisitedq.enqueue(startvertex); // start with any vertexd[startvertex] = 0; // mark visitedwhile (!q.isEmpty()) {u = q.dequeue();for (each vertex w adjacent from u)if (d[w] == ) { // w not marked as visitedd[w] = d[u]+1; // mark visitedq.enqueue(w);}}12v1v2v4v3v513Unweighted Shortest Path ProblemUnweighted 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].14Depth First Traversaldfs(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)}15DFS (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);}}16Depth First Traversal with Finish Timesdfs(Graph G) {for (each v  V)d[v] = 0 // d = discovery “time”time = 0 // “global” variablefor (each v  V)if (d[v] = 0) // not discovered yetdfs (v)}dfs(Vertex v) {time = time + 1d[v] = time // “discover” and mark vfor(each vertex w adjacent from v)if (d[w] = 0) // w not discovereddfs(w)time = time + 1f[v] = time // v is “finished”}17v1v2v4v3v518Edge TypesAfter 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 v2; 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]19Edge Types (after DFS completion)Condition Type of Edge (v1, v2)If (d[v1] < d[v2]) && (f[v1] > f[v2]) Tree 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]) Forward20Utility 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