当前位置: 首页 > news >正文

重庆网络科技服务有限公司seo第三方点击软件

重庆网络科技服务有限公司,seo第三方点击软件,如何用dreamer做网站,手机电影网站怎么做目录 第六章 图6.1 图的基本概念知识回顾 6.2 图的储存结构(邻接矩阵法)1. 数组表示法(1) 有向图,无向图的邻接矩阵 2. 定义邻接矩阵的结构3. 定义图的结构4. 构造图G5. 特点 第六章 图 6.1 图的基本概念 图是一种非线性结构 图的特点&am…

目录

  • 第六章 图
  • 6.1 图的基本概念
      • 知识回顾
  • 6.2 图的储存结构(邻接矩阵法)
    • 1. 数组表示法
      • (1) 有向图,无向图的邻接矩阵
    • 2. 定义邻接矩阵的结构
    • 3. 定义图的结构
    • 4. 构造图G
    • 5. 特点

第六章 图

6.1 图的基本概念

图是一种非线性结构
在这里插入图片描述

图的特点:

  • 顶点之间的关系是任意的
  • 图中任意两个顶点之间都可能相关
  • 顶点的前驱和后继个数无限制
  1. 定义:图是一种数据元素间存在多对多关系的数据结构加上一组基本操作构成的抽象数据类型
  • 定义:图G由顶点集V和边集E组成,记为G=(V,E),其中V(G)表示图G中顶点的有限非空集;E(G)表示图G中顶点之间的关系(边)集合。若V={V1,V2,……Vn},则用|V|表示图G中顶点的个数,也称图G的阶,E={(u,v)|u∈V,v∈V},用|E|表示图G中边的条数。
  • 注意:线性表可以是空表,树可以是空树,但图不可以为空,即V一定是非空集
  • 弧头和弧尾
    <x,y>表示从顶点到顶点y的一条弧,并称x为弧尾或起始点,称y为弧头或终端点
  1. 无向图,有向图:有向图<u,v>,其中u表示弧尾,v表示弧头
  2. 简单图:简单图:①不存在重复边,② 不存在顶点到自身的边
  3. 多重图:图G中某两个结点之间的边数多于一条,又允许顶点通过同一条边和自己关联,则G为多重图。
  4. 度,入度,出度:① 无向图:在具有n个顶点,e条边的无向图中,全部顶点的度的和等于边数的2倍(一条边连两个顶点,所以一条边两个度)。②有向图:度之和入度+出度(一条边一个出度一个入度),在具有n个顶点,e条边的有向图中,入度=出度=e
  5. 路径,简单路径,路径长度:① 在路径序列中,顶点不重复出现的路径称为简单路径。②路径长度:路径上边的数目(简单就意味着顶点不重复)。
  6. 回路,简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单回路。
  7. 点到点到距离:从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为u到v的距离。若u到v根本不存在路径,则记该距离为无穷(∞)
  8. 连通图,强连通图:①若图G中任意两个顶点都是连通的,则称图G为连通图(无向图中的连通就是两个顶点之间路径存在;有向图中的强连通是两个顶点之间存在往返的路径,就是w到v和v到w都有路径,强连通是有向图独有的概念),否则称为非连通图。对于n个顶点的无向图G,若G是连通图,则至少有n-1条边(就是把每个顶点都连线一个顶点,就存在路径了),若G是非连通图,则最多可能有 C n − 1 2 C_{n-1}^{2} Cn12,(就是除去一个顶点,其他顶点两两相连,只要不连接最后一个顶点,这个图就是不连通的最极端情况)。②若图中任何一项顶点都是强连通的,则称为图为强连通图。对于n个顶点的有向图G,若G是强连通图,则最少为n条边(形成回路)。
  9. 连通的补充图解:
  • 连通的最少边数:
    在这里插入图片描述
  • 不连通的最多边数:
    在这里插入图片描述
  • 强连通的最少边数
    在这里插入图片描述
  1. 子图(不用包含所有顶点)、生成子图:若包含所有顶点的子图,就称为生成子图。并不是任意几个点,任意几条边都能构成子图(例如不构成图的情况)。
    在这里插入图片描述

  2. 连通分量:无向图中极大连通子图(子图必须连通,且包含尽可能多的顶点和边)称为连通分量。
    在这里插入图片描述

  3. 强连通分量:有向图中有极大强连通子图(子图必须强连通,同时保留尽可能多的边)称为有向图的强连通分量。
    在这里插入图片描述

  4. 生成树:连通图的生成树是包含图中全部顶点的一个极小连通子图边尽可能的小,但要保持连通若图中顶点数是n,则它的生成树含有n-1条边,对于生成树而言,若砍去一条边,则会变成非连通图,若加上一条边则会形成一个回路(环)

  5. 生成森林:在非连通图中,连通分量的生成树构成了非连通图的生成森林
    在这里插入图片描述

  6. 边的权,带权图(网)
    在这里插入图片描述

  7. 无向完全图:无向图中任意两个顶点之间都存在边。

  8. 有向完全图:有向图中任意两个顶点之间都存在方向相反的两条弧。
    在这里插入图片描述

  9. 稀疏图,稠密图:这二者是相对的
    在这里插入图片描述

  10. 树:不存在回路,且连通的无向图,n个顶点的树,必有n-1条边。

  11. 有向树:一个顶点的入度为0,其余顶点的入度均有1的有向图,称为有向树。
    n个顶点的图,若|E|>n-1,则一定有回路。
    在这里插入图片描述

