Graph traversals in Data Structures
Download as PPTX, PDF9 likes8,574 views
Graph traversal techniques are used to search vertices in a graph and determine the order to visit vertices. There are two main techniques: breadth-first search (BFS) and depth-first search (DFS). BFS uses a queue and visits the nearest vertices first, producing a spanning tree. DFS uses a stack and visits vertices by going as deep as possible first, also producing a spanning tree. Both techniques involve marking visited vertices to avoid loops.
1 of 11
Downloaded 78 times
Recommended
Graph in data structure
Graph in data structureAbrish06
油
This document defines and provides examples of graphs and their representations. It discusses:
- Graphs are data structures consisting of nodes and edges connecting nodes.
- Examples of directed and undirected graphs are given.
- Graphs can be represented using adjacency matrices or adjacency lists. Adjacency matrices store connections in a grid and adjacency lists store connections as linked lists.
- Key graph terms are defined such as vertices, edges, paths, and degrees. Properties like connectivity and completeness are also discussed.Graph data structure and algorithms
Graph data structure and algorithmsAnandhasilambarasan D
油
This document discusses graph data structures and algorithms. A graph consists of nodes and edges, where nodes represent entities and edges represent relationships between nodes. There are different types of graphs including undirected, directed, weighted, and cyclic graphs. Graphs can be represented using an adjacency matrix or adjacency list. Graphs are used to model real-world networks and solve problems in areas like social networks, maps, robot path planning, and neural networks.Complexity analysis in Algorithms
Complexity analysis in AlgorithmsDaffodil International University
油
1) The document discusses complexity analysis of algorithms, which involves determining the time efficiency of algorithms by counting the number of basic operations performed based on input size.
2) It covers motivations for complexity analysis, machine independence, and analyzing best, average, and worst case complexities.
3) Simple rules are provided for determining the complexity of code structures like loops, nested loops, if/else statements, and switch cases based on the number of iterations and branching.Data structure - Graph
Data structure - GraphMadhu Bala
油
The document defines and describes various graph concepts and data structures used to represent graphs. It defines a graph as a collection of nodes and edges, and distinguishes between directed and undirected graphs. It then describes common graph terminology like adjacent/incident nodes, subgraphs, paths, cycles, connected/strongly connected components, trees, and degrees. Finally, it discusses two common ways to represent graphs - the adjacency matrix and adjacency list representations, noting their storage requirements and ability to add/remove nodes.Bfs and Dfs
Bfs and DfsMasud Parvaze
油
The document discusses graph traversal algorithms breadth-first search (BFS) and depth-first search (DFS). It provides examples of how BFS and DFS work, including pseudocode for algorithms. It also discusses applications of BFS such as finding shortest paths and detecting bipartitions. Applications of DFS include finding connected components and topological sorting.Tree - Data Structure
Tree - Data StructureAshim Lamichhane
油
This document provides an overview of trees as a non-linear data structure. It begins by discussing how trees are used to represent hierarchical relationships and defines some key tree terminology like root, parent, child, leaf, and subtree. It then explains that a tree consists of nodes connected in a parent-child relationship, with one root node and nodes that may have any number of children. The document also covers tree traversal methods like preorder, inorder, and postorder traversal. It introduces binary trees and binary search trees, and discusses operations on BSTs like search, insert, and delete. Finally, it provides a brief overview of the Huffman algorithm for data compression.single linked list
single linked listSathasivam Rangasamy
油
This document discusses the implementation of a single linked list data structure. It describes the nodes that make up a linked list, which have an info field to store data and a next field pointing to the next node. The document outlines different ways to represent linked lists, including static arrays and dynamic pointers. It also provides algorithms for common linked list operations like traversing, inserting, and deleting nodes from the beginning, end, or a specified position within the list.1.1 binary tree
1.1 binary treeKrish_ver2
油
The document discusses binary trees and their representations and operations. It defines binary trees as trees where each node has at most two child nodes. It also defines complete binary trees as trees where every node has two children except leaf nodes. The document discusses array and linked representations of binary trees and various traversal operations like preorder, inorder and postorder traversals. It also provides code snippets for inserting and deleting nodes from a binary tree.Doubly Linked List
Doubly Linked ListNinad Mankar
油
Each node in a doubly linked list contains two pointers - one pointing to the next node and one pointing to the previous node. This allows traversal in both directions through the list. A doubly linked list supports common operations like insertion and deletion at both ends of the list as well as anywhere in the list by updating the relevant pointer fields of the nodes. While requiring more space per node, doubly linked lists allow easy traversal backwards through the list and reversing of the list.Spanning trees
Spanning treesShareb Ismaeel
油
PPT of Spanning trees
BY Shareb Ismaeel
DEPT. OF INFORMATION TECHNOLOGY
CENTRAL UNIVERSITY OF KASHMIRThreaded Binary Tree
Threaded Binary Treekhabbab_h
油
OVERVIEW:
Introduction
Definition
Example of Threaded BT.
Types & Structure
One-way .
Double-way.
Structure.
Traversal
Algorithm for Traversal
Traversal Example
Inserting
Algorithm for Inserting
Inserting Example
Comparison With Binary Tree
Advantages and Disadvantages
Why Threaded BT are used?
Conclusion
ReferenceGraph representation
Graph representationTech_MX
油
A graph consists of vertices and edges, where vertices represent entities and edges represent relationships between vertices. Graphs can be represented sequentially using matrices like adjacency and incidence matrices, or linked using data structures like adjacency lists. Adjacency matrices allow fast addition/removal of edges but use more memory, while adjacency lists use less memory but are slower to modify. The best representation depends on whether the graph is dense or sparse.DFS and BFS
DFS and BFSsatya parsana
油
This document discusses and provides examples of depth-first search (DFS) and breadth-first search (BFS) algorithms for traversing graphs. It explains that DFS involves recursively exploring all branches of the graph as deep as possible before backtracking, while BFS involves searching the neighbors of the starting node first before moving to the next level. Examples are given showing the step-by-step process of applying DFS and BFS to traverse graphs and mark visited vertices.Breadth First Search & Depth First Search
Breadth First Search & Depth First SearchKevin Jadiya
油
The slides attached here describes how Breadth first search and Depth First Search technique is used in Traversing a graph/tree with Algorithm and simple code snippet.
Dfs presentation
Dfs presentationAlizay Khan
油
The document describes depth-first search (DFS), an algorithm for traversing or searching trees or graphs. It defines DFS, explains the process as visiting nodes by going deeper until reaching the end and then backtracking, provides pseudocode for the algorithm, gives an example on a directed graph, and discusses time complexity (O(V+E)), advantages like linear memory usage, and disadvantages like possible infinite traversal without a cutoff depth.STACKS IN DATASTRUCTURE
STACKS IN DATASTRUCTUREArchie Jamwal
油
This document discusses stacks as a linear data structure. It defines a stack as a last-in, first-out (LIFO) collection where the last item added is the first removed. The core stack operations of push and pop are introduced, along with algorithms to insert, delete, and display items in a stack. Examples of stack applications include reversing strings, checking validity of expressions with nested parentheses, and converting infix notation to postfix.Asymptotic notations
Asymptotic notationsNikhil Sharma
油
The document discusses asymptotic notations that are used to describe the time complexity of algorithms. It introduces big O notation, which describes asymptotic upper bounds, big Omega notation for lower bounds, and big Theta notation for tight bounds. Common time complexities are described such as O(1) for constant time, O(log N) for logarithmic time, and O(N^2) for quadratic time. The notations allow analyzing how efficiently algorithms use resources like time and space as the input size increases.All pair shortest path
All pair shortest pathArafat Hossan
油
The document discusses the all pairs shortest path problem, which aims to find the shortest distance between every pair of vertices in a graph. It explains that the algorithm works by calculating the minimum cost to traverse between nodes using intermediate nodes, according to the equation A_k(i,j)=min{A_{k-1}(i,j), A_{k-1}(i,k), A_{k-1}(k,j)}. An example is provided to illustrate calculating the shortest path between nodes over multiple iterations of the algorithm.sorting and its types
sorting and its typesSIVASHANKARIRAJAN
油
This document discusses different types of sorting algorithms. It describes internal sorting and external sorting, with internal sorting handling all data in memory and external sorting requiring external memory. Bubble sort, selection sort, and insertion sort are briefly explained as examples of sorting methods. Bubble sort works by comparing adjacent elements and swapping if out of order, selection sort finds the minimum element and selection sort inserts elements into the sorted position. Pseudocode and examples are provided for each algorithm.Applications of stack
Applications of stackeShikshak
油
The document discusses applications of stacks, including reversing strings and lists, Polish notation for mathematical expressions, converting between infix, prefix and postfix notations, evaluating postfix and prefix expressions, recursion, and the Tower of Hanoi problem. Recursion involves defining a function in terms of itself, with a stopping condition. Stacks can be used to remove recursion by saving local variables at each step.Linked list
Linked listKalaivaniKS1
油
Linked lists are linear data structures where elements are linked using pointers. The three main types are singly, doubly, and circular linked lists. Linked lists allow dynamic memory allocation and fast insertion/deletion compared to arrays but slower access. A linked list contains nodes, each with a data field and pointer to the next node. Basic operations on linked lists include insertion, deletion, traversal, and search. Doubly linked lists include pointers to both the next and previous nodes.Sorting
SortingAshim Lamichhane
油
The document discusses sorting algorithms. It begins by defining sorting as arranging data in logical order based on a key. It then discusses internal and external sorting methods. For internal sorting, all data fits in memory, while external sorting handles data too large for memory. The document covers stability, efficiency, and time complexity of various sorting algorithms like bubble sort, selection sort, insertion sort, and merge sort. Merge sort uses a divide-and-conquer approach to sort arrays with a time complexity of O(n log n).Hashing
HashingAmar Jukuntla
油
Hashing is a technique used to uniquely identify objects by assigning each object a key, such as a student ID or book ID number. A hash function converts large keys into smaller keys that are used as indices in a hash table, allowing for fast lookup of objects in O(1) time. Collisions, where two different keys hash to the same index, are resolved using techniques like separate chaining or linear probing. Common applications of hashing include databases, caches, and object representation in programming languages.linked list in data structure 
linked list in data structure shameen khan
油
This document discusses data structures and linked lists. It provides definitions and examples of different types of linked lists, including:
- Single linked lists, which contain nodes with a data field and a link to the next node.
- Circular linked lists, where the last node links back to the first node, forming a loop.
- Doubly linked lists, where each node contains links to both the previous and next nodes.
- Operations on linked lists such as insertion, deletion, traversal, and searching are also described.Symbol table in compiler Design
Symbol table in compiler DesignKuppusamy P
油
The document discusses symbol tables, which are data structures used by compilers to track semantic information about identifiers, variables, functions, classes, etc. It provides details on:
- How various compiler phases like lexical analysis, syntax analysis, semantic analysis, code generation utilize and update the symbol table.
- Common data structures used to implement symbol tables like linear lists, hash tables and how they work.
- The information typically stored for different symbols like name, type, scope, memory location etc.
- Organization of symbol tables for block-structured vs non-block structured languages, including using multiple nested tables vs a single global table.Sorting Algorithms
Sorting AlgorithmsPranay Neema
油
This document discusses various sorting algorithms and their complexities. It begins by defining an algorithm and complexity measures like time and space complexity. It then defines sorting and common sorting algorithms like bubble sort, selection sort, insertion sort, quicksort, and mergesort. For each algorithm, it provides a high-level overview of the approach and time complexity. It also covers sorting algorithm concepts like stable and unstable sorting. The document concludes by discussing future directions for sorting algorithms and their applications.B trees in Data Structure
B trees in Data StructureAnuj Modi
油
B-Trees are tree data structures used to store data on disk storage. They allow for efficient retrieval of data compared to binary trees when using disk storage due to reduced height. B-Trees group data into nodes that can have multiple children, reducing the height needed compared to binary trees. Keys are inserted by adding to leaf nodes or splitting nodes and promoting middle keys. Deletion involves removing from leaf nodes, borrowing/promoting keys, or joining nodes.Priority Queue in Data Structure
Priority Queue in Data StructureMeghaj Mallick
油
This document discusses priority queues. It defines a priority queue as a queue where insertion and deletion are based on some priority property. Items with higher priority are removed before lower priority items. There are two main types: ascending priority queues remove the smallest item, while descending priority queues remove the largest item. Priority queues are useful for scheduling jobs in operating systems, where real-time jobs have highest priority and are scheduled first. They are also used in network communication to manage limited bandwidth.graphtraversals.pdf
graphtraversals.pdfSeethaDinesh
油
This document discusses graph traversal techniques for searching graphs. It describes two common techniques: breadth-first search (BFS) and depth-first search (DFS). BFS uses a queue data structure to visit all adjacent vertices of the starting vertex before moving to the next level, producing a spanning tree. DFS uses a stack, visiting all vertices reachable from the starting point before backtracking, also producing a spanning tree. The document outlines the step-by-step process for implementing BFS and DFS on a graph.DFS_New.pptx
DFS_New.pptxsandeep54552
油
DFS uses a stack to perform a depth first traversal of a graph, which produces a spanning tree without loops as the final result. It selects a starting vertex, visits it and its non-visited neighbors, pushing them on the stack until there are no more to visit, then backtracks and pops vertices off the stack until it is empty, producing the final spanning tree.More Related Content
What's hot (20)
Doubly Linked List
Doubly Linked ListNinad Mankar
油
Each node in a doubly linked list contains two pointers - one pointing to the next node and one pointing to the previous node. This allows traversal in both directions through the list. A doubly linked list supports common operations like insertion and deletion at both ends of the list as well as anywhere in the list by updating the relevant pointer fields of the nodes. While requiring more space per node, doubly linked lists allow easy traversal backwards through the list and reversing of the list.Spanning trees
Spanning treesShareb Ismaeel
油
PPT of Spanning trees
BY Shareb Ismaeel
DEPT. OF INFORMATION TECHNOLOGY
CENTRAL UNIVERSITY OF KASHMIRThreaded Binary Tree
Threaded Binary Treekhabbab_h
油
OVERVIEW:
Introduction
Definition
Example of Threaded BT.
Types & Structure
One-way .
Double-way.
Structure.
Traversal
Algorithm for Traversal
Traversal Example
Inserting
Algorithm for Inserting
Inserting Example
Comparison With Binary Tree
Advantages and Disadvantages
Why Threaded BT are used?
Conclusion
ReferenceGraph representation
Graph representationTech_MX
油
A graph consists of vertices and edges, where vertices represent entities and edges represent relationships between vertices. Graphs can be represented sequentially using matrices like adjacency and incidence matrices, or linked using data structures like adjacency lists. Adjacency matrices allow fast addition/removal of edges but use more memory, while adjacency lists use less memory but are slower to modify. The best representation depends on whether the graph is dense or sparse.DFS and BFS
DFS and BFSsatya parsana
油
This document discusses and provides examples of depth-first search (DFS) and breadth-first search (BFS) algorithms for traversing graphs. It explains that DFS involves recursively exploring all branches of the graph as deep as possible before backtracking, while BFS involves searching the neighbors of the starting node first before moving to the next level. Examples are given showing the step-by-step process of applying DFS and BFS to traverse graphs and mark visited vertices.Breadth First Search & Depth First Search
Breadth First Search & Depth First SearchKevin Jadiya
油
The slides attached here describes how Breadth first search and Depth First Search technique is used in Traversing a graph/tree with Algorithm and simple code snippet.
Dfs presentation
Dfs presentationAlizay Khan
油
The document describes depth-first search (DFS), an algorithm for traversing or searching trees or graphs. It defines DFS, explains the process as visiting nodes by going deeper until reaching the end and then backtracking, provides pseudocode for the algorithm, gives an example on a directed graph, and discusses time complexity (O(V+E)), advantages like linear memory usage, and disadvantages like possible infinite traversal without a cutoff depth.STACKS IN DATASTRUCTURE
STACKS IN DATASTRUCTUREArchie Jamwal
油
This document discusses stacks as a linear data structure. It defines a stack as a last-in, first-out (LIFO) collection where the last item added is the first removed. The core stack operations of push and pop are introduced, along with algorithms to insert, delete, and display items in a stack. Examples of stack applications include reversing strings, checking validity of expressions with nested parentheses, and converting infix notation to postfix.Asymptotic notations
Asymptotic notationsNikhil Sharma
油
The document discusses asymptotic notations that are used to describe the time complexity of algorithms. It introduces big O notation, which describes asymptotic upper bounds, big Omega notation for lower bounds, and big Theta notation for tight bounds. Common time complexities are described such as O(1) for constant time, O(log N) for logarithmic time, and O(N^2) for quadratic time. The notations allow analyzing how efficiently algorithms use resources like time and space as the input size increases.All pair shortest path
All pair shortest pathArafat Hossan
油
The document discusses the all pairs shortest path problem, which aims to find the shortest distance between every pair of vertices in a graph. It explains that the algorithm works by calculating the minimum cost to traverse between nodes using intermediate nodes, according to the equation A_k(i,j)=min{A_{k-1}(i,j), A_{k-1}(i,k), A_{k-1}(k,j)}. An example is provided to illustrate calculating the shortest path between nodes over multiple iterations of the algorithm.sorting and its types
sorting and its typesSIVASHANKARIRAJAN
油
This document discusses different types of sorting algorithms. It describes internal sorting and external sorting, with internal sorting handling all data in memory and external sorting requiring external memory. Bubble sort, selection sort, and insertion sort are briefly explained as examples of sorting methods. Bubble sort works by comparing adjacent elements and swapping if out of order, selection sort finds the minimum element and selection sort inserts elements into the sorted position. Pseudocode and examples are provided for each algorithm.Applications of stack
Applications of stackeShikshak
油
The document discusses applications of stacks, including reversing strings and lists, Polish notation for mathematical expressions, converting between infix, prefix and postfix notations, evaluating postfix and prefix expressions, recursion, and the Tower of Hanoi problem. Recursion involves defining a function in terms of itself, with a stopping condition. Stacks can be used to remove recursion by saving local variables at each step.Linked list
Linked listKalaivaniKS1
油
Linked lists are linear data structures where elements are linked using pointers. The three main types are singly, doubly, and circular linked lists. Linked lists allow dynamic memory allocation and fast insertion/deletion compared to arrays but slower access. A linked list contains nodes, each with a data field and pointer to the next node. Basic operations on linked lists include insertion, deletion, traversal, and search. Doubly linked lists include pointers to both the next and previous nodes.Sorting
SortingAshim Lamichhane
油
The document discusses sorting algorithms. It begins by defining sorting as arranging data in logical order based on a key. It then discusses internal and external sorting methods. For internal sorting, all data fits in memory, while external sorting handles data too large for memory. The document covers stability, efficiency, and time complexity of various sorting algorithms like bubble sort, selection sort, insertion sort, and merge sort. Merge sort uses a divide-and-conquer approach to sort arrays with a time complexity of O(n log n).Hashing
HashingAmar Jukuntla
油
Hashing is a technique used to uniquely identify objects by assigning each object a key, such as a student ID or book ID number. A hash function converts large keys into smaller keys that are used as indices in a hash table, allowing for fast lookup of objects in O(1) time. Collisions, where two different keys hash to the same index, are resolved using techniques like separate chaining or linear probing. Common applications of hashing include databases, caches, and object representation in programming languages.linked list in data structure
linked list in data structure shameen khan
油
This document discusses data structures and linked lists. It provides definitions and examples of different types of linked lists, including:
- Single linked lists, which contain nodes with a data field and a link to the next node.
- Circular linked lists, where the last node links back to the first node, forming a loop.
- Doubly linked lists, where each node contains links to both the previous and next nodes.
- Operations on linked lists such as insertion, deletion, traversal, and searching are also described.Symbol table in compiler Design
Symbol table in compiler DesignKuppusamy P
油
The document discusses symbol tables, which are data structures used by compilers to track semantic information about identifiers, variables, functions, classes, etc. It provides details on:
- How various compiler phases like lexical analysis, syntax analysis, semantic analysis, code generation utilize and update the symbol table.
- Common data structures used to implement symbol tables like linear lists, hash tables and how they work.
- The information typically stored for different symbols like name, type, scope, memory location etc.
- Organization of symbol tables for block-structured vs non-block structured languages, including using multiple nested tables vs a single global table.Sorting Algorithms
Sorting AlgorithmsPranay Neema
油
This document discusses various sorting algorithms and their complexities. It begins by defining an algorithm and complexity measures like time and space complexity. It then defines sorting and common sorting algorithms like bubble sort, selection sort, insertion sort, quicksort, and mergesort. For each algorithm, it provides a high-level overview of the approach and time complexity. It also covers sorting algorithm concepts like stable and unstable sorting. The document concludes by discussing future directions for sorting algorithms and their applications.B trees in Data Structure
B trees in Data StructureAnuj Modi
油
B-Trees are tree data structures used to store data on disk storage. They allow for efficient retrieval of data compared to binary trees when using disk storage due to reduced height. B-Trees group data into nodes that can have multiple children, reducing the height needed compared to binary trees. Keys are inserted by adding to leaf nodes or splitting nodes and promoting middle keys. Deletion involves removing from leaf nodes, borrowing/promoting keys, or joining nodes.Priority Queue in Data Structure
Priority Queue in Data StructureMeghaj Mallick
油
This document discusses priority queues. It defines a priority queue as a queue where insertion and deletion are based on some priority property. Items with higher priority are removed before lower priority items. There are two main types: ascending priority queues remove the smallest item, while descending priority queues remove the largest item. Priority queues are useful for scheduling jobs in operating systems, where real-time jobs have highest priority and are scheduled first. They are also used in network communication to manage limited bandwidth.Similar to Graph traversals in Data Structures (20)
graphtraversals.pdf
graphtraversals.pdfSeethaDinesh
油
This document discusses graph traversal techniques for searching graphs. It describes two common techniques: breadth-first search (BFS) and depth-first search (DFS). BFS uses a queue data structure to visit all adjacent vertices of the starting vertex before moving to the next level, producing a spanning tree. DFS uses a stack, visiting all vertices reachable from the starting point before backtracking, also producing a spanning tree. The document outlines the step-by-step process for implementing BFS and DFS on a graph.DFS_New.pptx
DFS_New.pptxsandeep54552
油
DFS uses a stack to perform a depth first traversal of a graph, which produces a spanning tree without loops as the final result. It selects a starting vertex, visits it and its non-visited neighbors, pushing them on the stack until there are no more to visit, then backtracks and pops vertices off the stack until it is empty, producing the final spanning tree.Bfs new
Bfs newsandeep54552
油
BFS uses a queue to perform a traversal of a graph, visiting all adjacent unvisited vertices of the vertex at the front of the queue and adding them to the queue. This produces a spanning tree without loops as the final result, where each vertex in the graph can be reached from the starting vertex without cycles. The queue, which has a maximum size of the total number of vertices, ensures a layer-by-layer search of the graph from the starting vertex out is performed.Bfs new
Bfs newsandeep54552
油
BFS uses a queue to perform a traversal of a graph, visiting all adjacent unvisited vertices of the vertex at the front of the queue and adding them to the queue. This produces a spanning tree without loops as the final result, where each vertex in the graph can be reached from the starting vertex without cycles. The queue, which has a maximum size of the total number of vertices, ensures a breadth-first search where all vertices at each level are explored before moving to the next level out.bfs tree searching ,sortingUntitled presentation.pptx
bfs tree searching ,sortingUntitled presentation.pptxsaurabhpandey679381
油
Breadth First Search (BFS) is a graph traversal algorithm that explores all vertices in a graph level-by-level starting from a specified starting vertex. It uses a queue data structure to keep track of vertices to be explored. The time complexity of BFS is O(V+E) where V is the number of vertices and E is the number of edges, as it visits all vertices and edges in the worst case. The space complexity is O(V) as all vertices may need to be stored in the queue.
graph representation.pdf
graph representation.pdfamitbhachne
油
A graph is a data structure consisting of vertices and edges. Graphs are used to represent real-world networks like social networks and road maps. There are two main representations of graphs: adjacency matrix and adjacency list. Adjacency matrix uses a 2D array to store edge information while adjacency list uses an array of lists. Graph traversal algorithms like depth-first search and breadth-first search are used to search graphs in a systematic way without loops.Unit VI - Graphs.ppt
Unit VI - Graphs.pptHODElex
油
The document defines key concepts related to graphs, including types of graphs (directed, undirected, weighted, unweighted), graph terminology (vertex, edge, path, cycle), representations of graphs (adjacency matrix, adjacency list), and algorithms for traversing graphs (breadth-first search, depth-first search). It also discusses minimum spanning trees, spanning tree properties, and algorithms for finding minimum spanning trees like Kruskal's and Prim's algorithms.Data structure note
Data structure noteMuhammad Nawaz
油
This document discusses different graph traversal algorithms and spanning trees. It explains that breadth-first search (BFS) traverses a graph level-by-level using a queue, while depth-first search (DFS) traverses as far as possible from the root node using a stack. A spanning tree connects all nodes of a graph using the minimum number of edges without cycles. Minimum spanning trees for weighted graphs use algorithms like Kruskal's and Prim's that apply greedy approaches.Bfs and dfs
Bfs and dfsutsav patel
油
The document discusses Breadth First Search (BFS) and Depth First Search (DFS) graph traversal algorithms. BFS uses a queue data structure and explores neighbor nodes level-wise, starting from a source node. Its time and space complexity is O(V+E) and O(V) respectively. DFS uses a stack and explores nodes by going deeper first until reaching a dead end, then backtracks. Its complexity is O(V+E) for adjacency lists and O(V^2) for adjacency matrices. Both algorithms are used for path finding, cycle detection and other graph applications.Graphs
GraphsKomalPaliwal3
油
The document discusses graphs and graph algorithms. It defines what a graph is - a non-linear data structure consisting of vertices connected by edges. It describes different graph representations like adjacency matrix, incidence matrix and adjacency list. It also explains graph traversal algorithms like depth-first search and breadth-first search. Finally, it covers minimum spanning tree algorithms like Kruskal's and Prim's algorithms for finding minimum cost spanning trees in graphs.Ai1.pdf
Ai1.pdfkaxeca4096
油
The document discusses the Breadth-First Search (BFS) algorithm. It begins with an introduction to graph traversal and explains that BFS is a graph traversal technique that explores all nodes layer-by-layer from a starting node. It then provides an example of applying BFS to a binary tree, showing the steps of selecting a starting node, inserting its children into a queue, extracting nodes from the queue and inserting their children, and repeating until the queue is empty. The document concludes by listing some applications of BFS such as for web crawlers, GPS navigation, and finding the minimum spanning tree of an unweighted graph.
Lecture # 02-Search Algorithms11111.pptx
Lecture # 02-Search Algorithms11111.pptxTheSmartSolverAcadem
油
Artificial Intelligence based Search AlgorithmsSearch Algorithms in AI.pptx
Search Algorithms in AI.pptxDr.Shweta
油
Search algorithms are fundamental to artificial intelligence (AI) because they play a crucial role in solving complex problems, making decisions, and finding optimal solutions in various AI applications.bfs and dfs (data structures).pptx
bfs and dfs (data structures).pptxssuser55cbdb
油
This document summarizes breadth-first search (BFS) and depth-first search (DFS) graph traversal algorithms. It discusses that BFS visits all adjacent nodes of the starting node before moving deeper, using a queue data structure, while DFS explores each branch fully before backtracking, using a stack. The document also compares BFS and DFS, noting that BFS finds the shortest path but uses more memory, while DFS uses less memory but does not guarantee the shortest path. It provides examples of applications for each algorithm such as search engines for BFS and job scheduling for DFS.Presentation on Breadth First Search (BFS)
Presentation on Breadth First Search (BFS)Shuvongkor Barman
油
This document contains a presentation on Breadth-First Search (BFS) given to students. The presentation includes:
- An introduction to BFS and its inventor Konrad Zuse.
- Definitions of key terms like graph, tree, vertex, level-order traversal.
- An example visualization of BFS on a graph with 14 steps.
- Pseudocode and a Java program implementing BFS.
- Applications of BFS like shortest paths, social networks, web crawlers.
- The time and space complexity of BFS is O(V+E) and O(V).
- A conclusion that BFS is an important algorithm that traversesppt 1.pptx
ppt 1.pptxShasidharaniD
油
Graphs are non-linear data structures containing vertices (nodes) connected by edges. A graph G is represented as G = (V, E) where V is the set of vertices and E is the set of edges. Edges can be directed, undirected, or weighted. Graphs are used to model real-world networks and relationships. Common graph algorithms include traversal (depth-first search and breadth-first search), topological sorting of directed acyclic graphs, and finding single-source shortest paths (Dijkstra's algorithm).LAB7_FILS_DSA_graphs_datastructures.pptx
LAB7_FILS_DSA_graphs_datastructures.pptxionutionescuionut
油
This document discusses graphs and graph algorithms. It introduces graphs and their representations using adjacency matrices and linked lists. It covers graph searching algorithms like depth-first search (DFS) and breadth-first search (BFS). It provides pseudocode for DFS and BFS implementations and discusses applications like topological sorting and finding shortest paths. It also mentions other graph searching algorithms and modeling problems as graphs. Finally, it provides exercises on implementing DFS, BFS and checking if a graph is bipartite using the adjacency matrix representation.Data structure
Data structurelalithambiga kamaraj
油
Breadth First Search (BFS) and Depth First Search (DFS) are two graph traversal algorithms. BFS uses a queue to visit all neighbor nodes at the present depth prior to moving to the next depth level, while DFS uses a stack to explore as far as possible along each branch before backtracking. The document provides pseudocode for BFS and DFS algorithms and explains their process through examples of traversing graphs from a starting node.Recently uploaded (20)
Analysis of Conf File Parameters in Odoo 17
Analysis of Conf File Parameters in Odoo 17Celine George
油
In this slide, we will analyse the configuration file parameters in Odoo 17. The odoo.conf file plays a pivotal role in configuring and managing the Odoo 17 server. It contains essential parameters that control database connections, server behaviour, logging, and performance settings.
Antifungal drug are those medicine that kill or stop the growth of fungi.
Antifungal drug are those medicine that kill or stop the growth of fungi.AbuShahma9
油
Antifungal drugs are those medicine that kil aur stop the growth of fungi.
These are also called as anti myotic agent.
So, fungal infection are disease caused by fungus, dryness of skin or irritation cause of fungal infection.
Fungal infection are most common on your skin or nails.
They are treated with antifungal drugs.URINE SPECIMEN COLLECTION AND HANDLING CLASS 1 FOR ALL PARAMEDICAL OR CLINICA...
URINE SPECIMEN COLLECTION AND HANDLING CLASS 1 FOR ALL PARAMEDICAL OR CLINICA...Prabhakar Singh Patel
油
1. Urine analysis provides important information about renal and metabolic function through physical, chemical, and microscopic examination of urine samples.
2. Proper collection, preservation and timely testing of urine samples is necessary to obtain accurate results and detect abnormalities that can indicate underlying diseases.
3. Introduction to Systematic Reviews - Prof Ejaz Khan
Introduction to Systematic Reviews - Prof Ejaz KhanSystematic Reviews Network (SRN)
油
A Systematic Review:
Provides a clear and transparent process
Facilitates efficient integration of information for rational decision
making
Demonstrates where the effects of health care are consistent and
where they do vary
Minimizes bias (systematic errors) and reduce chance effects
Can be readily updated, as needed.
Meta-analysis can provide more precise estimates than individual
studies
Allows decisions based on evidence , whole of it and not partialConrad "Accessibility Essentials: Introductory Seminar"
Conrad "Accessibility Essentials: Introductory Seminar"National Information Standards Organization (NISO)
油
This presentation was provided by Lettie Conrad of LibLynx and San Jos辿 University during the initial session of the NISO training series "Accessibility Essentials." Session One: The Introductory Seminar was held April 3, 2025.Developing Topic and Research Question for Systematic Reviews - Emmanuel Ekpor
Developing Topic and Research Question for Systematic Reviews - Emmanuel EkporSystematic Reviews Network (SRN)
油
The topic and research question forms the foundation of the entire systematic review.
A poorly defined topic/question leads to:
Unfocused search strategy
Irrelevant studies
Weak synthesis and conclusions
McElaney "What is inclusive publishing and why do we care about accessibility...
McElaney "What is inclusive publishing and why do we care about accessibility...National Information Standards Organization (NISO)
油
This presentation was provided by Jack McElaney of Microassist during the initial session of the NISO training series "Accessibility Essentials." Session One: The Introductory Seminar was held April 3, 2025.
Enhancing SoTL through Generative AI -- Opportunities and Ethical Considerati...
Enhancing SoTL through Generative AI -- Opportunities and Ethical Considerati...Sue Beckingham
油
This presentation explores the role of generative AI (GenAI) in enhancing the Scholarship of Teaching and Learning (SoTL), using Feltens five principles of good practice as a guiding framework. As educators within higher education institutions increasingly integrate GenAI into teaching and research, it is vital to consider how these tools can support scholarly inquiry into student learning, while remaining contextually grounded, methodologically rigorous, collaborative, and appropriately public.
Through practical examples and case-based scenarios, the session demonstrates how generative GenAI can assist in analysing critical reflection of current practice, enhancing teaching approaches and learning materials, supporting SoTL research design, fostering student partnerships, and amplifying the reach of scholarly outputs. Attendees will gain insights into ethical considerations, opportunities, and limitations of GenAI in SoTL, as well as ideas for integrating GenAI tools into their own scholarly teaching practices. The session invites critical reflection and dialogue about the responsible use of GenAI to enhance teaching, learning, and scholarly impact.
"The Write Path: Navigating Research Writing, Publication, and Professional G...
"The Write Path: Navigating Research Writing, Publication, and Professional G...neelottama
油
To understand the meaning of publication
IB-Unit-4 BBA BVIMR 2022 Syllabus_watermark.pdf
IB-Unit-4 BBA BVIMR 2022 Syllabus_watermark.pdfDr. Mahtab Alam
油
International Business BBA 4 as per Syllabus CBCS 2022 of Bharati Vidyapeeth (Deemed to be University)Strategic Corporate Social Responsibility: Sustainable Value Creation Fourth
Strategic Corporate Social Responsibility: Sustainable Value Creation Fourthkeileyrazawi
油
Strategic Corporate Social Responsibility: Sustainable Value Creation Fourth
Strategic Corporate Social Responsibility: Sustainable Value Creation Fourth
Strategic Corporate Social Responsibility: Sustainable Value Creation Fourth
10.socialorganisationandsocialsystem .pptx
10.socialorganisationandsocialsystem .pptxVivek Bhattji
油
SOCIAL ORGANIATION & SOCIAL DISORGANIZATION
APPLIED SOCIOLOGY Anti-Viral Agents.pptx Medicinal Chemistry III, B Pharm SEM VI
Anti-Viral Agents.pptx Medicinal Chemistry III, B Pharm SEM VISamruddhi Khonde
油
Antiviral agents are crucial in combating viral infections, causing a variety of diseases from mild to life-threatening. Developed through medicinal chemistry, these drugs target viral structures and processes while minimizing harm to host cells. Viruses are classified into DNA and RNA viruses, with each replicating through distinct mechanisms. Treatments for herpesviruses involve nucleoside analogs like acyclovir and valacyclovir, which inhibit the viral DNA polymerase. Influenza is managed with neuraminidase inhibitors like oseltamivir and zanamivir, which prevent the release of new viral particles. HIV is treated with a combination of antiretroviral drugs targeting various stages of the viral life cycle. Hepatitis B and C are treated with different strategies, with nucleoside analogs like lamivudine inhibiting viral replication and direct-acting antivirals targeting the viral RNA polymerase and other key proteins.
Antiviral agents are designed based on their mechanisms of action, with several categories including nucleoside and nucleotide analogs, protease inhibitors, neuraminidase inhibitors, reverse transcriptase inhibitors, and integrase inhibitors. The design of these agents often relies on understanding the structure-activity relationship (SAR), which involves modifying the chemical structure of compounds to enhance efficacy, selectivity, and bioavailability while reducing side effects. Despite their success, challenges such as drug resistance, viral mutation, and the need for long-term therapy remain.Test Bank Pharmacology 3rd Edition Brenner Stevens
Test Bank Pharmacology 3rd Edition Brenner Stevensevakimworwa38
油
Test Bank Pharmacology 3rd Edition Brenner Stevens
Test Bank Pharmacology 3rd Edition Brenner Stevens
Test Bank Pharmacology 3rd Edition Brenner StevensYSPH VMOC Special Report - Measles Outbreak Southwest US 4-6-2025 ver 5.pptx
YSPH VMOC Special Report - Measles Outbreak Southwest US 4-6-2025 ver 5.pptxYale School of Public Health - The Virtual Medical Operations Center (VMOC)
油
A measles outbreak originating in West Texas has been linked to confirmed cases in New Mexico, with additional cases reported in Oklahoma and Kansas. 58 individuals have required hospitalization, and 3 deaths, 2 children in Texas and 1 adult in New Mexico. These fatalities mark the first measles-related deaths in the United States since 2015 and the first pediatric measles death since 2003. The YSPH The Virtual Medical Operations Center Briefs (VMOC) were created as a service-learning project by faculty and graduate students at the Yale School of Public Health in response to the 2010 Haiti Earthquake. Each year, the VMOC Briefs are produced by students enrolled in Environmental Health Science Course 581 - Public Health Emergencies: Disaster Planning and Response. These briefs compile diverse information sources including status reports, maps, news articles, and web content into a single, easily digestible document that can be widely shared and used interactively.Key features of this report include:
- Comprehensive Overview: Provides situation updates, maps, relevant news, and web resources.
- Accessibility: Designed for easy reading, wide distribution, and interactive use.
- Collaboration: The unlocked" format enables other responders to share, copy, and adapt it seamlessly.
The students learn by doing, quickly discovering how and where to find critical油information and presenting油it in an easily understood manner.油油URINE SPECIMEN COLLECTION AND HANDLING CLASS 1 FOR ALL PARAMEDICAL OR CLINICA...
URINE SPECIMEN COLLECTION AND HANDLING CLASS 1 FOR ALL PARAMEDICAL OR CLINICA...Prabhakar Singh Patel
油
Conrad "Accessibility Essentials: Introductory Seminar"
Conrad "Accessibility Essentials: Introductory Seminar"National Information Standards Organization (NISO)
油
Developing Topic and Research Question for Systematic Reviews - Emmanuel Ekpor
Developing Topic and Research Question for Systematic Reviews - Emmanuel EkporSystematic Reviews Network (SRN)
油
McElaney "What is inclusive publishing and why do we care about accessibility...
McElaney "What is inclusive publishing and why do we care about accessibility...National Information Standards Organization (NISO)
油
YSPH VMOC Special Report - Measles Outbreak Southwest US 4-6-2025 ver 5.pptx
YSPH VMOC Special Report - Measles Outbreak Southwest US 4-6-2025 ver 5.pptxYale School of Public Health - The Virtual Medical Operations Center (VMOC)
油
Graph traversals in Data Structures
- 1. PRESENTED BY D.ANANDHASILAMBARASAN KIT - CBE GRAPH TRAVERSALS IN DATA STRUCTURE
- 2. GRAPH TRAVERSALS Graph traversal is technique used for searching a vertex in a graph. The graph traversal is also used to decide the order of vertices to be visit in the search process. 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 graph without getting into looping path. There are two graph traversal techniques and they are as follows... BFS (breadth first search) DFS (depth first search)
- 3. BFS (Breadth First Search) BFS traversal of a graph, produces a spanning tree as final result. Spanning tree is a graph without any loops. We use queue data structure with maximum size of total number of vertices in the graph to implement BFS traversal of a graph. We use the following steps to implement BFS traversal. Step 1: Define a queue of size total number of vertices in the graph. Step 2: Select any vertex as starting point for traversal. Visit that vertex and insert it into the queue.
- 4. Step 3: Visit all the adjacent vertices of the vertex which is at front of the queue which is not visited and insert them into the queue. Step 4: When there is no new vertex to be visit from the vertex at front of the queue then delete that vertex from the queue. Step 5: Repeat step 3 and 4 until queue becomes empty. Step 6: When queue becomes empty, then produce final spanning tree by removing unused edges from the graph.
- 7. DFS (DEPTH FIRST SEARCH) DFS traversal of a graph, produces a spanning tree as final result. Spanning tree is a graph without any loops. We use stack data structure with maximum size of total number of vertices in the graph to implement DFS traversal of a graph. We use the following steps to implement DFS traversal... Step 1: define a stack of size total number of vertices in the graph. Step 2: select any vertex as starting point for traversal. Visit that vertex and push it on to the stack.
- 8. Step 3: visit any one of the adjacent vertex of the vertex which is at top of the stack which is not visited and push it on to the stack. Step 4: repeat step 3 until there are no new vertex to be visit from the vertex on top of the stack. Step 5: when there is no new vertex to be visit then use back tracking and pop one vertex from the stack. Step 6: repeat steps 3, 4 and 5 until stack becomes empty. Step 7: when stack becomes empty, then produce final spanning tree by removing unused edges from the graph. Back tracking is coming back to the vertex from which we came to current vertex.