概述
图(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();
}
分享到:
相关推荐
图的基本概念: 引入 定义 相关术语: 有向图 无向图 完全图 稀疏图 稠密图 权 网 邻接 关联(依附) 顶点的度 有向树 路径 路径长度 回路(环) 简单路径 简单回路(简单环) 连通图 强连通图 子图 连通分量 强连通...
(⼆)、基本表的定义、删除、修改 (⼆)、基本表的定义、删除、修改 1、定义基本表 定义基本表语句格式: CREATE TABLE <表名> (<列名> <数据类型> [ <列级完整性约束条件> ] , <列名> <数据类型> [ <列级完整性...
为了制订和应用质量标准以及便于国际交流中的相互理解,本国际标准规定了有关质量概念的基本术语,它们适用于所有领域。 (二)术语和定义 下列定义中,凡引入字母索引中的术语都用半黑体字印刷,在每个术语的定义...
1.1 HTML的基本概念 4 1.2 HTML发展史 4 1.3 HTML的基本结构 5 1.3.1 HTML文件的编写方法 5 1.3.2 文件开始标签<html> 7 1.3.3 文件头部标签<head> 7 1.3.4 文件标题标签<title> 7 ...
⼤数据导论(1)——"⼤数据"相关概念、5V特征、数据类型 在过去的⼗⼏年中,各个领域都出现了⼤规模的数据增长,⽽各类仪器、通信⼯具以及集成电路⾏业的发展也为海量数据的产⽣与存储提供 了软件条件与硬件⽀持。...
第十一章 图的基本概念主要内容图通路与回路图的连通性图的矩阵表示预备知识多重集合——元素可以重复出现的集合11.1 图定义11.1 无向图G = ,E>,
计算机网络概述 计算机网络基本概念 "三网合一"包括:传统电信网、计算机网络、广播电视网 宽带网络可分为宽带骨干网和宽带接入网 计算机网络的定义 计算机网络是利用通信设备与通信链路或者通信网络,互连位置不同...
a)阐明与质量有关的基本概念以及这些概念之间的区别和相互联系; b)提供ISO9000族质量管理和质量保证国际标准的选择和使用指南。 (二)引用标准 本国际标准发布时所引用的下列标准的有效版本,构成了本标准的一...
Oracle数据库基本概念逻辑存储结构表空间主要表空间表约束条件段、数据区和数据块物理存储结构数据文件控制文件日志文件实例 Oracle是一种关系数据库管理系统(RDBMS)。关系数据库是按照二维表结构方式组织的数据...
5.1.1 基本概念 分布式存储系统的定义:分布式存储系统是将为数众多的普通计算机或服务器通过网络进行连接,同时对外提供一个整体的存储服务。 分布式存储系统包括以下几个特性: 高性能 可扩展 低成本 易用性 ...
第六章 图王道考研——数据结构本节内容图定义基本术语王道考研/cskaoyan.com知识总览图的定义图G由顶点集V和边集E组成,记为G = (V, E),其中
Java学习流程——基础篇目录参考链接基本概念注意事项编译与运行编译执行基本数据类型内置数据类型引用类型常量定义参考链接Java基础语法Java基本数据类型基本
随着后PC时代的到来,随着计算机和通讯技术的飞速发展,互联网的迅速普及和3C融合的加速,嵌入式技术成为本世纪最有生命力的技术之一得到...这部分主要介绍了嵌入式系统的基本概念,包括嵌入式系统的定义、分类、特点等
2. 掌握计算机局域网的基本概念和工作原理。 3. 了解网络操作系统的基本知识。 4. 掌握Internet的基础知识,了解电子政务与电子商务的应用。 5. 掌握组网、网络管理与网络安全等计算机网络应用的基本知识...
6.1.3 明确定义概念 6.1.4 编写性能测试计划 6.1.5 编写性能测试方案 6.1.6 编写性能测试用例 6.2 搭建测试环境 6.2.1 测试平台评估 6.2.2 数据生成 6.2.3 测试环境搭建手册 6.3 创建脚本 6.3.1 用户注册 6.3.2 用户...
◆ 基本概念:数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型。数据 ——所有能被计算机识别、存储和处理的符号的集合。 数据元素 ——是数据的基本单位,具有完整确定的实际意义。 数据对象 ——具有...
笔记整理——Python爬虫(三):基本概念及常用基本方法一、爬虫基本概念定义使用爬虫的目的企业获取数据的方式使用Python做爬虫的优势爬虫分类通用爬取步骤(语义层面概括)二、爬虫请求模块模块及导入常用方法详解...
数据结构——堆 1.容易蒙圈的概念问题 ⼀般我在学习⼀个新的东西的时候都会在脑⼦⾥有⼀⼤堆问题!...实现堆的⼀⼤堆操作来袭 实现堆先要建⼀个堆类 定义它的属性和⽅法 我这⾥定义了如下的⽅法(基本
数据库1_1——数据库系统概述1.1 数据库的四个基本概念1.1.1 数据(Data)1.1.2 数据库(Database)1.1.3 数据库管理系统(DBMS)1.1.3.1 定义与作用1.1.3.2 DBMS的主要功能:建存管改联a. 数据定义功能:b. 数据...
1.1、课程设计的目的 数据库课程设计是数据库原理及应用实践环节极为重要的一部分,其目的主要是为了加强学生对数据库基本概念、原理和技术的掌握,结合实际的操作和设计,巩固课堂教学内容,将理论与实际相结合,...