# Welcome to IS 2610 - University of Pittsburgh School of ... IS 2610: Data Structures Graph April 5, 2004 Graph Terminology Graph : vertices + edges Induced subgraph of a subset of vertices Connected graph: a path between every pair Maximal connected: there is no path from this subgraph to an outside vertex Representation typedef struct { int v; int w; } Edge; Edge EDGE(int, int);

struct graph *Graph; GRAPHinit(int); GRAPHinsertE(Graph, Edge); GRAPHremoveE(Graph, Edge); GRAPHedges(Edge [], Graph G); GRAPHcopy(Graph); GRAPHdestroy(Graph); typedef struct node *link; struct node { int v; link next; }; struct graph { int V; int E; link *adj; }; Graph GRAPHinit(int V) { int v; Graph G = malloc(sizeof *G); G->V = V; G->E = 0; G->adj = malloc(V*sizeof(link)); for (v = 0; v < V; v++) G->adj[v] = NULL; return G; } Hamilton Path Hamilton path:

Given two vertices, is there a simple path connecting them that visits every vertex in the graph exactly once? Worst case for finding Hamilton tour is exponential Assume one vertex isolated; and all v-1 vertices are connected (v-1)! Edges need to be checked Euler Tour/Path Euler Path

Euler tour: Is there a cycle with each edges exactly once Bridges of konigsberg Properties: Is there a path connecting two vertices that uses each edge in the graph exactly once? Vertices may be visited multiple times A graph has a Euler tour iff it is connected and all the vertices are of even degree A graph has a Euler path iff it is connected and exactly two of its vertices are of odd degrees

Complexity? Graph Search Depth First Search void dfsR(Graph G, Edge e) { link t; int w = e.w; pre[w] = cnt++; for (t = G->adj[w]; t != NULL; t = t>next) if (pre[t->v] == -1) dfsR(G, EDGE(w, t->v)); } V2 for adj matrix V+E for adj. list Graphs may not be connected #define dfsR search

void dfsR(Graph G, Edge e) { int t, w = e.w; pre[w] = cnt++; for (t = 0; t < G->V; t++) if (G->adj[w][t] != 0) if (pre[t] == -1) dfsR(G, EDGE(w, t)); } static int cnt, pre[maxV]; void GRAPHsearch(Graph G) { int v; cnt = 0; for (v = 0; v < G->V; v++) pre[v] = -1; for (v = 0; v < G->V; v++) if (pre[v] == -1) search(G, EDGE(v, v)); } DFS for graph problems

Cycle detection Back edges Simple path Simple connectivity The graph search function calls the recursive DFS function only once. Two way Euler tour Each edge visited exactly twice Spanning tree Given a connected graph with V vertices, find a set of V-1 edges that connects the vertices Any DFS is a spanning tree Two coloring, bipartiteness check Separability and Connectivity

Bridge An edge that, if removed, would separate a connected graph into two disjoint subgraphs. Edge-connected graph has no bridges In a DFS tree, edge v-w is a bridge iff there are no back edges that connect a descendant of w to an ancestor of w T T G S E R

G A S E R A Separability and Connectivity Articulation point (separation/cut) Removal results in at least two disjoint subgraphs K-connected - for each pair: At least k vertex disjoint paths Indicates the number of vertices that need to be removed to disconnect a graph Biconnected : 2-connected

removal of a vertex does not disconnect K-edge-connected - for each pair: At least k edge disjoint paths Indicates the number of edges that need to be removed to disconnect a graph T G S E R A BFS Search Instead of Stack

Use a Queue Can be used to solve Connected components Spanning tree Shortest paths #define bfs search void bfs(Graph G, Edge e) { int v, w; QUEUEput(e); while (!QUEUEempty()) if (pre[(e = QUEUEget()).w] == -1) { pre[e.w] = cnt++; st[e.w] = e.v; for (v = 0; v < G->V; v++)

if (G->adj[e.w][v] == 1) if (pre[v] == -1) QUEUEput(EDGE(e.w, v)); } } Directed Graph Digraph: Vertices + directed edges In-degree: number of directed edge coming in Out-degree: number of directed edge going out DAG no directed cycles Strongly connected

Every vertex is reachable from every other Not strongly connected : set of strong components Kernel K(D) of digraph D One vertex of K(D) corresponds to each strong component of D One edge in K(D) corresponds to each edge in D that connects vertices in different components K(D) is a DAG Reachability and Transitive closure Transitive closure of a graph

Same vertices + an edge from s to t in transitive closure if there is a directed path from s to t Warshalls algorithm Complexity: V3 for (i = 0; i < G->V; i++) for (s = 0; s < G->V; s++) for (t = 0; t < G->V; t++) if (A[s][i] && A[i][t] == 1) G->tc[s][t] = 1; void GRAPHtc(Graph G) { int i, s, t; G->tc = MATRIXint(G->V, G->V, 0); for (s = 0; s < G->V; s++) for (t = 0; t < G->V; t++) G->tc[s][t] = G->adj[s][t]; for (s = 0; s < G->V; s++) G->tc[s][s] = 1; for (i = 0; i < G->V; i++) for (s = 0; s < G->V; s++) if (G->tc[s][i] == 1) for (t = 0; t < G->V; t++) if (G->tc[i][t] == 1) G->tc[s][t] = 1;

} Topological Sort Given a DAG Renumber vertices such that every directed edge points from a lower-numbered vertex to a highernumber one 0 6 2 1 4 6 2 1 7

