文档章节

数据结构之图

思想永无止境
 思想永无止境
发布于 2016/11/04 11:59
字数 860
阅读 3
收藏 0

地震层析成像,一种比较先进的射线追踪方法——最小时间射线路径法用到计算机图形学(CG)的最小时间算法,这个是以图为基础的。

本章中介绍下列主要内容:
   1.图的定义
   2.图的存储结构
   3.图的遍历操作
   4.图的几个典型应用问题
课时分配:
1、2两个学时,3两个学时,4四个学时,上机两个学时
重点、难点:
图的遍历操作、典型应用问题

第一节 图的定义

1.定义
图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

在上面两个图结构中,一个是有向图,即每条边都有方向,另一个是无向图,即每条边都没有方向。
在有向图中,通常将边称作弧,含箭头的一端称为弧头,另一端称为弧尾,记作<vi,vj>,它表示从顶点vi到顶点vj有一条边。
若有向图中有n个顶点,则最多有n(n-1)条弧,我们又将具有n(n-1)条弧的有向图称作有向完全图。
以顶点v为弧尾的弧的数目称作顶点v的出度,以顶点v为弧头的弧的数目称作顶点v的入度。 
在无向图中,边记作(vi,vj),它蕴涵着存在< vi,vj>和<vj,vi>两条弧。若无向图中有n个顶点,则最多有n(n-1)/2条边,我们又将具有n(n-1)/2条边的无向图称作无向完全图。
与顶点v相关的边的条数称作顶点v的度。 路径长度是指路径上边或弧的数目。
若第一个顶点和最后一个顶点相同,则这条路径是一条回路。
若路径中顶点没有重复出现,则称这条路径为简单路径。
在无向图中,如果从顶点vi到顶点vj有路径,则称vi和vj连通。如果图中任意两个顶点之间都连通,则称该图为连通图,否则,将其中的极大连通子图称为连通分量。
在有向图中,如果对于每一对顶点vi和vj,从vi到vj和从vj到vi都有路径,则称该图为强连通图;否则,将其中的极大连通子图称为强连通分量。

2.图的基本操作
基本操作:
(1)创建一个图结构 CreateGraph(G)
(2)检索给定顶点 LocateVex(G,elem)
(3)获取图中某个顶点 GetVex(G,v)
(4)为图中顶点赋值 PutVex(G,v,value)
(5)返回第一个邻接点 FirstAdjVex(G,v)
(6)返回下一个邻接点 NextAdjVex(G,v,w)
(7)插入一个顶点 InsertVex(G,v)
(8)删除一个顶点 DeleteVex(G,v)
(9)插入一条边 InsertEdge(G,v,w)
(10)删除一条边 DeleteEdge(G,v,w)
(11)遍历图 Traverse(G,v)

第二节 图的存储结构

1.邻接矩阵
1.1 有向图的邻接矩阵
具有n个顶点的有向图可以用一个n×n的方形矩阵表示。假设该矩阵的名称为M,则当

© 著作权归作者所有

思想永无止境
粉丝 4
博文 257
码字总数 292814
作品 0
昌平
程序员
私信 提问
游戏开发与程序设计知识总结02——数据结构

更新日志 每此对思维导图有改动或者在github中有了对应的实现,则增加一条更新日志。 2017.9.2: 确定更新为系列文章并持续维护 更新B树,B+树,红黑树的参考链接 更新了Huffman树的标注 前言...

kashiwa
2017/08/31
0
0
SylixOS x86中断探测(二)

MP Spec简介 MP Spec即MultiProcessor Specification,简称MPS,中文翻译为多重处理器规范,定义了MP系统配置的数据结构。BIOS构建MP配置数据结构,将硬件以已知格式呈现给标准设备驱动程序或...

huikai309
2018/02/28
1
0
网络协议报文结构与抓包示例

TCP/IP的分层 OSI的分层 以太网帧抓包看到的结构如下图: IP数据报文 以太网帧抓包看到的结构如下图: TCP数据报文 TCP报文抓包看到的结构如下图: UDP数据报文 UDP报文抓包看到的结构如下图...

hongliang_liu
2017/04/17
0
0
C语言/C加加程序员新手入门学习基础之数据类型分享

请点击此处输入图片描述 关注我们 为什么要首先介绍数据类型? 因为(数据结构就是对数据类型的操作)不论是哪一种语言,都要有其基本数据类型,这些基本的数据类型就像一块块砖,而程序中的...

小辰GG
2017/12/30
0
0
解读Dual Path Networks(DPN,原创)

Dual Path Networks,论文链接:https://arxiv.org/pdf/1707.01629.pdf ResNet和DenseNet是近几年两种比较热门的网络结构,ResNet把输入直接加到(element-wise adding)卷积的输出上,Dense...

张磊_0503
2017/12/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Android进阶(四):Activity启动过程(最详细&最简单)

1.前言 最近一直在看 《Android进阶解密》 的一本书,这本书编写逻辑、流程都非常好,而且很容易看懂,非常推荐大家去看看(没有收广告费,单纯觉得作者写的很好)。 上一篇简单的介绍了And...

天王盖地虎626
39分钟前
0
0
DLA SQL技巧:行、列转换和JSON数据列展开

1. 简介 在数据库SQL处理中,常常有行转列(Pivot)和列转行(Unpivot)的数据处理需求。本文以示例说明在Data Lake Analytics(https://www.aliyun.com/product/datalakeanalytics)中,如何...

阿里云云栖社区
43分钟前
0
0
docker入门

第一步、安装docker 这里给出阿里云的docker安装步骤 https://help.aliyun.com/document_detail/51853.html?spm=a2c4g.11186623.6.820.RaToNY 注意:docker需要linux内核在3.10以上才可以安装...

嘴角轻扬30
43分钟前
2
0
容器中的JVM资源该如何被安全的限制?

前言 Java与Docker的结合,虽然更好的解决了application的封装问题。但也存在着不兼容,比如Java并不能自动的发现Docker设置的内存限制,CPU限制。 这将导致JVM不能稳定服务业务!容器会杀死你...

xiaomin0322
51分钟前
6
0
mysql查询最近连续登录和累计登录

这条sql写了一天,百度无数,终于摸到点门路 需求是查询从当前日期向前推的连续登录,比如一个用户他今天登录了,昨天没登,连续登录为1 他昨天前天都登录了,今天没登录,连续登录为0 SELEC...

七月大人
53分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部