Graph Representations A D C B node list

Graph Representations A D C B node list

Graph Representations A D C B node list A-BCDEF B-ACEH C -ABD EH D -AC FGH E-ABCFG F-ADEGH G-DEFH H-BCDFG F H E G node list - lists the nodes connected to each node edge list - lists each of the edges as a pair of nodes undirected edges may be listed twice XY and YX in order to simplify algorithm implementation A B C adjacency matrix - for an n-node graph we build an D nxn array with 1's indicating edges and 0's no edge E F the main diagonal of the matrix is unused unless a G node has an edge connected to itself. If graph is weighted, 1's are replaced with edge weight values H adjacency matrix A 1 1 1 1 1 0 0 B 1 1 0 1 0 0 1 C 1 1 1 1 0 0

1 D 1 0 1 0 1 1 1 E 1 1 1 0 1 1 0 F 1 0 0 1 1 1 1 G 0 0 0 1 1 1 1 H 0 1 1 1 0 1 1 - edge list AB EA AC EB AD EC AE EF AF EG BA FA BC FD BE FE BH FG

CA FH CB GD CD GE CE GF CH GH DA HB DC HC DF HD DG HF DH HG Graph Depth-First Traversal (DFT) Algorithm Implementation text file representation Given a graph G(V,E) and a starting node vstart perform a depth-first traversal. Provide a list of the nodes in the order they are traversed. Graph is defined in a text file of the following format: 1st Line - # of nodes, N # of edges, E 2nd Line - List of node labels (you may assume 1 char each) 3rd Line - through N+3 Line an N x N adjacency matrix A D F C B H E G 8 AB CD EFGH 01111100 10101001 11011001 10100111 11100110 10011011 00011101 01110110 Graph Depth-First Traversal (DFT) Algorithm Implementation pseudo-code DFT( node vk ) { // deal with current node for each node, vi { if (node_avail(vi)) then DFT(vi) }

} node_avail( vi ) is a Boolean function that returns true if node vi is available for traversal, which means that vi has not been traversed, and vi is adjacent to vk. Floyd's Algorithm for Shortest Paths procedure floyd(W,D:matype) is 2 begin D:=W; V5 5 3 V 2 for k in 1..n loop 2 for i in 1..n loop 6 1 1 for j in 1..n loop D(i,j):=min(D(i,j),D(i,k)+D(k,j)); V3 V4 1 end loop; end loop; end loop; 1 2 3 4 5 end floyd; V1 1 1 2 3 4 5 0 3 2 1 2 0 - 6 0 1 - 0 - 1 1 0 Floyd's algorithm is very simple to implement. The fact that it works at all is not obvious. Be sure to work through the proof of algorithm correctness in the text. Graph Breadth-First Traversal Given a graph G(V,E) and a starting vertex s, perform a breadth-first traversal (BFT) of G. such that each

reachable vertex is entered exactly once. If all vertices are reachable, the edges traversed and the set of vertices will represent a spanning tree embedded in the graph G. A D F C B H E G 1) BFT suggests an iterative process (rather than a recursive one) 2) BFT vertices order of traversal can be maintained using a Queue data structure 3) The preferred representation for the graph is an adjacency matrix 4) We will need a way to keep up with which vertices have been "used" (e.g. a Boolean list) 5) Process begins by placing the starting vertex in the Queue 6) A vertex is taken from the Queue, every unused vertex adj to this vertex is added to the Queue This operation is repeated until the Queue is empty. 8) The output (answer) is returned in the form of a list of vertices in the order they entered the Queue Breadth-First Traversal of a Graph There are many applications in computer science for which we need to examine the nodes of a graph (or tree) in some orderly fashion. Previously we have looked at depth-first traversal using a recursive method operating on a stack data structure. Now we will investigate breadth-first traversal using an iterative method operating on a queue data structure. A graph consisting of nodes and edges connecting pairs of nodes can be represented as an adjacency matrix in which a 1 in row i column j indicates that there is an edge connecting node i to node j. If there is no edge, the corresponding value in the adjacency matrix will be zero (0). 0 2 1 3 5 4 6 0 1 2 3 4 5 6 0 1 2 3 4 5