8 3 5 0 4 3 relabel 8 5 7 Topological Sort Process each vertex before processing the vertices it points 0

1 2 3 Reverse topological sort 8 7 6 4 rearrange Scheduling applications Postorder numbering in DFS yields a reverse topological

sort 5 Topological Sort // Reverse (adj list) static int cnt0; static int pre[maxV]; void DAGts(Dag D, int ts[]) { int v; cnt0 = 0; for (v = 0; v < D->V; v++) { ts[v] = -1; pre[v] = -1; } for (v = 0; v < D->V; v++) if (pre[v] == -1) TSdfsR(D, v, ts); } void TSdfsR(Dag D, int v, int ts[]) { link t; pre[v] = 0; for (t = D->adj[v]; t != NULL; t = t->next) if (pre[t->v] == -1) TSdfsR(D, t->v, ts); ts[cnt0++] = v; } // Adj. matrix

void TSdfsR(Dag D, int v, int ts[]) { int w; pre[v] = 0; for (w = 0; w < D->V; w++) if (D->adj[w][v] != 0) if (pre[w] == -1) TSdfsR(D, w, ts); ts[cnt0++] = v; } Minimum Spanning Tree Weighted graph To incorporate this information into the graph, a weight, usually a positive integer, is attached to each arc capacity, length, traversal time, or

traversal cost. Minimum Spanning tree (MST) A spanning tree whose weight (the sum of the weights in its edges) is no larger than the weight of any other spanning tree Representation weighted graph using an adjacency matrix is straightforward use an integer matrix In the adjacency list representation, the elements of the list now have two components, the node and the weight of the arc MST

A graph and its MST MST A Cut A partition of the vertices into two disjoint sets Crossing edge is one that connects a vertex in one set with a vertex in the other Cut Property Given some cut in a graph, every minimal crossing edge belongs to some MST of the graph, and every MST contains a minimal crossing edge X N1

N2 Cut Property Proof: Suppose that on the contrary, there is no minimum spanning tree that contains X. Take any minimum spanning tree and add the arc X to it. X N1 N2 Y A cycle is formed after adding X. Cycle Property Cycle property

Given a graph G, consider the graph G defined by adding an edge e to G Adding e to an MST of G and deleting a maximal edge on the resulting cycle gives an MST of G Prims algorithm Prims algorithm Step 1: x V, Let A = {x}, B = V - {x} Step 2: Select (u, v) E, u A, v B such that (u, v) has the smallest weight between A and B Step 3: (u, v) is in the tree. A = A {v}, B = B {v}

Step 4: If B = , stop; otherwise, go to Step 2. time complexity: O(n2), n = |V|. Prims Algorithm Kruskals algorithm Step 1: Sort all edges Step 2: Add the next smallest weight edge to the forest if it will not cause a cycle. Step 3: Stop if we

have n-1 edges. Otherwise, go to Step2. Shortest Path The shortest path problem has several different forms: Given two nodes A and B, find the shortest path in the weighted graph from A to B. Given a node A, find the shortest path from A to every other node in the graph. (single-source shortest path problem) Find the shortest path between every pair of nodes in the graph. (all-pair shortest path problem) Shortest Path

Visit the nodes in order of their closeness; visit A first, then visit the closest node to A, then the next closest node to A, and so on. Dijkstras algorithm Shortest path To select the next node to visit, we must choose the node in the fringe that has the shortest path to A. The shortest path from the next closest node must immediately go to a visited node. Visited nodes form a shortest path tree Fringe node set

## Recently Viewed Presentations

• [email protected] Negative issues. no money available for home loans, job security, ongoing commentary that house prices will continue to fall for the foresable future. Positive. there are people who see good value for money and want to buy now and...
• The Metis were a people of mixed aboriginal and French descent who lived in the Northwest Territories and who engaged in hunting, trading and some agriculture. ... Quebec made provincial rights and autonomy an important issue in Quebec, this was...
• Obligation Adjustment Reporting System (OARS) What is OARS? It is the current system to request authority for an Upward Obligation Adjustment (UOA). You can locate the system to request access at the following URL: https://oars.hq.af.mil. With the current system a...
• Periodic Table Designs Discovering the Periodic Table Metals and Nonmetals Slide 16 The Periodic Table Orbitals Being Filled Electron Filling in Periodic Table Metallic Characteristic Periodic Table Melting Points Densities of Elements Electronegativities Slide 25 Atomic Radii Atomic Radii of...
• Arthur Chee. Sandy Lee. Motivation. Abusiness continuity plan helps an organization prepare in advance of a disruption, and the impact of a disaster can be reduced by planning ahead. The objective of the study is to provide a directional sense...
• Sensor and Transducers. ... The Thermistor is another type of temperature sensor, whose name is a combination of the words THERM-ally sensitive res-ISTOR. A thermistor is a type of resistor which changes its physical resistance with changes in temperature.
• Romania. Their Ministry: Sharing the Gospel and training leaders through Christian Camp ministries. Things to Pray for: Camp - They are gearing up for camp. Pray they are diligent and persevering in preparing each program. Training starts the 22nd. Ministry...
• 61% of bankers say a customer-centric business model is "very important". Only 17% are "very prepared" for it. "Fewer Heart Transplants, More Bypasses" ... As a bonus from last month, the storefront play from retail holds true for branch banking....