CS 225 Lecture 39: Graphs, Matrix and Lists imple

• School: University of Illinois
• Department: Computer Science
• Course: CS 225
• Professor: Heeren Cinda

Document Summary

Lecture 39 - graphs, matrix and lists imple. Mp7 available, due 12/6, 11:59p ec due 11/30, 11:59p. // these are simple connected, if not mentioned, it"s simple. // don"t assume it"s connected if not mentioned. // in other words, assume simple, but don"t assume connected. // but these bounds are for simple connected graphs. // number of edges is at least 99. Need: common vocabulary, graph implementation, traversal, algorithms. We express a graph g = (v,e) as vertices and edges. We can use a map where key is vertices, mapped to a set of edges connected two vertices, for example. vertices u and v connected by a. Some functions we"ll compare: insertvertex(vertex v) o(n) removevertex(vertex v) o(n) areadjacent(vertex v, vertex u) incidentedges(vertex v) o(n) We can also represent the graph as a 2d array, which is easier, where the indexes are vertices and it will be a true false whether there"s an edge connecting the two edges.