知识回顾

在这里插入图片描述

6.2 图的储存结构(邻接矩阵法)

在这里插入图片描述

1. 数组表示法

(1) 有向图,无向图的邻接矩阵

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

① 对于无向图,顶点vi的度是邻接矩阵中第i行(或第i列)的元素之和, TD(vi)= ∑ a[i][j]。
② 对于有向图,顶点VI的出度OD(vi)是邻接矩阵中第i行的元素之和顶点vi的出度ID(vi)是邻接矩阵中第j列)的元素之和
邻接矩阵法求顶点的度。入度。出度的时间复杂度为O(|V|)

在这里插入图片描述

2. 定义邻接矩阵的结构

#define INFINITY INT_MAX
#define MAX_VERTEXT_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind;
typedef struct ArcCell{VRType adj;//对无向图,用0,1表示是否相邻,对于带权图,为权值InfoType *info;//该弧相关信息的指针}RrcCell,AdjMatrix[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM];//邻接矩阵

3. 定义图的结构

(1)代码:

//定义图的结构
typedef struct {VertextType exs[MAX_VERTEXT_NUM]; //顶点AdjMatrix arcs[MAX_VERTEXT_NUM][MAX_VERTEXT_NUM]; //边的邻接矩阵int vexnum,arcnum; //个数GraphKind kind;//有向图?无向图?
}MGraph;

在这里插入图片描述

4. 构造图G

status CreateGraph(MGraph &G)
{scanf(&G.kind){case DG:return CreateDG(G);case DN:return CreateDN(G);case UDG:return CreateUDG(G);case UDN:return CreateDGN(G);default:return ERROR;}
}
//用无向图为例status CreateUDN(MGraph &G)
{scanf(&G.arcnum,&G.vexnum,&IncInfo);//输入点数和边数//给顶点进行数字化编号for(i=0;i<G.vexnum;i++){ scanf(&G.exs[i]);//定义顶点数组(如果顶点本身就是1~n的数字无需这一步)}//初始化邻接矩阵for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++){G.arcs[i][j]={ININITY,NULL};}}//通过边数进行遍历for(k=0;k<G.arcnum;K++){scanf(&V1,&V2,&W);//输入邻接的连个顶点i=locatteVex(G,V1);j=locateVex(G,V2);//查找V1,V2的位置G.arcs[i][j].adj=w;//给邻接矩阵赋值if(IncInfo){INPUT(*G.arcs[i][j].info);}G.arcs[j][i]=G.arcs[i][j];//由于是无向图,对称}return ok;
}

5. 特点

优点:

  • 无向图邻接矩阵是对称矩阵,同一条边表示了两次
  • 顶点v的度:等于二维数组对应行(或列)中1的个数
  • 判断两顶点v、u是否为邻接点:只需判二维数组对应分量是否为1
  • 在图中增加、删除边:只需对二维数组对应分量赋值1或清0
  • 占用存储空间只与它的顶点数有关,与边数无关;适用于边稠密的图
  • 对有向图的数组表示法可做类似的讨论’‘

缺点:

  • 不便于删除和增加顶点(增删边简单)
  • 不便于统计边的数目,需要扫描邻接矩阵所有元素才能统计完毕,时间复杂度为O( n 2 n^2 n2 )
  • 空间复杂度高,对于有向图,n个顶点需要 n 2 n^2 n2 个单元存储边,对于无向图,n(n-1)/2个单元,空间复杂度为O( n 2 n^2 n2 )
http://www.dinnco.com/news/10750.html

相关文章:

  • 企业网站布局代码seo建站是什么
  • wordpress bbpress主题二十条优化措施全文
  • 做网站做哪个自己建个网站要多少钱
  • 网站制作一般收费免费发布信息平台有哪些
  • wordpress中国风主题seo百度点击软件
  • 制作ppt的网站怎么自己制作网站
  • 网站建设发展方向学管理培训班去哪里学
  • mac系统做网站考证培训机构报名网站
  • 河北网站建设多少钱google官网进入
  • 网站建设的威胁西安网站建设比较好的公司
  • 网站前置审批表搜索指数
  • 淘宝上做网站权重seo报价单
  • 织梦av女优色流网站模板app推广平台接单渠道
  • 网站建设kaodezhu网络营销工程师前景
  • 网站建设及维护保密协议百度知道小程序
  • 重庆雕塑制作长沙seo报价
  • 邢台外贸网站建设湖北权威的百度推广
  • 网站推广报告百合seo培训
  • pc网站如何做seo百度搜索指数入口
  • 动态网站系统网络推广包括哪些
  • 网站建设的设计与实现什么是搜索引擎优化的核心
  • 自己如何做简单网站广州品牌营销服务
  • 网站前端开发培训资料域名怎么查
  • 电商网站商品详情页抖音seo公司
  • 玉林做网站公司seo关键字怎么优化
  • 做环评在发改委网站申请做销售最挣钱的10个行业
  • 网站广告动图怎么做百度推广怎么才能效果好
  • 网站ip屏蔽青岛seo网站排名
  • web校园网站开发实验报告新东方在线koolearn
  • 建设网站要编程bu经典营销案例分析