Udemy
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
Turn what you know into an opportunity and reach millions around the world.
Learn More
Your cart is empty.
Keep shopping
Graph Theory and Algorithms Implementation
Rating: 5.0 out of 5(1 rating)
12 students

Graph Theory and Algorithms Implementation

Implement Graphs important Algorithms like DFS, BFS, Kruskals ,Prims and Dijastra's Algorithms in C++
Created byKunal Gupta
Last updated 6/2021
English
English [Auto],

What you'll learn

  • Thorough Understanding about Graph Algorithms .
  • Depth First Search and Breadth First Search.
  • From scratch Implementation of DFS and BFS Algorithms.
  • From scratch Implementation of Important algorithms like Kruskals, PRims and Dijastra's Algorithm
  • Spanning Trees and MST

Course content

4 sections • 19 lectures • 4h 39m total length

  • Introduction to Graphs17:39

    Explore graphs by examining vertices and edges, learn how connectivity and paths model city networks and roads, and understand reachability and degree concepts.

  • Graph Implementation7:51

    Explore graph concepts and implement graphs using adjacency matrices. Encode edges with boolean values, where 1 marks an edge and 0 indicates no edge, then analyze directed connections between nodes.

  • Introduction to DFS and BFS8:44

    Explore dfs and bfs on a graph, printing vertices and their connected children through depth-first and level-order traversal to reveal depth versus level exploration.

  • Source Codes .From here we will start implementing Codes of Different Algorithms0:03
  • CODE of Depth First Search25:19

    Learn to implement depth-first search on graphs using an adjacency matrix. Start from a chosen vertex, track visited nodes, and print the DFS order as you traverse edges.

  • Important Part of Depth First Search9:13

    Demonstrate depth-first search on a graph using a visited array to identify connected components and print the visitation order, starting indices at zero.

  • CODE of Breadth First Search23:34

    Implement breadth-first search on graphs using a queue to visit vertices level by level, marking visited nodes to avoid repeats and printing as you go.

  • Find Path IN A GRAPH19:34

    Find a path from a start vertex to a target in a graph by exploring adjacent vertices, tracking visited nodes, and returning the path via DFS.

  • Directed Graphs and Weighted Graphs5:56

    Explore directed graphs and weighted graphs; assign edge weights representing distances between cities to model travel costs, and analyze reachability and weighted connections using a simple example.

  • Spanning Trees and MST Introduction9:22

    This lecture introduces spanning trees and the minimum spanning tree, showing how a connected acyclic graph connects all vertices with minimal edge weight and outlining MST basics.

Requirements

  • Programming Knowledge in C++

Description

Graphs are used to solve many real-life problems. Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network. Graphs are also used in social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a vertex(or node). Each node is a structure and contains information like person id, name, gender, locale etc.

We are going to start our discussion by looking at the basic terms of graph theory and them jump on to discuss graph theory related algorithms and then implement those with c++. Following are the types of algorithms we are going to discuss in this course.

In this Course we shall Implement many Importants Algorithms like DFS ,BFS, Kruskals, PRims and Dijastra's Algorithms.

We shall understand how to find path in a given graph ,Directed Graphs ,Spanning Trees ,Minimum spanning trees etc.

Minimal Spanning Tree

A spanning tree whose sum of weight (or length) of all its edges is less than all other possible spanning tree of graph G is known as a minimal spanning tree or minimum cost spanning tree.

To implement the minimum cost-spanning tree, the following two methods are used −

  • Prim’s Algorithm

  • Kruskal’s Algorithm

Dijkstra’s algorithm is very similar to Prim’s algorithm for minimum spanning tree. Like Prim’s MST, we generate a SPT (shortest path tree) with given source as root. We maintain two sets, one set contains vertices included in shortest path tree, other set includes vertices not yet included in shortest path tree. At every step of the algorithm, we find a vertex which is in the other set (set of not yet included) and has a minimum distance from the source.



Who this course is for:

  • Any C++ programmer who wants to learn Graph Important Algorithms
  • Who wants to learn how to implement important algorithms like DFS and BFS in Graphs
  • Who wants to learn how to Implement algorithms like Kruskals, PRims and Dijastra's Algorithm in Graphs

Report abuse