文档章节

Cobbage
 Cobbage
发布于 2015/02/14 23:26
字数 317
阅读 22
收藏 0

一、图的基本概念

       眼睛看到的都是图。

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

       定义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

Cobbage

粉丝 49
博文 145
码字总数 72814
作品 1
闵行
QA/测试工程师
私信 提问

暂无文章

结合lucene谈谈日期的压缩问题

说起日期值的压缩,一般容易想到的办法是将日期转化成long类型,然后再通过变长整形进行压缩,我算了一下按照毫秒来算最多占用5个字节(可以通过“谈谈变长整型”中的表查看),确实节省了部...

FAT_mt
42分钟前
0
0
导出私有函数与私有变量

在Go语言中, package中包含函数与变量通过identifier的首字母是否大写来决定它是否可以被其它package所访问。当一个函数或变量名称为小写字母时,默认是无法被其他package引用的. 有没有办法...

xtof
42分钟前
0
0
new Date() 在Safari下的 Invalid Date问题

问题复现 var timeStr = '2018-11-11 00:00:00';var time = new Date(timeStr);// error: Invalid Date... 在safari浏览器下,time为Invalid Date, 导致后面代码执行错误; 其他浏览器诸...

会写代码的husky
47分钟前
2
0
0009-如何升级Cloudera Manager和CDH

1.文档编写目的 本文档讲述如何升级Cloudera Manager和CDH,通过本文档,您将学习到以下知识: 1.如何对Cloudera Manager进行停机升级 2.如何对CDH进行停机升级 3.如何在不影响集群作业的情况...

Hadoop实操
57分钟前
1
0
vue2中引用 better-scroll的方法

文章主要介绍了vue2中引用better-scroll和使用 better-scroll的方法,使用时有三个要点及注意事项在文中给大家详细介绍 ,需要的朋友可以参考下 使用时有三个要点: 一:html部分 <div class...

前端攻城老湿
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部