图 - 基础篇

简介: 图 - 基础篇

连通图针对无向图,强连通图针对有向图。


稀疏图(边数较少),稠密图(边数较多)。

稠密图:邻接矩阵、Prim算法...

稀疏图:邻接表、Kruskal算法...


如果一个连通图的所有结点的度都是偶数,那么它就是Eulerian,如果除了两个结点的度是奇数其他都是偶数,那么它就是Semi-Eulerian,否则就是Non-Eulerian。

给定一组节点的度序列来判断一个图是否为简单图?(符合以下两点即可)


a、每个节点度数要小于节点个数。

b、该图具有偶数个奇数度的节点。


判定哈密顿回路条件:

a、路径节点个数等于 n+1

b、相邻点之间存在连通的边

c、各点只出现过1次(除了首尾)

d、第一个节点等于最后一个节点(构成回路)

待更新...


目录
相关文章
|
算法 决策智能 索引
二部图问题
二部图问题
|
人工智能 计算机视觉 开发者
一、图 图是由一组节点和边组成的非线性数据结构,用于描述节点之间的关系。图的节点称为顶点,边表示顶点之间的连接关系。图可以用于描述现实世界中的各种关系,例如社交网络中的好友关系、城市之间的道路连接、电路中的元器件连接等。 图的主要特点包括: 1. 顶点:图的基本单位,用于表示实体或抽象概念。 2. 边:用于表示顶点之间的连接关系,可以是有向或无向的,带权或不带权的。 3. 路径:连接图中两个顶点的路径是由一系列相邻的边构成的序列。 4. 连通性:如果图中任意两个顶点之间都存在路径,则称该图为连通图,否则为非连通图。 5. 度:顶点的度表示与该顶点相邻的边的数量。 6. 子图:图中的一部分称为子
60 0
|
算法
N-S图详解
N-S图详解
890 0
|
数据可视化 算法 架构师
各种图介绍
系统架构师-UML相关图
86 0
|
存储 算法 C++
|
存储