離散数学入門#3: 根付き木とBFS（幅優先探索）アルゴリズム

This is one of the lecture videos of the "Introduction to Discrete Mathematics" by Dr Momoko Hayamizu, a module open to all 3rd and 4th-year students of Waseda University, Tokyo, Japan. By her lecture series, students can learn the basics of discrete mathematics and how to use graph-theoretical theorems and algorithms to solve real-world problems.
---------------------------------------------------------------------------------------
This video explains the properties of "rooted trees" with oriented edges and the "breadth-first search algorithm," one of the methods to search graphs. Breadth-first search and depth-first search are two typical methods for exploring graphs, and both are important concepts that help us understand various algorithms for graphs. In this lecture, the breadth-first search algorithm is explained through the concrete problem of "finding the shortest path out of a maze" in order to help students understand how the abstract problem of "graph search" appears in real situations. Let's understand what properties of rooted trees are utilized in the algorithm and become able to escape from any maze in the shortest time!

0:00 Opening
0:46 What is a rooted tree?
2:50 Important Properties of Rooted Trees
4:37 Terms related to rooted trees (parent, child, sibling)
6:08 Terms related to rooted trees (ancestors, descendants)
7:02 Terms related to rooted trees (apex depth, rootstock height)
8:23 Rooted tree terminology (m-branch tree, regular m-branch tree)
9:26 Properties of regular binary binary trees
10:51 Properties of regular m-branch trees
11:31 What is graph search, and how to find the shortest escape route in a maze using breadth-first search (BFS)
20:07 Breadth-first search (BFS) trees

▷ Playlist: List of the videos in this lecture series
離散数学入門 〜グラフ理論の世界にようこそ〜
---------------------------------------------------------------------------------------
Assistant video editor: SK

• #science_technology
• #
• #
• #
• #
• #