Graph Traversal

9 Key excerpts on "Graph Traversal"

• 

  eBook - PDF

  Data Structure Practice

  for Collegiate Programming Contests and Education

  • Yonghui Wu, Jiande Wang(Authors)
  • 2016(Publication Date)
  • CRC Press

    (Publisher)

  337 Chapter 11 Applications of Graph Traversal In some applications, all vertices in a graph need to be visited exactly once. Such a process is called Graph Traversal. Tree traversal is a special case of Graph Traversal. Because the structure of a graph is more complex than the structure of a tree, algorithms for Graph Traversal are also more complex than algorithms for tree traversal. In the process of Graph Traversal, each visited vertex should be marked to avoid a vertex being visited more than once. In this chapter, first, two kinds of Graph Traversals, breadth-first search (BFS) and depth-first search (DFS), are introduced. Given a vertex in a graph, all vertices in the connected component containing the vertex can be visited by BFS or DFS. Then, based on BFS and DFS, topological sort and connectivity of undirected graphs are introduced. 11.1 BFS Algorithm Given a graph G ( V , E ) and a source vertex s in G , BFS visits all vertices that can be reached from s layer by layer; and calculates distances from s to all vertices (i.e., numbers of edges from s to these vertices). The distance from s to vertex v d [ v ], v ∈ V , is as follows: d v s v [ ] = -1 if and are not connected the length of the shortest path from to otherwise s v    Initially, d [ s ] = 0, and for v ∈ V – { s }, d [ v ] = –1. The process for BFS is as follows. Every visited vertex u is processed in order: for every vertex v that is adjacent to u and is not visited, that is, ( u , v ) ∈ E and d [ v ] = –1, v will be visited. Because vertex u is the parent or the precursor for vertex v , d [ v ] = d [ u ] + 1. Because the traversal order is based on hierarchy and the traversal is implemented through the first-in, first-out (FIFO) access rule, a queue Q is used to store visited vertices: Initially, source vertex s is added into queue Q , and d [ s ] = 0.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Hands-On Data Structures and Algorithms with Python

  • Dr. Basant Agarwal(Author)
  • 2022(Publication Date)
  • Packt Publishing

    (Publisher)

  We can also iteratively move from one node to another in order to traverse the full graph or part of it. Graph Traversal algorithms are very important in answering many fundamental problems—they can be useful to determine how to get from one vertex to another in a graph, and which path from A node to B node in a graph is better than other paths. For example, Graph Traversal algorithms can be useful in finding out the shortest route from one city to another in a network of cities. In the next section, we will discuss two important Graph Traversal algorithms: breadth-first search (BFS) and depth-first search (DFS). Breadth-first traversal Breadth-first search (BFS) works very similarly to how a level order traversal algorithm works in a tree data structure. The BFS algorithm also works level by level; it starts by visiting the root node at level 0, and then all the nodes at the first level directly connected to the root node are visited at level 1. The level 1 node has a distance of 1 from the root node. After visiting all the nodes at level 1, the level 2 nodes are visited next. Likewise, all the nodes in the graph are traversed level by level until all the nodes are visited. So, breadth-first traversal algorithms work breadthwise in the graph. A queue data structure is used to store the information of vertices that are to be visited in a graph. We begin with the starting node. Firstly, we visit that node, and then we look up all of its neighboring, or adjacent, vertices. We first visit these adjacent vertices one by one, while adding their neighbors to the list of vertices that are to be visited

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures and Algorithms in Python

  • Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
  • 2013(Publication Date)
  • Wiley

    (Publisher)

  This labyrinth was so complex that neither beast nor human could escape it. No human, that is, until the Greek hero, Theseus, with the help of the king’s daughter, Ariadne, decided to implement a Graph Traversal algorithm. Theseus fastened a ball of thread to the door of the labyrinth and unwound it as he traversed the twisting passages in search of the monster. Theseus obviously knew about good algorithm design, for, after finding and defeating the beast, Theseus easily followed the string back out of the labyrinth to the loving arms of Ariadne. Formally, a traversal is a systematic procedure for exploring a graph by exam- ining all of its vertices and edges. A traversal is efficient if it visits all the vertices and edges in time proportional to their number, that is, in linear time. Graph Traversal algorithms are key to answering many fundamental questions about graphs involving the notion of reachability, that is, in determining how to travel from one vertex to another while following paths of a graph. Interesting problems that deal with reachability in an undirected graph G include the following: • Computing a path from vertex u to vertex v, or reporting that no such path exists. • Given a start vertex s of G, computing, for every vertex v of G, a path with the minimum number of edges between s and v, or reporting that no such path exists. • Testing whether G is connected. • Computing a spanning tree of G, if G is connected. • Computing the connected components of G. • Computing a cycle in G, or reporting that G has no cycles. Interesting problems that deal with reachability in a directed graph  G include the following: • Computing a directed path from vertex u to vertex v, or reporting that no such path exists. • Finding all the vertices of  G that are reachable from a given vertex s. • Determine whether  G is acyclic. • Determine whether  G is strongly connected.

  Sign up to read

  Learn more about book
