CompSci 100E37.1IntrotoGraphsÿ Definitions and Vocabularyþ A graph consists of a set of vertices (or nodes) and a set of edges(or arcs) where each edge connects a pair of vertices.þ If the pair of vertices defining an edge is ordered, then it is adirected graph.þ A vertex may have information called a label .þ An edge may have information called a weight or cost .þ A vertex i is adjacent to j if there is an edge from j to i.CompSci 100E37.2IntrotoGraphsÿ Definitions and Vocabularyþ A path is a sequence of adjacent vertices with a lengthequal to the number of edges on the path. This is alsoknown as the unweighted path length. The weighted pathlength is the sum of the costs of the edges of the path.þ A cycle is a path of at least length one where the first andlast vertex are the same.CompSci 100E37.3Graph Representationÿ Adjacency matrixþ Row and column numbers represent verticesþ Cells represent edgeso Use true/false for unweighted graphso Use weights for weighted graphs with special value(infinity) for no connectionþ Can have separate vector of vertex labelsAlgorithms use integers as identifiersþ O(N2) space: often sparse; much wasted spaceCompSci 100E37.4Graph Representationÿ How far from A to B?03551977823241Raleigh3550543283340105Murphy1975430259203438Manteo78283259054178Greensboro23340203540231Durham2411054381782310AshevilleRaleighMurphyManteoGreensboroDurhamAshevilleCompSci 100E37.5Graph Representationÿ Adjacency lists (Edge lists)þ Use vector to represent all vertices where index identifiesvertexo Each node in the vector can include a vertex labelþ Use linked lists to represent edges from these verticeso Each node in the linked list identifies a vertex and,optionally, edge costþ O(N) space when sparse; O(N2) when denseCompSci 100E37.6Graph Representationÿ Adjacency ListCompSci 100E37.7Graphsÿ Totally linked versions are also possibleÿ Special caseþ General Treesþ "Naturally Corresponding" Binary Treesÿ Working with graphs:Marking (I've been here! ... and more ...)þ Cave or maze explorationþ How have binary tree algorithms avoided the need forsuch marks?CompSci 100E37.8Graph Traversalsÿ Traversals: Depth First or Breadth First?þ What if vertices represent chess boards (i.e., positions)?þ What is a pre-order t raversal of a binary tree?þ What is a level-order traversal of a binary tree?CompSci 100E37.9Depth First Searchÿ Depth First Search (recursive)þ Un-mark all vertices (pre search initialization!!!)þ Process and mark starting vertexþ For each unmarked adjacent vertex do Depth First SearchCompSci 100E37.10Breadth First Searchþ Un-mark all verticesþ Process and mark starting vertex and place in queueþ Repeat until queue is empty:1. Remove a vertex from front of queue2. For each unmarked adjacent vertexÿ process itÿ mark itÿ place it on the queueCompSci 100E37.11Breadth First Searchÿ What if we apply this to binary tree?ÿ What would you name this traversal?CompSci 100E37.12Graph Algorithmsÿ Topological Sortþ Produce a valid ordering of all nodes, given pairwiseconstraintsþ Solution usually not uniqueþ When is solution impossible?ÿ Topological Sort Example: Getting an AB in CPSþ Express prerequisite structureþ This example, CPS courses only: 6, 100, 104, 108, 110, 1 30þ Ignore electives or outside requirements (can add later)CompSci 100E37.13IntrotoGraphsÿ Topological Sort Algorithm1. Find vertex with no incoming edges2. Remove (updating incoming edge counts) and Output3. Repeat 1 and 2 while vertices remainþ Complexity?ÿ Refine Algorithmþ Use queue? (and marking)þ Complexity?ÿ What is the minimum number of semesters required?þ Develop algorithmCompSci 100E37.14IntrotoGraphsÿ Shortest Pathÿ Traveling
View Full Document
Unlocking...