6.1 图

2023-08-07

数据结构

6.1-1 定义

由顶点的有穷非空集合和顶点之间边的集合组成
通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
线性表可以空，树可以空，图不可以

6.1-2 一些概念

数据结构

生成子图要包含所有顶点
强连通分量：有向图中
连通图的生成树：连通图的极小连通子图

6.1-3 图的存储

数据结构

6.1-3.1 邻接矩阵

数据结构

出度：一行中非0元素的个数
入度：一列中非0元素的个数
空间复杂度：O(|v|²)
无向图->对称->矩阵压缩
设邻接矩阵A只含0、1，则A^k中非零元素表示从i到j的长度为k的路径数

6.1-3.2 邻接表

数据结构

空间复杂度：O(|v|+|e|)

6.1-3.3 十字链表（有向图）

数据结构

空间复杂度：O(|v|+|e|)
如何找到指定顶点的所有出边：沿着绿色的箭头找
如何找到指定顶点的所有入边：沿着橙色的箭头找

6.1-3.4 邻接多重表（无向图）

数据结构

空间复杂度：O(|v|+|e|)
删除边、顶点很方便

6.1-4 基本操作

函数	功能
Adjacent(G,x,y)	判断是否有从x到y的边，无向图只需判断一次
Neighbors(G,x)	返回与x邻接的顶点
InsertVertex(G,x)	插入顶点
DeleteVertex(G,x)	删除顶点
AddEdge(G,x,y)	插入边
RemoveEdge(G,x,y)	删除边
FirstNeighbor(G,x)	返回x的第一个邻接点
NextNeighbor(G,x,y)	返回x相对于y的下一个邻接点
Get_edge_value(G,x,y)	返回边(x,y)的权值
Set_edge_value(G,x,y,v)	设置边(x,y)的权值为v

有向图	无向图

6.1-4.1 图的遍历

广度优先遍历（BFS）
- 找到所有与v相邻的顶点：FirstNeighbor(G,v)，NextNeighbor(G,v,w)
- 标记哪个顶点已经访问过：visited[]
- 用队列保存已经访问过的顶点

数据结构
- 如果图是非连通的，需要对每个连通分量进行BFS

- 广度优先生成树

- 广度优先生成森林

深度优先遍历（DFS）
- 深度优先生成树
- 深度优先生成森林

缺失模块。
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

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家