概述
图(Graph)是一种比线性表和树更为复杂的数据结构。
线性结构:是研究数据元素之间的一对一关系。在这种结构中,除第一个和最后一个元素外,任何一个元素都有唯一的一个直接前驱和直接后继。
树结构:是研究数据元素之间的一对多的关系。在这种结构中,每个元素对下(层)可以有0个或多个元素相联系,对上(层)只有唯一的一个元素相关,数据元素之间有明显的层次关系。
图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间可能存在关系。即结点之间的关系可以是任意的,图中任意元素之间都可能相关。
图的基本概念
图的定义和术语
一个图(G)定义为一个偶对(V,E),记为G=(V,E)。其中:V是顶点(Vertex)的非空有限集合,记为V(G);E是无序集V&V的一个子集,记为E(G),其元素是图的弧(Arc)。
将顶点集合为空的图称为空图。其形式化定义为:
G=(V,E)
V={v|vÎdataobject}
E={<v,w>|v,wÎV∧p(v,w)}
P(v,w)表示从顶点v到顶点w有一条直接通路。
弧(Arc):表示两个顶点v和w之间存在一个关系,用顶点偶对<v,w>表示。通常根据图的顶点偶对将图分为有向图和无向图。
有向图(Digraph):若图G的关系集合E(G)中,顶点偶对<v,w>的v和w之间是有序的,称图G是有向图。
在有向图中,若<v,w>ÎE(G),表示从顶点v到顶点w有一条弧。其中:v称为弧尾(tail)或始点(initialnode),w称为弧头(head)或终点(terminalnode)。
无向图(Undigraph):若图G的关系集合E(G)中,顶点偶对<v,w>的v和w之间是无序的,称图G是无向图。
在无向图中,若"<v,w>ÎE(G),有<w,v>ÎE(G),即E(G)是对称,则用无序对(v,w)表示v和w之间的一条边(Edge),因此(v,w)和(w,v)代表的是同一条边。
例1:设有有向图G1和无向图G2,形式化定义分别是:
G1=(V1,E1)
V1={a,b,c,d,e}
E1={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}
G2=(V2,E2)
V2={a,b,c,d}
E2={(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}
它们所对应的图如图所示。
完全无向图:对于无向图,若图中顶点数为n,用e表示边的数目,则eÎ[0,n(n-1)/2]。具有n(n-1)/2条边的无向图称为完全无向图。完全无向图另外的定义是:
对于无向图G=(V,E),若"vi,vjÎV,当vi≠vj时,有(vi,vj)ÎE,即图中任意两个不同的顶点间都有一条无向边,这样的无向图称为完全无向图。
完全有向图:对于有向图,若图中顶点数为n,用e表示弧的数目,则eÎ[0,n(n-1)]。具有n(n-1)条边的有向图称为完全有向图.完全有向图另外的定义是:
对于有向图G=(V,E),若"vi,vjÎV,当vi≠vj时,有<vi,vj>ÎE∧<vj,vi>ÎE,即图中任意两个不同的顶点间都有一条弧,这样的有向图称为完全有向图。
有很少边或弧的图(e<n㏒n)的图称为稀疏图,反之称为稠密图。
权(Weight):与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离或耗费。
子图和生成子图:设有图G=(V,E)和G’=(V’,E’),若V’ÌV且E’ÌE,则称图G’是G的子图;若V’=V且E’ÌE,则称图G’是G的一个生成子图。
顶点的邻接(Adjacent):对于无向图G=(V,E),若边(v,w)ÎE,则称顶点v和w互为邻接点,即v和w相邻接。边(v,w)依附(incident)与顶点v和w。
对于有向图G=(V,E),若有向弧<v,w>ÎE,则称顶点v“邻接到”顶点w,顶点w“邻接自”顶点v,弧<v,w>与顶点v和w“相关联”。
顶点的度、入度、出度:对于无向图G=(V,E),"viÎV,图G中依附于vi的边的数目称为顶点vi的度(degree),记为TD(vi)。
显然,在无向图中,所有顶点度的和是图中边的2倍。即∑TD(vi)=2ei=1,2,…,n,e为图的边数。
对有向图G=(V,E),若"viÎV,图G中以vi作为起点的有向边(弧)的数目称为顶点vi的出度(Outdegree),记为OD(vi);以vi作为终点的有向边(弧)的数目称为顶点vi的入度(Indegree),记为ID(vi)。顶点vi的出度与入度之和称为vi的度,记为TD(vi)。即
TD(vi)=OD(vi)+ID(vi)
路径(Path)、路径长度、回路(Cycle):对无向图G=(V,E),若从顶点vi经过若干条边能到达vj,称顶点vi和vj是连通的,又称顶点vi到vj有路径。
对有向图G=(V,E),从顶点vi到vj有有向路径,指的是从顶点vi经过若干条有向边(弧)能到达vj。或路径是图G中连接两顶点之间所经过的顶点序列。即
Path=vi0vi1…vim,vijÎV且(vij-1,vij)ÎEj=1,2,…,m或
Path=vi0vi1…vim,vijÎV且<vij-1,vij>ÎEj=1,2,…,m
路径上边或有向边(弧)的数目称为该路径的长度。
在一条路径中,若没有重复相同的顶点,该路径称为简单路径;第一个顶点和最后一个顶点相同的路径称为回路(环);在一个回路中,若除第一个与最后一个顶点外,其余顶点不重复出现的回路称为简单回路(简单环)。
连通图、图的连通分量:对无向图G=(V,E),若"vi,vjÎV,vi和vj都是连通的,则称图G是连通图,否则称为非连通图。若G是非连通图,则极大的连通子图称为G的连通分量。
对有向图G=(V,E),若"vi,vjÎV,都有以vi为起点,vj为终点以及以vj为起点,vi为终点的有向路径,称图G是强连通图,否则称为非强连通图。若G是非强连通图,则极大的强连通子图称为G的强连通分量。
“极大”的含义:指的是对子图再增加图G中的其它顶点,子图就不再连通。
生成树、生成森林:一个连通图(无向图)的生成树是一个极小连通子图,它含有图中全部n个顶点和只有足以构成一棵树的n-1条边,称为图的生成树,如图所示。
关于无向图的生成树的几个结论:
◆一棵有n个顶点的生成树有且仅有n-1条边;
◆如果一个图有n个顶点和小于n-1条边,则是非连通图;
◆如果多于n-1条边,则一定有环;
◆有n-1条边的图不一定是生成树。
有向图的生成森林是这样一个子图,由若干棵有向树组成,含有图中全部顶点。
有向树是只有一个顶点的入度为0,其余顶点的入度均为1的有向图,如图7-3所示。
网:每个边(或弧)都附加一个权值的图,称为带权图。带权的连通图(包括弱连通的有向图)称为网或网络。网络是工程上常用的一个概念,用来表示一个工程或某种流程,如图7-4所示。
图的抽象数据类型定义
图是一种数据结构,加上一组基本操作就构成了图的抽象数据类型。图的抽象数据类型定义如下:
Graph{
数据对象V:具有相同特性的数据元素的集合,称为顶点集。
数据关系R:R={VR}
VR={<v,w>|<v,w>|v,wÎV∧p(v,w),<v,w>表示从v到w的弧,P(v,w)定义了弧<v,w>的信息}
基本操作P:
添加顶点
添加边
获得顶点的个数
获得边的条数
移除顶点
移除边
……
}
图的接口Graph
package datastructure.graph;
/**
* 图的接口
* @author luoweifu
*
*/
public interface Graph {
/**
* 添加顶点
* @param v
*/
public void addVex(Object v);
/**
* 添加边
* @param v1 第一个顶点
* @param v2 第二个顶点
* @param weight 权值
*/
public void addEdge(Object v1, Object v2, double weight);
/**
* 添加边
* @param v1 第一个顶点
* @param v2 第二个顶点
* @param info 边信息
* @param weight 权值
*/
public void addEdge(Object v1, Object v2, Object info, double weight);
/**
* 置空图
*/
public void clear();
/**
* 获得顶点v的第一个邻接结点
* @param v 顶点
* @return 顶点v的第一个邻接结点
*/
public Object getFirstVertex(Object v);
/**
* 在图G中寻找v1结点的邻接结点v2的下一个邻接结点
* @param v1 顶点
* @param v2 v1的一个邻接结点
* @return 邻接v1的在v2后的一个结点
*/
public Object getNextVertex(Object v1, Object v2);
/**
* 获得顶点的个数
* @return
*/
public int getVertexSize();
/**
*获得边的条数
* @return
*/
public int getEdgeSize();
/**
* 移除顶点
* @param v 顶点
*/
public void removeVex(Object v);
/**
* 移除边
* @param v1 顶点1
* @param v2 顶点2
*/
public void removeEdge(Object v1, Object v2);
/**
* 深度优先遍历
* @param o 遍历的初始顶点
* @return 遍历的结果
*/
public String dfs(Object o);
/**
* 深度优先遍历
* @param o 遍历的初始顶点
* @return 遍历的结果
*/
public String bfs(Object o);
/**
* 打印图的各顶点
* @return
*/
public String printGraph();
}
边的接口Edge
package datastructure.graph;
public abstract class Edge implements Comparable{
protected double weight;
protected Object info;
/**
* 构造函数
*/
public Edge() {
this.weight = 0;
}
/**
* 构造函数
* @param weight 权值
*/
public Edge(double weight) {
this.weight = weight;
}
public Edge(Object info, double weight) {
this.weight = weight;
this.info = info;
}
/**
* 获取权值
* @return 权值
*/
public double getWeight() {
return weight;
}
/**
* 设置权值
* @param weight 权值
*/
public void setWeight(double weight) {
this.weight = weight;
}
/**
* 获取边的信息
* @return 边的信息
*/
public Object getInfo() {
return info;
}
/**
* 设置边的信息
* @param info 边的信息
*/
public void setInfo(Object info) {
this.info = info;
}
/**
* 获取边的第一个顶点
* @return 第一个顶点
*/
public abstract Object getFirstVertex();
/**
* 获取边的第二个顶点
* @return 第二个顶点
*/
public abstract Object getSecondVertex();
}
分享到:
相关推荐
员工满意度是指员工对于工作环境、待遇、职业发展和组织管理等方面的满意程度。它是衡量员工对工作的整体感受和情绪状态的重要指标。
2020届软件工程本科毕业生毕业设计项目
平衡小车 基于stm32 平衡小车 基于stm32 平衡小车 基于stm32
c语言火车票订票管理源码.rar
施耐德PLC例程源码四台水泵的轮换提取方式是百度网盘分享地址
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
digix算法创新大赛2019baseline
三菱PLC小型立体仓库项目.zip 叉手篮具到位检测 入库2电机前限
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
软考高项_ITTO背诵打印必过版_2024_高项已通过
TCP三次握手及四次挥手详细图解 相对于SOCKET开发者,TCP创建过程和链接折除过程是由TCP/IP协议栈自动创建的.因此开发者并不需要控制这个过程.但是对于理解TCP底层运作机制,相当有帮助. TCP三次握手 所谓三次握手(Three-way Handshake),是指建立一个TCP连接时,需要客户端和服务器总共发送3个包。 三次握手的目的是连接服务器指定端口,建立TCP连接,并同步连接双方的序列号和确认号并交换 TCP 窗口大小信息.在socket编程中,客户端执行connect()时。将触发三次握手。 1.TCP建立流程 第一次握手:建立连接时,客户端发送SYN(Seq = J)包到服务器,并进入到syn_sent状态。等待服务器确认。 第二次握手:服务器收到SYN包,知道了Client端想建立连接. 它会向客户端发送SYN+ ACK包(ack =J+1 TCP 四次挥手 TCP的连接的拆除需要发送四个包,因此称为四次挥手(four-way handshake)。客户端或服务器均可主动发起挥手动作,在socket编程中,任何一方执行close()操作即可产生挥手操作
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
欧母龙PLC例程源码扎钢机程序提取方式是百度网盘分享地址
驾驶员注意力检测,驾驶员分神驾驶检测,DMS,汽车智能驾驶,智能座舱
Unity实现二维码扫描,二维码生成 提供ZXing.unity.dll可以进行二维码的生成和扫描,扫描的方式是在场景中发射射线,射线获取rawimage的texture并读取,然后作为二维码进行解析。 提供源代码。
中山大学-计科-操作系统实验.zip
施耐德PLC例程源码恒压供水程序(用施耐德TWIDO PLC编的)提取方式是百度网盘分享地址
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
小说词频统计是指对一本小说中出现的各个词语进行计数和分析,以确定每个词语在整篇小说中的出现频率。 以下是对小说词频统计的一些基本说明: 数据收集:首先需要获取目标小说的文本数据。这可以通过手动输入、复制粘贴文本内容或使用自动化工具来提取文本。 文本处理:在进行词频统计之前,通常需要对文本数据进行预处理。这可能包括去除标点符号、停用词(如“的”、“是”等)和特殊字符,将文本转换为统一的格式。 词语计数:进行词频统计时,遍历整个文本,逐个词语地计数它们的出现次数。通常会使用字典、哈希表或其他数据结构来存储词语及其计数。