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
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) RECURSIVE IMPLEMENTATION OF DFS - Explore as far as possible before going private void dfs(Graph G, int v) back { marked[v] = true; - Search down entire subgraph of a child for (int w : G.adj(v)) before moving onto the next child { - If there are multiple children that you could if (!marked[w]) { explore, break ties alphabetically - Preorder: mark the current vertex, then edgeTo[w] = v; visit the children dfs(G, w); - Postorder: visit the children, then mark the } current vertex } - Fringe is a stack } - Runtime: O(V + E) - Visualization: here
Breadth First Search (BFS) ITERATIVE IMPLEMENTATION OF BFS private void bfs(Graph G, int s) { Queue<Integer> fringe = new - Search graph equidistantly from Queue<>(); the source fringe.enqueue(s); - marked[s] = true; Start at the root, search all the while (!fringe.isEmpty()) { children, then do the same with all int v = the other children fringe.dequeue(); - Fringe is a queue for (int w : G.adj(v)) { if (!marked[w]) { - Runtime: O(V + E) - Can be helpful in finding shortest fringe.enqueue(w); paths on unweighted graphs marked[w] = true; edgeTo[w] = v; } } }
2 Searches and Traversals Run depth first search (DFS) and breadth first search (BFS) on the graph starting from node A. List the order in which each node is first visited. Whenever there is a choice of which node to visit next, visit nodes in alphabetical order.
Topological Sorting - Do not explore a node unless it is a source node or all incoming nodes have been explored - If we have a graph of classes and prerequisites, a topological sort will give us an ordering to take the classes - Can run DFS postorder and reverse the ordering to get a valid topological sort - Can only work on DAG (directed acyclic graphs) - Think about the prerequisites. Does it make sense to have cycles in a graph of prerequisites?
Dijkstra’s Algorithm - Find shortest paths to all the vertices with edge weights != 1 - Fringe is a priority queue - Runtime: O((V+E) log V) - Idea: when you pop an element off fringe, it will be the shortest path!
4 Dijkstra’s Algorithm Given the following graph, run Dijkstra’s algorithm starting at node A. At each step, write down the entire state of the algorithm. This includes the value dist(v) for all vertices v for that iteration as well as what node was popped off of the fringe for that iteration.
5 Dijkstra’s Correctness What must be true about our graph in order to guarantee Dijkstra’s will return the shortest paths tree to every vertex? Draw an example of a graph that demonstrates why Dijkstra’s might fail if we do not satisfy this condition. Note: Is this true in all cases? Can you think of an exception to this general rule?
Hiển thị 15 trang đầu. Tải tài liệu để xem đầy đủ.
Chưa có bình luận nào. Hãy là người đầu tiên!
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!