图

2022-03-04

6.1_1 图的基本概念

图的定义

有向图，$(u,v)$表示顶点$u$和$v$之间有一条边
无向图，$$表示顶点$u$和$v$之间有一条边，$u$为弧尾，$v$为弧头
简单图：不存在重复边，不存在顶点到自身的边
多重图：允许顶点到自身有边，允许有重复的边
顶点的度，入度，出度
路径
简单路径：顶点不重复的路径
回路 / 环
简单回路：除了第一个定点和最后一个顶点，其余路径不重复
路径长度：路径边的数目
连通
连通图
- 非联通图最多有$C^2_{n-1}$条边
强连通：顶点$v$到$w$和顶点$w$到$v$之间都有路径
强连通图
- 最少有$n$条边
子图
生成子图：包含原图的所有节点
连通分量：无向图中的极大连通子图
强连通分量：有向图中的极大强连通子图
生成树：包含全部顶点的极小连通子图 $n-1$条边
生成森林：非连通图的连通分量的生成树构成
权带权图带权路径长度

6.2_1 图的存储邻接矩阵法

0表示两个顶点之间没有边
1表示两个顶点之间有边
带权图：用权值表示边，不存在边则$\infty$或0
不适合用于存储稀疏图

邻接矩阵的性质

假设$G$的邻接矩阵为$A$（矩阵元素为0/1），则$A^n$的元素$A[i][j]$表示从顶点$i$到顶点$j$的长度为$n$的数量

6.2_2 临接表法

图的临界表表示并不唯一

6.3_3 十字链表、邻接多重表

十字链表法只用于存储有向图

邻接多重表用于存储无向图

6.2_4 图的基本操作

缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是yilia根目录）执行以下命令：
npm i hexo-generator-json-content --save

3、在根目录_config.yml里添加配置：

  jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

ComeOn

一定要赢