6 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0 Reading the Adjacency Matrix from a File import java.util.Scanner; import java.io.*; public class BFT { public static void main(String[] args) throws Exception { int[][] mat = readMat(); showMat(mat);

} public static int[][] readMat() { try { Scanner input = new Scanner(new File("adjmat.txt")); int nrows = input.nextInt(); int ncols = input.nextInt(); int[][] m = new int[nrows][ncols]; for(int i = 0; i < nrows; i++) for(int j = 0; j < ncols; j++) m[i][j] = input.nextInt(); input.close(); return m; } catch(IOException e) { e.printStackTrace(); return null; } } public static void showMat(int[][] m) { for(int i=0;i q = new java.util.LinkedList(); q.offer(n); avail[n] = false; 0 while(q.size()>0) { 1 cur = q.remove(); 3 System.out.print(cur + " "); for(int k=0;k

4 { q.offer(k); 6 avail[k] = false; 0 1 2 3 4 } } 0 0 1 1 0 0 } 1 1 0 0 1 1 System.out.println(); 2 1 0 0 1 0 } 3 4 5 6 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 2 5 5 6 0 0 1 0 0 0 1 0 0 0 1 1 1

0 public static int[,] mat; public static bool[] avail; public static int nrow, ncol; C# Version static void Main(string[] args) { int startnode; load_mat(); show_mat(); Console.Write("Enter starting node... "); startnode = Convert.ToInt32(Console.ReadLine()); bft(startnode); 0 Console.ReadKey(); } 2 1 public static void bft(int n) { int cur; Queue q = new Queue(); q.Enqueue(n); avail[n] = false; while (q.Count > 0) { cur = (int)q.Dequeue(); Console.Write(cur + " "); for (int c = 0; c < ncol; c++) { if (avail[c] && mat[cur, c] == 1) { q.Enqueue(c); avail[c] = false; } } } Console.WriteLine(); } 3 5 4 6 0 1 2 3 4 5 6 0 1 2

3 4 5 6 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0

Recently Viewed Presentations

  • The International Non-Apportioned Commercial Vehicle Agreement (INCVA) A

    The International Non-Apportioned Commercial Vehicle Agreement (INCVA) A

    Missouri No restrictions for intra and inter. Need to stop at weigh scales if over 18,000 lbs. Regulations same as IFTA. Iowa (Transferred to Port of Entry) Inter is permitted under 26,000 lbs. Intra application required through Port of entry....
  • Welcome to Vermont The Continuing Story of Middle/Secondary

    Welcome to Vermont The Continuing Story of Middle/Secondary

    Welcome to Vermont Technology Virtual PDS Mini-grants Cited and Referenced extensively in numerous publications, edited by UVM faculty, published by Lab School (Brown) Interns - block scheduling, teacher advisory, and teaching to standards New Partnership - rethinking partnership with alternative...
  • Intercompany Inven - 1 INTERCOMPANY INVENTORY TRANSFERS Parent

    Intercompany Inven - 1 INTERCOMPANY INVENTORY TRANSFERS Parent

    Record Peerless's proportionate share of the increase in . value of available-for-sale securities held by subsidiary. Record increase in fair value of available-for-sale securities. Other Comprehensive Income from Subsidiary— Unrealized Gain on Investments (OCI) Income and Dividend Information about Peerless...
  • Land Planning Concepts

    Land Planning Concepts

    Steps of HIA Assessment, which is a two step process that first describes the baseline health status and then assesses potential impacts Scoping, to establish the scope of health effects that will be included in the HIA, the populations affected,...
  • Microsoft PowerPoint - Final. DISBO Council Meeting (9 22 ...

    Microsoft PowerPoint - Final. DISBO Council Meeting (9 22 ...

    Bureau of Diversity, Inclusion and Small Business Opportunities (BDISBO) MISSION: Support the growth and development of small businesses (SBs) and small diverse businesses (SDBs). VISION: To increase Commonwealth SB/SDB spend and create a more welcoming and conscientious SB/SDB procurement culture...
  • CS244- Introduction to embedded systems and ubiquitous computing

    CS244- Introduction to embedded systems and ubiquitous computing

    CS244-Introduction to Embedded Systems and Ubiquitous Computing Instructor: Eli Bozorgzadeh Computer Science Department UC Irvine Winter 2010 * Winter 2010- CS 244 * CS244 - Lecture 7 Sensors, Actuators and Other hardware components ICS212 WQ05 (Dutt) Hardware Components: Sensors, Actuators,...
  • IRIS Professional Development Building a Comprehensive ...

    IRIS Professional Development Building a Comprehensive ...

    Jigsaw Activity. Expert Groups Differentiate instructional elements (Page 4) Differentiate content (Page 5) Differentiate process (Page 6) Differentiate product (Page 7) Evaluate and grade student performance (Page 8) IRIS Center . IRIS Professional Development Series- Classroom Management (Part 1)
  • Ch. 1 slides Units, scientific notation.ppt 1 Scientific

    Ch. 1 slides Units, scientific notation.ppt 1 Scientific

    120 ms. 50 km. 12 mg. 100 km/hr. Units to help solve problems. 2 groups of students are working to clean a beach. It takes each group 5 minutes to clean up 200 m of a beach. How long does...