CS 310 Graphs, Page 1'&$%GraphsA graph consists of a set of vertices V and a set of edgesE = {(v1, v2)|v1, v2∈ V }.If (v1, v2) are ordered, we have a directed graph, or digraph.ADBECV = {A,B,C,D,E}E = {(A,C),(A,D),(A,E) (B,E),(C,A),(C,B), (C,D),(D,C),(E,D) }In a directed graph, edge (u, v) is different from edge (v, u).For a directed edge (u, v), u is called the source and v thedestination.CS 310 Graphs, Page 2'&$%If (v1, v2) are unordered, we have a undirected graph (or simplygraph).ADBECV = {A,B,C,D,E}E = {(A,C),(A,D),(A,E) (B,C),(B,E),(C,A),(C,B), (C,D),(D,C),(D,A),(D,E), (E,A),(E,B),(E,D)}In an undirected graph, (u, v) and (v, u) represent the same edge.CS 310 Graphs, Page 3'&$%More Examples125 34310 99CS 310 Graphs, Page 4'&$%ApplicationsGraphs are used to represent and investigate the relationships(edges) among entries (vertices).Examples:Let vertex set V1contain all the states of USA.• Graph G1= (V1, E1) whereE1= {(v1, v2) | states v1and v2are geometrically adjacent}• Graph G2= (V1, E2) whereE1= {(v1, v2) | there is a direct Northwest flightfrom state v1to state v2}CS 310 Graphs, Page 5'&$%Let vertex set V2be all the 1999 CS courses at GMU.• Graph G3= (V2, E3) whereE3= {(v1, v2) | course v1is a prerequisite of course v2}• Graph G4= (V2, E4) whereE4= {(v1, v2) | courses v1and v2are taughtby the same instructor}Let vertex set V3be all the computers connected to the Internet.• The topology of the Internet can be defined as a graphG5= (V3, E5), whereE5= {(v1, v2) | machines v1and v2are connecteddirectly via some communication link}CS 310 Graphs, Page 6'&$%One More ApplicationLet us consider a little game.• To start the game, you place three coins on the table in a lineas (H, T, H).• You may flip the middle coin whenever you want to.• You may flip one of the end coins only if the other two coinsare the same as each other.• The goal of the game is to reach the configuration (T, H, T).CS 310 Graphs, Page 7'&$%We could use a graph to help figure out a solution.• Vertices: all possible coin configurations, that is, allcombinations of H/T of three coins.• Edges: two configurations u and v are connected if we can gofrom configuration u to configuration v with a legal flip.(H, H, H)(T, H, H) (H, T, H) (H, H, T)(T, T, H) (T, H, T) (H, T, T)(T, T, T)CS 310 Graphs, Page 8'&$%Terminology• A vertex is also called a node, and an edge is also called a link.• Two nodes u and v are adjacent if e = (u, v) is an edge in thegraph.We also say u and v are connected by edge e.• A path a sequence of verticesv0, v1, v2, . . . , vksuch that (vi, vi+1), 0 ≤ i < k, is an edge in G.• A cycle is a path that starts and ends at the same vertex.• A graph G is connected if starting with any vertex v you canreach all the other vertices in G.CS 310 Graphs, Page 9'&$%Representations of GraphsADBECV = {A,B,C,D,E}E = {(A,C),(A,D),(A,E) (B,E),(C,A),(C,B), (C,D),(D,C),(E,D) }• Adjacency Table:A B C D EA 0 0 1 1 1B 0 0 0 0 1C 1 1 0 1 0D 0 0 1 0 0E 0 0 0 1 0CS 310 Graphs, Page 10'&$%• Adjacency List:A=0B=1C=2D=3E=42 3 440 3 123CS 310 Graphs, Page 11'&$%• Edge Sets: use a Set data structure to store the neighboringvertices of each vertex.Assume that we have implemented a template Set class, whichinternally uses a B-tree to store the objects of a set. Torepresent a graph with 10 vertices:Set<int> neighbors[10](set neighbors[i] contains all neighbors of vertex i).CS 310 Graphs, Page 12'&$%Which Representation is Best ?• Adjacent table☞ Space consumption: O(N2), where N is the number ofvertices.☞ O(1) time to add/remove edges or to check if two verticesare connected.☞ O(N ) time to find out all the neighbors of a given node.☞ Easy to implement☞ Bad for sparse graphs where there is a large number ofnodes but each node has only a small number neighbors.CS 310 Graphs, Page 13'&$%• Adjacent list☞ Space consumption depends on the “density” of the graph.General cases ?Worst case ?☞ Time to add/remove edges or to check if two vertices areconnected:General cases ?Worst case ?☞ Time to find out all the neighbors of a given node:General cases ?Worst case ?☞ Good for sparse graphs.CS 310 Graphs, Page 14'&$%• Edge sets☞ Space consumption depends on the “density” of the graph.General cases ?Worst case ?☞ Time to add/remove edges or to check if two vertices areconnected:General cases ?Worst case ?☞ Time to find out all the neighbors of a given node:General cases ?Worst case ?☞ Performance is stable across wildly different graphs.☞ Difficult to implement due to the involvement of advancedtree structures.CS 310 Graphs, Page 15'&$%Implementing Digraphs Using Adjacency Liststruct ListNode {int vertex_id, ListNode* next};typedef ListNode* ListNode_ptr;class Digraph {protected:ListNode **neighbors_list; // a ListNode* array whose// size determined by max_sizestring* labels; // a string array whose size determined by// max_sizeint vertex_count;int max_size; // max_size not const; it can vary// from graph to graphCS 310 Graphs, Page 16'&$%public:Digraph (int n) {vertex_count=0;max_size=n;labels=new string[max_size];neighbors_list = new ListNode_ptr[max_size];}~Digraph();void add_vertex (const string& label);void add_edge (int u, int v);void remove_edge (int u, int v);bool is_connected (int u, int v); // return true if// edge (u,v) exists.string& operator[] (int i) {return labels[i];}};CS 310 Graphs, Page 17'&$%void Digraph::add_vertex (const string& label) {int new_vertex_number = vertex_count++;neighbors_list[new_vertex_number] = NULL;labels[new_vertex_number] = label;}void Digraph::add_edge (int u, int v) {if (is_connected (u,v)) return;ListNode* p = new ListNode;p->vertex_id = v;p->next = neighbors_list[u];neighbors_list[u] = p;}CS 310 Graphs, Page 18'&$%bool Digraph::is_connected (int u, int v) {ListNode *p;for (p=neighbors_list[u]; p!=NULL; p=p->next)if (p->vertex_id == v) return true;return false;}bool Digraph::remove_edge (int u, int v) {ListNode **p;for (p=&neighbors_list[u]; *p!=NULL; p=&((*p)->next))if ((*p)->vertex_id == v) {*p = (*p)->next;return true;}return false;}CS 310 Graphs, Page 19'&$%To build the graph shown in page 1,Digraph g(20); // max node number = 20g.add_vertex (’A’); // vertex A numbered 0g.add_vertex (’B’); // vertex A numbered 1g.add_vertex (’C’); // vertex A numbered 2g.add_vertex (’D’); // vertex A numbered 3g.add_vertex (’E’); // vertex A numbered