computing cycle in gor reporting that has no cycles the justification of proposition is based on algorithms that use slightly modified versions of the dfs algorithm as subroutines implementing depth-first search as we have mentioned abovethe data structure we use to represent graph impacts the performance of the dfs algorithm for examplean adjacency list can be used to yield running time of ( mfor traversing graph with vertices and edges using an adjacency matrixon the other handwould result in running time of ( )since each of the calls to the incidentedges method would take (ntime if the graph is densethat isit has close to ( edgesthen the difference between these two choices is minoras they both would run in ( time but if the graph is sparsethat isit has close to (nedgesthen the adjacency matrix approach would be much slower than the adjacency list approach another important implementation detail deals with the way vertices and edges are represented in particularwe need to have way of marking vertices and edges as visited or not there are two simple solutionsbut each has drawbackswe can build our vertex and edge objects to contain an explored fieldwhich can be used by the dfs algorithm for marking this approach is quite simpleand supports constant-time marking and unmarkingbut it assumes that we are designing our graph with dfs in mindwhich will not always be valid furthermorethis approach needlessly restricts dfs to graphs with vertices having an explored field thusif we want generic dfs algorithm that can take any graph as inputthis approach has limitations we can use an auxiliary hash table to store all the explored vertices and edges during the dfs algorithm this scheme is generalin that it does not require any special fields in the positions of the graph but this approach does not achieve worst-case constant time for marking and unmarking of vertices edges insteadsuch hash table only supports the mark (insertand test (findoperations in constant expected time (see section fortunatelythere is middle ground between these two extremes the decorator pattern marking the explored vertices in dfs traversal is an example of the decorator software engineering design pattern this pattern is used to add decorations (also called attributesto existing objects each decoration is identified by key identifying this decoration and by value associated with the key the use of decorations is motivated by the need of some algorithms and data structures to add extra variablesor temporary scratch datato objects that do not normally