graph algorithms in this we discuss several common problems in graph theory not only are these algorithms useful in practicethey are also interesting because in many real-life applications they are too slow unless careful attention is paid to the choice of data structures we will show several real-life problemswhich can be converted to problems on graphs give algorithms to solve several common graph problems show how the proper choice of data structures can drastically reduce the running time of these algorithms see an important techniqueknown as depth-first searchand show how it can be used to solve several seemingly nontrivial problems in linear time definitions graph (veconsists of set of verticesvand set of edgese each edge is pair (vw)where vw edges are sometimes referred to as arcs if the pair is orderedthen the graph is directed directed graphs are sometimes referred to as digraphs vertex is adjacent to if and only if (vwe in an undirected graph with edge (vw)and hence (wv) is adjacent to and is adjacent to sometimes an edge has third componentknown as either weight or cost path in graph is sequence of vertices wn such that (wi wi+ for < the length of such path is the number of edges on the pathwhich is equal to we allow path from vertex to itselfif this path contains no edgesthen the path length is this is convenient way to define an otherwise special case if the graph contains an edge (vvfrom vertex to itselfthen the path vv is sometimes referred to as loop the graphs we will consider will generally be loopless simple path is path such that all vertices are distinctexcept that the first and last could be the same cycle in directed graph is path of length at least such that wn this cycle is simple if the path is simple for undirected graphswe require that the edges be distinct the logic of these requirements is that the path uvu in an undirected graph should not be considered cyclebecause (uvand (vuare the same edge in directed graphthese are different edgesso it makes sense to call this cycle directed graph is acyclic if it has no cycles directed acyclic graph is sometimes referred to by its abbreviationdag