Please enable JavaScript.

Coggle requires JavaScript to display documents.

图 (逻辑结构, 应用, 存储结构, 操作：遍历) - Coggle Diagram

- - - - 顶点不重复出现的路径
    - - 除头尾顶点外，其余顶点不重复出现的回路
  - - - 任意两个顶点都是连通的
    - - 无向图中的极大连通子图
    - - 无向图中两个顶点之间有路径
  - - - 有向图中v到w和w到v之间都有路径
    - - 图中任意一对顶点都是强连通的
    - - 有向图中极大强连通子图
  - - - 包含图中全部顶点的一个极小连通子图
    - - 砍去一条边，则会变成非连通图
      - 加上一条边则会形成一个回路
    - - 非连通图中连通分量的生成树的集合
  - - - 有向边的有限集合，<x,y>表示顶点x到y的一条弧，x为弧尾，y为弧头
    - - 无向边的有限集合，边表示为(x,y)
  - - - 完全图中任意两个顶点之间都存在边
    - - 任意两个顶点之间都存在方向相反的两条弧
  - - - 出度
        
        以该顶点为起点的有向边的数目
      - 入度
        
        以该顶点为终点的有向边的数目
    - - 度为依附于该顶点的边的条数
- - - - 带权连通无向图的边的权值最小的生成树
    - - 假设G=(V,E)时一个带权连通无向图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u属于U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树
    - - 普里姆Prim算法
      - 克鲁斯卡尔Kruskal算法
  - - - AOV网
        
        顶点表示活动，弧表示优先关系的有向无环图
      - 拓补序列
        
        有向图G=(V,E)中V中顶点的线性序列
      - 拓补排序
        
        由AOV网构造拓补序列的过程
    - - 1.从AOV网中选择一个没有前驱的顶点并输出
      - 2.从网中删除该顶点和所有以它为起点的有向边
      - 3.重复1和2直到当前AOV网为空或当前网中不存在无前驱的顶点为止
  - - - 非网图
        
        两顶点之间经过边数最少的路径
      - 网图
        
        两顶点经过的边上权值之和最少的路径
    - - 迪杰斯特拉Dijkstra算法
      - 弗洛伊德Floyd算法
  - - - AOE网
        
        顶点表示事件，有向边表示活动，以边上的权值表示完成该活动的开销的带权有向图
      - 关键路径
        
        从入度为零的顶点导出度为零的顶点的最长路径
      - 关键活动
        
        关键路径上的活动
    - - 1.从源点出发，令ve=0，按拓补排序求其余顶点最早发生事件
      - 2.从汇点出发，令vl=0，按逆拓补排序求其余顶点的最迟发生时间
      - 3.根据各顶点的ve值求所有弧的最早开始时间
      - 4.根据各顶点的vl值求所有弧的最迟开始时间
      - 求AOE网中所有活动的差额d，找出d=0的活动构成关键路径
- - - - 用两个数组表示图，一个一维数组存储顶点信息，一个二维数组储存边或者弧的信息
    - - 无向图
        
        一定是对称矩阵，且主对角线上全零
        
        矩阵第i行非零元素的个数正好是第i个顶点的度
      - 有向图
        
        主对角线全零，不一定对称
        
        vi顶点的入度为第i列各数之和，出度为第i行各数之和
      - 带权图的邻接矩阵中对应项应存放权值
    - - 容易确定图中任意两个顶点之间是否相连
      - 稠密图适合用邻接矩阵表示，节省空间
    - - 确定有多少条边时，花费时间代价大
      - 稀疏图浪费大量空间
  - - - 由顶点表和边表组成，边表：对每个顶点建立单链表，第i个单链表中的结点表示依附于顶点vi的边(有向图则是以vi为尾的弧) ；顶点表：边表的头指针和顶点的数据信息顺序存储
    - - 无向图
        
        存储空间O(|V|+2|E|)
        
        顶点的度为对应单链表上结点的个数
      - 有向图
        
        存储空间O(|V|+|E|)
        
        出度为单链表上结点的个数，入度则需要搜索所有单链表
      - 网图可以在边表结点定义中增加一个weight
    - - 稀疏图极大节省存储空间
      - 给定顶点容易找出其所有邻边
    - - 判断给定两个顶点之间是否存在边效率较低
      - 有向图算入度需要遍历全表效率很低
- - - - 从图中某个顶点V0出发，首先访问V0
      - 依次从V0的未被访问的邻接点出发DFS，直到图中所有和V0有路径相通的顶点都被访问
    - - 存储结构
        
        用邻接矩阵
        
        时间复杂度:O(n^2)
        
        用邻接表
        
        时间复杂度:O(n+e)
      - 算法
        
        递归
        
        空间复杂度O(n)
        
        非递归
  - - - 从图中某个顶点V0出发，首先访问V0
      - 依次访问V0的各个未被访问的邻接点
      - 若Vi在Vk之前被访问，则Vi的所有未被访问的邻接点应在Vk的所有未被访问邻接点之前访问
    - - 存储方式
        
        用邻接表
        
        时间复杂度:O(n+e)
        
        用邻接矩阵
        
        时间复杂度:O(n^2)
      - 都需借助一个辅助队列Q，空间复杂度空间复杂度O(n)