• 

  No longer available |Learn more

  Data Structures and Program Design Using C

  A Self-Teaching Introduction

  • D. Malhotra, N. Malhotra(Authors)
  • 2018(Publication Date)
  • Mercury Learning and Information

    (Publisher)

  486 • DATA STRUCTURES AND PROGRAM DESIGN USING C 12.4 Graph Traversal Techniques In this section, we will discuss various types of techniques to traverse a graph. As we all know, a graph is a collection of nodes and edges. Thus, traversing in a graph is the process of visiting each node and edge in some systematic approach. Therefore, there are two types of standard graph tra- versal techniques, which are: 1. Breadth First Search (BFS) 2. Depth First Search (DFS) So now, we will discuss both of these techniques in detail. 12.4.1 Breadth First Search Breadth first search is a traversal technique that uses the queue as an auxiliary data structure for traversing all member nodes of a graph. In this technique, first we will select any node in the graph as a starting node, and then we will take all the nodes adjacent to the starting node. We will main- tain the same approach for all the other nodes. Also, we will maintain the status of all the traversed/visited nodes in a queue so that no nodes are tra- versed again. Now, let us take a graph and apply BFS to traverse the graph. FIGURE 12.23: A sample graph. Now, we will start the traversal of the graph by taking node A as a start- ing node of the above sample graph. Then, we will traverse all the nodes adjacent to the starting node A. As we can see, B, C, and E are the adjacent nodes of A. So we will traverse these nodes in any order, say E, C, B. So the traversal is: GRAPHS • 487 Now, we will traverse all the nodes adjacent to E. Node C is adjacent to node E. But node C has already been traversed, so we will ignore it and we will move to the next step. Now, we will traverse all the nodes adjacent to node C. As we can see, D is the adjacent node of C. So we will traverse node D and the traversal is: Now, we can see that all the nodes have been traversed and hence, this was the breadth first search traversal by taking node A as a starting node.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures

  Abstraction and Design Using Java

  • Elliot B. Koffman, Paul A. T. Wolfgang(Authors)
  • 2021(Publication Date)
  • Wiley

    (Publisher)

  10.4 Traversals of Graphs 513 Depth-First Search Another way to traverse a graph is depth-first search. In depth-first search, you start at a ver- tex, visit it, and choose one adjacent vertex to visit. Then choose a vertex adjacent to that ver- tex to visit, and so on until you go no further. Then back up and see whether a new vertex (one not previously visited) can be found. In the discussion that follows, we use color to distinguish among three states for a node: being visited (light color), finished visiting (dark color), and not yet visited (white). Initially, of course, all nodes are not yet visited. Note that the light color is used in depth-first search to indicate that a vertex is in the process of being visited, whereas it was used in our discussion of breadth-first search to indicate that the vertex was identified. Example of Depth-First Search Consider the graph shown in Figure 10.18. We can start at any vertex, but for simplicity we will start at 0. The vertices adjacent to 0 are 1, 2, 3, and 4. We mark 0 as being visited (change it to light color; see Figure 10.19(a)). Next we consider 1. We mark 1 as being visited (see Figure 10.19(b)). The vertices adjacent to 1 are 0, 3, and 4. But 0 is being vis- ited, so we recursively apply the algorithm with 3 as the start vertex. We mark 3 as being visited (see Figure 10.19(c)). The vertices adjacent to 3 are 0, 1, and 4. Because 0 and 1 are already being visited, we recursively apply the algorithm with 4 as the start vertex. We mark 4 as being visited (see Figure 10.19(d)). The vertices adjacent to 4 are 0, 1, and 3. All of these are being visited, so we mark 4 as finished (see Figure 10.19(e)) and return from the recursion. Now all of the vertices adjacent to 3 have been visited, so we mark 3 as finished and return from the recursion. Now all of the vertices adjacent to 1 have been visited, so we mark 1 as finished and return from the recursion to the original start vertex, 0.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  C++ Programming

  Program Design Including Data Structures

  • D. Malik(Author)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  Therefore, we must keep track of the vertices that have been visited. We must also traverse the graph from each vertex (that has not been visited) of the graph. This ensures that the entire graph is traversed. The two most common Graph Traversal algorithms are the depth first traversal and breadth first traversal , which are described next. For simplicity, we assume that when a vertex is visited, its index is output. Moreover, each vertex is visited only once. We use the bool array visited to keep track of the visited vertices. Depth First Traversal The depth first traversal is similar to the preorder traversal of a binary tree. The general algorithm is as follows: for each vertex, v, in the graph if v is not visited start the depth first traversal at v Consider the graph G of Figure 20-6. FIGURE 20-6 Directed graph G 0 3 6 4 8 2 5 9 7 1 A depth first ordering of the vertices of the graph G in Figure 20-6 is 0, 1, 4, 3, 2, 5, 7, 8, 6, 9 Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. WCN 02-300 Graph Traversals | 1429 2 0 For the graph of Figure 20-6, the depth first search starts at the vertex 0. After visiting all of the vertices that can be reached starting at the vertex 0, the depth first search starts at the next vertex that is not visited. There is a path from the vertex 0 to every other vertex except the vertices 6 and 9. Therefore, when the depth first search starts at the vertex 0, all of the vertices except 6 and 9 are visited before these vertices. After completing the depth first search that started at the vertex 0, the depth first search starts at the vertex 6 and then at the vertex 9. Note that there is no path from the ver-tex 6 to the vertex 9. Therefore, after completing the depth first search that started at the vertex 6, the depth first search starts at the vertex 9. The general algorithm to do a depth first traversal at a given node , v , is as follows: 1.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Graphs and Networks

  • S. R. Kingan(Author)
  • 2022(Publication Date)
  • Wiley

    (Publisher)

  113 5 Graph Algorithms This chapter introduces graph algorithms, the third major topic in the book along with theory and applications. Graph algorithms is an interdisciplinary area covering both mathematics and computer science. A thorough understanding requires knowing computational complexity (see Appendix C), data structures (see Appendix D), and a programming language in order to implement the algorithms. Nonetheless, it is possible to understand the algorithms and their importance in a more theoretical manner. Generally speaking graph algorithms can be divided into two broad classes: existence algorithms and optimization algorithms. An existence algorithm finds the property, invariant, or object of interest. An optimization algorithm finds the best option among a set of options. Section 5.1 presents two algorithms that determine whether or not a graph is connected; if the graph is connected, the algorithms find a spanning tree. They are examples of existence algorithms. Section 5.2 presents two algorithms for finding a minimum weight spanning tree in a weighted graph. Both use a “greedy strategy.” They are examples of optimization algorithms. Section 5.3 presents Dijkstra’s Shortest Path Algorithm for weighted graphs, another optimization algorithm. Richard Karp introduced the concept of NP-complete in his 1972 paper “Reducibility among combinatorial problems” and highlighted several graph invariants as being intractable (Karp, 1972). As such it is worth studying the problems in this chapter since they have nice and efficient algorithms. 5.1 Traversal Algorithms In this section we examine two algorithms to determine if a graph is connected: Depth-First Search (DFS) and Breadth-First Search (BFS). The input for both DFS and BFS is a graph and a starting vertex (call it s). Both algorithms search the graph by traversing edges from vertex to vertex, building a spanning tree as they proceed.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures using C

  A Practical Approach for Beginners

  • Amol M. Jagtap, Ajit S. Mali(Authors)
  • 2021(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Figure 6.21 , node 2 having three nodes in its linked list, that is, node 2 has out-degree 3. However, node 2 does not present in the linked list means node 2 having zero in-degree. Similarly, count node 4 in the linked list part, which is two in number, so node 4 has in-degree two.

  FIGURE

  6.21

  Sample node.

  However, it is difficult to determine the in-degree of node, but we can easily obtain the out-degree (Figure 6.22 ).

  FIGURE

  6.22

  Node directory representation for directed graph.

  6.2.2.3 Example of Adjacency List Representation for Weighted Graph

  Figure 6.23 shows a weighted graph (Figure 6.24 ), and Figure 6.25 shows its node directory representation for a weighted graph.

  FIGURE

  6.23

  Weighted graph.

  FIGURE

  6.24

  Sample node.

  FIGURE

  6.25

  Node directory representation for a weighted graph.

  6.3 Graph Traversal Techniques (Breadth First Search and Depth First Search)

  Graph Traversal is a procedure used to search for a vertex or node in a graph. The Graph Traversal is also used to decide the order of vertices be visited in the search process only once. A Graph Traversal finds the edges to be used in the search process without creating loops that means using Graph Traversal, we visit all vertices of the graph only at one time without getting into a looping path. The majority of graph problems involve the traversal of a graph. Traversal of a graph means visiting each node exactly once.

  There are two types of Graph Traversal techniques, and they are as follows:

  1. Breadth first search (BFS)
  2. Depth first search (DFS)

  6.3.1 BFS Traversal of a Graph

  6.3.1.1 Basics of BFS

  In the graph, say vertex V1 in a graph will be visited first, then all vertices adjacent to V1 will be traversed suppose adjacent to V1 are (V2 , V3 ) then again from V2

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Data Structures with C Programming

  • Anil Kumar Yadav, Vinod Kumar Yadav(Authors)
  • 2019(Publication Date)
  • Arcler Press

    (Publisher)

  GRAPH 8 CHAPTER CONTENTS 8.1. Introduction .................................................................................... 214 8.2. Definition of Graph ........................................................................ 214 8.3. Representation of Graphs ................................................................ 221 8.4. Graph Traversal ............................................................................... 224 8.5. Spanning Tree ................................................................................. 229 8.6. Shortest Path Problem ..................................................................... 240 8.7. Application Of Graph ..................................................................... 243 Data Structures with C Programming 214 8.1. INTRODUCTION In the earlier chapter, we have discussed a non-linear data structure i.e., Tree. Now we have discussed another non-linear data structure, i.e., Graphs. The tree data structure the main limitation is every tree has a unique root node. If we remove this limitation, we get a more complex data structure is called graphs. In computer science the graphs are used in a wide range, there are many theorems on graphs. The study of graphs in computer science is known as graph theory. One of the first results in graph theory appeared in Leonhard Euler’s paper, on seven bridges of Konigsberg, published in 1736. It’s also regarded as one of the first topological results in geometry; it does not depend on any measurements. In 1945, Gustav Kirchhoff published his Kirchhoff’s circuit laws for calculating the voltage and current in electric circuits. In 1852, Francies Guthrie proposed the four-color problem which asks if it is possible to color, using only four colors, any map of countries in such a way as to prevent two bordering countries from having the same color.

  Sign up to read

  Learn more about book