OutlineToday and next lecture:• Graph Terminology• Graph representation: adjacency matrix and adjacency list• Graph traversal: DFS and BFS• Topological sort• Minimum Spanning Tree (MST): Prim’s and Kruskal’s algorithms• Dijkstra’s SPFSugih Jamin ([email protected])GraphsWhat is a graph?Examples of graph: airline flight map, the Internet, the Web, NPC(non-player character) state machine, protocol state machine, objectinheritance, makefile dependencies, a program’s call graph, registerallocation, data-flow analysis, garbage collection, manufacturing process,organizational cash flow, facility location, etc.The most versatile of data structuresSugih Jamin ([email protected])Graph: Formal DefinitionA graph G = (V, E) isa set of vertices (or nodes), V = {v1, v2, v3, . . .},together with a set of edges (or links), E = {e1, e2, e3, . . .},that connect pairs of verticesTwo vertices are directly connected if there is an edge connecting themDirectly connected vertices are said to be adjacent to each other, andone is said to be the neighbor of the otherThe edge directly connecting two vertices are said to be incident to thevertices, and the vertices incident to the edgeSugih Jamin ([email protected])Nodes, Edges, PathsTwo vertices may be directly connected by more than one parallel edgesAn edge connecting a vertex to itself is called a self-loopA simple graph is a graph without parallel edges and self-loopsUnless otherwise specified, we will work mostly with simple graphA path in G from node u to v is a sequence of vertices from u to v in GA simple path is a path with no vertex appearing twiceA connected graph is a graph where a simple path existsbetween all pairs of verticesSugih Jamin ([email protected])Weighted GraphsWeighted graph: edges of a graph may have different costs or weightsExample: to go from A to B, one can fly, drive on freeway, drive onhighway, or bike, or walk on a trail, each has a different cost (in time,money, etc.)A network connection between two hosts can be through a 24KbpsGPRS, 56Kbps modem, 256Kbps satellite, 256Kbps ADSL, 1Mbps cablemodem, 1.5Mbps T1, 2Mbps microwave, 1-3Mbps fixed wireless, 10 MbpsWiFi, 45Mbps T3, 50 Mbps 802.11[ag], 100 Mbps MIMO, 155Mbps OC3,622Mbps OC12, 1Gbps Ethernet, 10Gbps Ethernet, etc.Unweighted graph: all edges have the same costSugih Jamin ([email protected])Directed GraphsDirected graph (digraph):• edges are directional• nodes incident to an edge form an ordered pairo order of nodes on edges is importanto e = (u, v) means there is an edge from u to v,i.e., a path can form from u to v but not vice versa• examples: rivers and streams, one-way streets, customer-providerrelationshipsSugih Jamin ([email protected])Undirected GraphsUndirected graph:• there’s no ordering of nodes on edges• e = (u, v) means there is an edge between u and va path can go in either direction• examples: co-authorship of books, co-starring of movies, team-mates,or any other kinds of inherently two-ways, symmetric relationshipsSugih Jamin ([email protected])Node Degree and ConnectednessThe degree of a node is the number of its (directly connected) neighborsFor directed edges, we differentiate between ingress (incoming) edgeand egress (outgoing) edge of a nodeThus we also speak of a node’s in-degree and out-degreeA directed graph is strongly connected if there is a simple directed pathbetween any pair of verticesA directed graph is weakly connected if there is a simple path betweenany pair of vertices in the underlying undirected graphSugih Jamin ([email protected])Acyclic GraphA cycle is a path starting and finishing at the same nodeA self-loop is a cycle of length 1A simple cycle has no repeated nodes (except the first == last node)A simple graph is a graph with no self-loop (nor parallel edges)An acyclic graph is a graph with no cycleA DAG is a directed acyclic graphSugih Jamin ([email protected])Graph Size and SubgraphThe size of a graph, and the complexity of a graph-theoretic algorithm,is usually defined in terms of number of edges |E|, number of vertices|V |, or bothSparse graph: a graph with few edges, |E|  |V |2or |E| ≈ |V |Dense graph: a graph with many edges, |E| ≈ |V |2G0= (V0, E0) is a subgraph of G = (V, E) iff V0⊂ V and E0⊂ EA clique is a subgraph where every node pair is directly connectedA complete graph (or (full-)mesh) is a graph whereevery node pair is directly connectedHow many edges are there in a complete graph of N nodes?Sugih Jamin ([email protected])Graph Algorithm QuestionsSee airline flight graph of GTM Fig. 12.14Describe an algorithm to determine:• all non-stop flights from JFK (O( ))• if any non-stop flights from JFK exist (O( ))• greatest distance covered by a non-stop flight from JFK (O( ))Associate a price with each flight, describe an algorithm to determine:• best “value” non-stop flight from JFK (max distance/price) (O( ))• best “value” tour (non-stop or connecting flights) from JFK (O( ))Sugih Jamin ([email protected])Graph Algorithm QuestionsDescribe an algorithm to determine:• if a flight from JFK to SFO exists (O( ))• minimal cost (distance or price) from JFK to SFO (O( ))Suppose numbers represent cost (in billions USD) to build high-speed rail,describe an algorithm to determine least cost construction, such that anycity can be reached from any other city (O( ))Suppose you are planning a family reunion. Your family is spread out allover the US and you are paying for their travel. Describe an algorithm tofind the city to host the reunion that minimizes total travel cost (O( ))Sugih Jamin ([email protected])Graph Representation: Adjacency MatrixThe graph:ac dfbegas an adjacency matrix:a b c d e f ga 0 0 1 1 0 1 0b 0 0 0 1 1 0 0c 1 0 0 0 0 1 0d 1 1 0 0 1 1 0e 0 1 0 1 0 0 0f 1 0 1 1 0 0 0g 0 0 0 0 0 0 0Adjacency matrix:• an edge in an unweighted graphis represented with a ‘1’,‘0’ otherwise• only needs O(|V |2) bits to rep-resent an unweighted graph• an edge in a weighted graph isrepresented with its weight, ‘∞’otherwise• undirected graph only needsO(|V |2/2) spaceSugih Jamin ([email protected])Graph Representation: Adjacency ListThe graph:ac dfbegas an adjacency list:a c d fb d ec a fd a b e fe b df a cgAdjacency list:• can also be implemented aslinked list• weighted graph stores edgeweight on link-list node• undirected graph must representeach edge twice• space used is O(|V | + |E|)Sugih Jamin