|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/learn-graph-algorithms-with-cpp-programming/
课程评论：没有评论
Coursera 课程“图论与算法实现” 总结 本课程旨在介绍图论的基础知识，并通过 C++ 实现相关的经典算法，以解决实际生活中的各种问题。 **课程概览：** Graphs (图) 是一种强大的工具，广泛应用于表示和解决现实世界中的网络问题，例如城市交通 **paths**（路径）、电话网络、电路网络以及社交网络（如 LinkedIn、Facebook）。在社交网络中，每个人可以被表示为一个 **vertex (or node)**（顶点或节点），每个节点包含个人信息（ID、姓名、性别、地区等）。 课程将从图论的基本概念入手，逐步深入探讨图论相关的算法，并使用 C++ 进行实际编码实现。重点讲解的算法包括： * **DFS (Depth-First Search)**：深度优先搜索 * **BFS (Breadth-First Search)**：广度优先搜索 * **Kruskal's Algorithm**：克鲁斯卡尔算法 * **Prim's Algorithm**：普里姆算法 * **Dijkstra's Algorithm**：迪杰斯特拉算法 通过学习，您将能够理解如何在图中找到路径，了解 **Directed Graphs**（有向图）的概念，以及掌握 **Spanning Trees**（生成树）和 **Minimum Spanning Trees**（最小生成树）的原理与实现。 **最小生成树：** **Minimal Spanning Tree**（最小生成树）是指图 G 的所有可能生成树中，其所有边的权重（或长度）之和最小的生成树。实现最小生成树的常用方法有两种： * **Prim's Algorithm**（普里姆算法） * **Kruskal's Algorithm**（克鲁斯卡尔算法） **Dijkstra's Algorithm**（迪杰斯特拉算法）与普里姆算法相似，用于生成以给定源点为根的 **SPT (Shortest Path Tree)**（最短路径树）。该算法维护两个集合：一个包含已加入最短路径树的顶点，另一个包含尚未加入的顶点。在每一步，算法会从尚未加入的集合中选择一个距离源点最近的顶点加入。
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 TreeA 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 AlgorithmKruskal's AlgorithmDijkstra'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.
