GraphsGraph definitionsGraph terminology IGraph terminology IIGraph terminology IIIGraph terminology IVAdjacency-matrix representation IAdjacency-matrix representation IIEdge-set representation IEdge-set representation IIAdjacency-set representation IAdjacency-set representation IIAdjacency-set representation IIIAdjacency-set representation IVSearching a graphExample: Depth-first searchFinding connected componentsGraph applicationsShortest-pathDijkstra’s algorithm IDijkstra’s algorithm IIDijkstra’s algorithm IIISummaryA graph puzzleThe EndGraphs2Graph definitionsThere are two kinds of graphs: directed graphs (sometimes called digraphs) and undirected graphsBirminghamRugbyLondonCambridgeBristolSouthhamptonDover60140190190150100120110An undirected graphstartfill panwith watertake eggfrom fridgebreak egginto panboilwateradd saltto waterA directed graph3Graph terminology IA graph is a collection of nodes (or vertices, singular is vertex) and edges (or arcs)Each node contains an elementEach edge connects two nodes together (or possibly the same node to itself) and may contain an edge attributeA directed graph is one in which the edges have a directionAn undirected graph is one in which the edges do not have a directionNote: Whether a graph is directed or undirected is a logical distinction—it describes how we think about the graphDepending on the implementation, we may or may not be able to follow a directed edge in the “backwards” direction4Graph terminology IIThe size of a graph is the number of nodes in itThe empty graph has size zero (no nodes)If two nodes are connected by an edge, they are neighbors (and the nodes are adjacent to each other)The degree of a node is the number of edges it hasFor directed graphs,If a directed edge goes from node S to node D, we call S the source and D the destination of the edgeThe edge is an out-edge of S and an in-edge of DS is a predecessor of D, and D is a successor of SThe in-degree of a node is the number of in-edges it hasThe out-degree of a node is the number of out-edges it has5Graph terminology IIIA path is a list of edges such that each node (but the last) is the predecessor of the next node in the listA cycle is a path whose first and last nodes are the sameExample: (London, Bristol, Birmingham, London, Dover) is a pathExample: (London, Bristol, Birmingham, London) is a cycleA cyclic graph contains at least one cycleAn acyclic graph does not contain any cyclesBirminghamRugbyLondonCambridgeBristolSouthhamptonDover601401901901501001201106Graph terminology IVAn undirected graph is connected if there is a path from every node to every other nodeA directed graph is strongly connected if there is a path from every node to every other nodeA directed graph is weakly connected if the underlying undirected graph is connectedNode X is reachable from node Y if there is a path from Y to X A subset of the nodes of the graph is a connected component (or just a component) if there is a path from every node in the subset to every other node in the subset7Adjacency-matrix representation IOne simple way of representing a graph is the adjacency matrixA 2-D array has a mark at [i][j] if there is an edge from node i to node jThe adjacency matrix is symmetric about the main diagonalABGEFDCABCDEFGA B C D E F G• This representation is only suitable for small graphs! (Why?)8Adjacency-matrix representation IIAn adjacency matrix can equally well be used for digraphs (directed graphs)A 2-D array has a mark at [i][j] if there is an edge from node i to node jAgain, this is only suitable for small graphs!ABGEFDCABCDEFGA B C D E F G9Edge-set representation IAn edge-set representation uses a set of nodes and a set of edgesThe sets might be represented by, say, linked listsThe set links are stored in the nodes and edges themselvesThe only other information in a node is its element (that is, its value)—it does not hold information about its edgesThe only other information in an edge is its source and destination (and attribute, if any)If the graph is undirected, we keep links to both nodes, but don’t distinguish between source and destinationThis representation makes it easy to find nodes from an edge, but you must search to find an edge from a nodeThis is seldom a good representation10Edge-set representation IIHere we have a set of nodes, and each node contains only its element (not shown)ABGEFDCpqrstuvwEach edge contains references to its source and its destination (and its attribute, if any)edgeSet = { p: (A, E), q: (B, C), r: (E, B), s: (D, D), t: (D, A), u: (E, G), v: (F, E), w: (G, D) }nodeSet = {A, B, C, D, E, F, G}11Adjacency-set representation IAn adjacency-set representation uses a set of nodesEach node contains a reference to the set of its edgesFor a directed graph, a node might only know about (have references to) its out-edgesThus, there is not one single edge set, but rather a separate edge set for each nodeEach edge would contain its attribute (if any) and its destination (and possibly its source)12Adjacency-set representation IIHere we have a set of nodes, and each node refers to a set of edgesABGEFDCpqrstuvwA { p }B { q }C { }D { s, t }E { r, u }F { v }G { w }Each edge contains references to its source and its destination (and its attribute, if any) p: (A, E)q: (B, C)r: (E, B)s: (D, D)t: (D, A)u: (E, G)v: (F, E)w: (G, D)13Adjacency-set representation IIIIf the edges have no associated attribute, there is no need for a separate Edge classInstead, each node can refer to a set of its neighborsIn this representation, the edges would be implicit in the connections between nodes, not a separate data structureFor an undirected graph, the node would have references to all the nodes adjacent to itFor a directed graph, the node might have:references to all the nodes adjacent to it, orreferences to only those adjacent nodes connected by an out-edge from this node14Adjacency-set representation IVHere we have a set of nodes, and each node refers to a set of other (pointed to) nodesThe edges are implicitABGEFDCA { E }B { C }C { }D { D, A }E { B, G }F { E }G { D }15Searching a graphWith certain modifications, any tree search technique can be applied to a graphThis
View Full Document