Graph Algorithms from edX

If you have ever used a navigation service to find the optimal route and estimate time to destination, you've used algorithms on graphs.

Graphs arise in various real-world situations, as there are road networks, water and electricity supply networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect set of computers into a network or efficient algorithm to automatically find communities and opinion leaders in Facebook, you're going to work with graphs and algorithms on graphs.

In this course, part of the Algorithms and Data Structures MicroMasters program, you will learn what a graph is and its most important properties. You’ll learn several ways to traverse graphs and how you can do useful things while traversing the graph in some order. We will also talk about shortest paths algorithms. We will finish with minimum spanning trees, which are used to plan road, telephone and computer networks and also find applications in clustering and approximate algorithms.

What's inside

Learning objectives

Graph exploration and decomposition into connected components
Shortest paths algorithms, including breadth-first search, dijkstra’s algorithm and bellman-ford algorithm

Minimum spanning tree algorithms

Graph exploration and decomposition into connected components
Shortest paths algorithms, including breadth-first search, dijkstra’s algorithm and bellman-ford algorithm
Minimum spanning tree algorithms

Syllabus

Modules 1 and 2: Decomposition of GraphsGraphs arise in various real-world situations as there are road networks, computer networks and, most recently, social networks! If you're looking for the fastest time to get to work, cheapest way to connect set of computers into a network or efficient algorithm to automatically find communities and opinion leaders hot in Facebook, you're going to work with graphs and algorithms on graphs. In this module, you will learn ways to represent a graph as well as basic algorithms for decomposing graphs into parts. In the programming assignment of this module, you will apply the algorithms that you’ve learned to implement efficient programs for exploring mazes, analyzing Computer Science curriculum, and analyzing road networks. In the first week of the module, we focus on undirected graphs.

Modules 3 and 4: Shortest PathsIn this module you will study algorithms for finding Shortest Paths in Graphs. These algorithms have lots of applications. When you launch a navigation app on your smartphone like Google Maps or Yandex.Navi, it uses these algorithms to find you the fastest route from work to home, from home to school, etc. When you search for airplane tickets, these algorithms are used to find a route with the minimum number of plane changes. Unexpectedly, these algorithms can also be used to determine the optimal way to do currency exchange, sometimes allowing to earn huge profit! We will cover all these applications, and you will learn Breadth-First Search, Dijkstra's Algorithm and Bellman-Ford Algorithm. These algorithms are efficient and lay the foundation for even more efficient algorithms which you will learn and implement in the Shortest Paths Capstone Project to find best routes on real maps of cities and countries, find distances between people in Social Networks. In the end you will be able to find Shortest Paths efficiently in any Graph.

Module 5: Minimum Spanning TreesIn this module, we study the minimum spanning tree problem. We will cover two elegant greedy algorithms for this problem: the first one is due to Kruskal and uses the disjoint sets data structure, the second one is due to Prim and uses the priority queue data structure. In the programming assignment for this module you will be computing an optimal way of building roads between cities and an optimal way of partitioning a given set of objects into clusters (a fundamental problem in data mining).

Module 6: Flows in NetworksNetwork flows show up in many real-world situations in which a good needs to be transported across a network with limited capacity. You can see it when shipping goods across highways and routing packets across the internet. In this unit, we will discuss the mathematical underpinnings of network flows and some important flow algorithms. We will also give some surprising examples on seemingly unrelated problems that can be solved with our knowledge of network flows.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Teaches algorithms for finding shortest paths, which is a valuable skill in many industries as well as in academia

Taught by recognized experts in algorithms, including Alexander S. Kulikov, Michael Levin, and Daniel Kane

Develops minimum spanning trees, a fundamental data structure that is highly relevant to a variety of applications in computer science

Requires no prior knowledge of algorithms, making it accessible to beginners

Provides hands-on programming assignments that allow learners to apply the algorithms they learn to real-world problems

Covers advanced topics such as flows in networks, which are relevant to areas such as transportation and logistics

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Graph Algorithms with these activities:

Review Graphs

Show steps

Start by reviewing the basics of graphs and data structures before taking this course to strengthen your understanding and knowledge

Browse courses on Graph

Show steps

Read through lecture notes and textbook sections on graphs and data structures
Complete practice problems and exercises on graphs and data structures

Algorithms, 4th Edition

Show steps

Review the textbook to supplement your learning of algorithms and data structures, providing a broader perspective on the topics covered in the course

View Introduction to Programming in Java: An... on Amazon

Show steps

Read through relevant chapters and sections on graphs and algorithms
Solve practice problems and exercises from the book

Study Group

Show steps

Join a study group to discuss course concepts, exchange ideas, and enhance your understanding through collaborative learning

