学习C语言中图的基本概念及相关概念总结

本文是基于王道和b站懒猫老师以及王卓老师的课程进行归纳总结所得。文章使用的具体语言是c语言，部分代码未能实现，使用了伪代码的方式。文章内容包含以下几个部分：图的基本概念，有向图，无向图等。 首先，我们来学习图的基本概念。图G由顶点集V和边集E组成，记为G=(V,E)，其中V表示图G中顶点的有限非空集合，E表示图G中顶点之间的关系(边）集合。若V={v1,v2,v3,…… }，则用|V表示图G中顶点的个数。而E={(u, v)| u∈v,v∈V}表示图G中边的条数。需要注意的是，线性表和树可以为空，但图不能为空，其顶点集不能为空，但边可以为空。 有向图是指当E是有向边(也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，其中v称为弧尾，w称为弧头，<v, w>称为从v到w的弧，也称v邻接到w。而无向图则是指当E为无向边（简称边）的有限集合时，则图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)，可以说w和v互为邻接点。 在实际的算法中，图的遍历是一种基本的操作，它是指对图中所有顶点或者边都进行检查或访问。对于有向图和无向图，我们常常采用深度优先搜索（DFS）和广度优先搜索（BFS）等方法来实现图的遍历。此外，对于图的表示，有邻接矩阵和邻接表两种常见的表示方法，其中邻接矩阵适用于稠密图，邻接表适用于稀疏图。 在图的算法中，最短路径算法是一类比较重要的算法，它用于寻找图中两个顶点之间的最短路径。其中Dijkstra算法和Floyd-Warshall算法是两种常用的最短路径算法，它们分别适用于有向图和无向图，对于带权图和无权图都能够有效地找到最短路径。而在最小生成树问题中，Prim算法和Kruskal算法是两种常用的解决方法，它们都能够有效地找到一个连通图的最小生成树。 总之，图是一种非常重要的数据结构，它在实际的计算机应用中有着广泛的应用，比如路线规划、网络传输等领域。掌握图的基本概念和算法对于提高程序的效率和性能有着重要的意义。希望本文的内容能够对读者有所帮助，同时也欢迎读者批评指正，共同进步。