博客专区 > Cobbage 的博客 > 博客详情
Cobbage 发表于3年前
  • 发表于 3年前
  • 阅读 14
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: 在以前从未碰过的

一、图的基本概念

       眼睛看到的都是图。

       数据结构中图示如何的?是个骨架点与线,熟悉的是长方形、梯形。

       定义G=(V,E) V代表的是点,E代表的是边

       分类,有向图,无向图,加权图,无权图,稀疏图,稠密图

       图的表示 一种是坐标

                    一种是点和边

 二、图的存储

                   相邻矩阵 存储点集

            

 

               相邻链表法 存储边集

           十字链表法 有向图计算出度比较方便

 

 

三、图的遍历

图的遍历之 深度优先搜索和广度优先搜索

                    1.深度遍历

                  原则是根据一条边 沿途找到向下找到最小的点进行遍历

                                          然后回溯进行第一步

                                         A->C->B->D->F->G->E

                                       A->B->C->E->D->F->G

                    2.广度遍历 按照层次来遍历的 例如 座位一排一排的

四、最小生成树

      求解有权限的连通图的问题。例如线路的假设。

      无向图中的求解:Kruscarl算法、Prim算法

五、最短路径

      单向的最短权值。例如你要从这个地方出发-〉目的地最短距离

      算法:Dijkstra算法,Bellman-Ford算法和SPFA算法


共有 人打赏支持
Cobbage
粉丝 45
博文 109
码字总数 54478
×
Cobbage
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: