Discussion 12: Graphs Christine Zhou Agenda Announcements Let’s try to get through all the worksheet! Announcements Congratulations on finishing the project and getting through these past few weeks! Stay strong, keep pushing through :) HW 7 has been released Threads for each section on Piazza Want to chat? Email me! Graphs Can represent relationships! Family trees, cities and roads, etc. Lots of terminology: Vertices/nodes: graphs are made up of a set of these Edges: connect two vertices together (can be (un)directed) Adjacent: vertices with an edge between them Labels/Weights: the value of a vertex or edge Path: vertices connected by edges Cycle: path whose first and last vertices are the same Connectivity: vertices are connected if there is a path in between them; graphs are connected if all vertices are connected How do we represent a graph? Adjacency matrix Edge set Adjacency list 1 Graph Representation Represent the graph above with an adjacency list and an adjacency matrix representation. General Graph Traversal Algorithm Stack fringe = new Stack(); Set visited = new Set(); fringe.push (startVertex); while (!fringe.isEmpty()) { Vertex v = fringe.pop(); if (!visited.contains(v)) { process(v); //do something with v for (Vertex neighbor: v.neighbors) { fringe.push(neighbor); } visited.add(v); } } Depth First Search (DFS) Explore as far as possible before going back Search down entire subgraph of a child before moving onto the next child If there are multiple children that you could explore, break ties alphabetically Preorder: mark the current vertex, then visit the children Postorder: visit the children, then mark the current vertex Fringe is a stack Runtime: O(V + E) Visualization: here RECURSIVE IMPLEMENTATION OF DFS private void dfs(Graph G, int v) { marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; dfs(G, w); } } } Breadth First Search (BFS) ITERATIVE IMPLEMENTATION OF BFS