Show steps

Find or create a study group with fellow students
Set regular meeting times and discuss assigned topics

Five other activities

Expand to see all activities and additional details

Show all eight activities

Dijkstra's Tutorial

Show steps

Follow a tutorial to enhance your understanding of Dijkstra's algorithm for finding the shortest path in a graph, as covered in Module 3

Show steps

Find a tutorial that explains Dijkstra's algorithm in detail
Follow the tutorial steps to implement the algorithm in your preferred programming language

LeetCode Practice

Show steps

Enhance your problem-solving skills by completing challenges on LeetCode related to graph algorithms, such as finding shortest paths and minimum spanning trees

Show steps

Sign up for a LeetCode account
Solve problems tagged with graph algorithms

Maze Solver

Show steps

This course teaches various algorithms for traversing graphs, try implementing a maze solver using these algorithms to test your understanding

Show steps

Design a representation for the maze
Implement a graph traversal algorithm, such as breadth-first search
Validate and test your implementation with different maze configurations

Graph Visualization

Show steps

Create a visual representation of graphs to deepen your understanding of their structure and relationships

Show steps

Choose a graph data structure
Implement functions to add nodes and edges
Develop a visualization algorithm to display the graph

Graph Theory Workshop

Show steps

Attend a workshop to engage with experts in graph theory, learn about advanced concepts, and enhance your practical skills

Show steps

Find and register for a relevant workshop
Actively participate in discussions and exercises

Career center

Learners who complete Graph Algorithms will develop knowledge and skills that may be useful to these careers:

Data Scientist

A Data Scientist knows a great deal about modeling and data analysis, which are skills that can help you solve real problems faster and understand complex systems more quickly. By taking this course, you will learn foundational algorithms and techniques that Data Scientists need in order to succeed.

See salaries and explore the career path for Data Scientist

Data Analyst

Data Analysts must be skilled in data collection, analysis, interpretation, and visualization. The knowledge you'll learn in this course will help you build a foundation for your work as a Data Analyst.

See salaries and explore the career path for Data Analyst

Software Engineer

Software Engineers design, develop, and maintain software. The algorithms and data structures skills you'll learn in this course will give you a leg up in many software development roles.

See salaries and explore the career path for Software Engineer

Business Analyst

A Business Analyst studies and evaluates the structure of an organization and defines business requirements. This course can help you build the skills to perform analysis that allows you to recommend changes and act as a liaison between management and technical staff.

See salaries and explore the career path for Business Analyst

Machine Learning Engineer

Machine Learning Engineers deploy models to increase programmatic efficiency. Your work will help companies stay competitive. This course will help you build foundational knowledge to get you started.

See salaries and explore the career path for Machine Learning Engineer

Quantitative Analyst

As a Quantitative Analyst, you will use statistical and mathematical modeling to solve complex problems on Wall Street or in other fields. This course gives you an edge in these fields.

See salaries and explore the career path for Quantitative Analyst

Actuary

Actuaries combine mathematical and statistical skills to assess financial risk, which makes taking this course a valuable addition to your skillset.

See salaries and explore the career path for Actuary

Operations Research Analyst

Operations Research Analysts apply advanced analytical methods to help organizations make better decisions. Taking this course may help you build foundational skills for this role.

See salaries and explore the career path for Operations Research Analyst

Statistician

Statisticians collect, analyze, interpret, and present data. This course may help you to develop critical thinking skills which can be beneficial for working as a Statistician.

See salaries and explore the career path for Statistician

Data Engineer

Data Engineers build, maintain, and manage data pipelines and databases. Taking this course will help you develop the necessary skills to succeed in this role.

See salaries and explore the career path for Data Engineer

Financial Analyst

Financial Analysts analyze and interpret financial data to make investment recommendations. The mathematical and analytical skills you'll learn in this course with help you build your foundation.

See salaries and explore the career path for Financial Analyst

Market Researcher

Market Researchers study market conditions, customer behavior, and industry trends to help businesses make better decisions. This course may provide some foundational knowledge that can be helpful in this career.

See salaries and explore the career path for Market Researcher

Computer Scientist

Computer Scientists are theoretically inclined individuals who research computing and information technology. This course will help you gain a deeper understanding of computing.

See salaries and explore the career path for Computer Scientist

Mathematician

Mathematicians use logic, reasoning, and symbols to develop and apply mathematical theories. This course may be useful as you work to build the skills you need to succeed as a Mathematician.

See salaries and explore the career path for Mathematician

Economist

Economists study the production, distribution, and consumption of goods and services. This course may be useful as you develop the skills required to be an Economist.

See salaries and explore the career path for Economist