考研笔记 | 数据结构 §6.图

  • 英语:

§1.概述

  1. 定义:由定点集V和边集E组成,记为G(V,E)

  2. 注意:线性表、树可为空,但图不可为空。至少一个顶点。

  3. 有向图:E是有向边(简称弧)的有限集合。 $0≤e≤n(n-1)$ 弧

  4. 无向图:E是无向边(简称边)的有限集合。 $0≤e≤\frac{n(n-1)}{2}$

  5. 简单图:满足 ① 不存在重复边,② 不存在定点到自身的边。

* 在数据结构中,讨论的均为简单图!(与之对应的是多重图)

  1. 无向完全图:任意两个顶点都存在边,$e=\frac{n(n-1)}{2}$

  2. 有向完全图:任意两个顶点存在着方向相反的两条弧,$e=n(n-1)$

  3. 连通:从顶点V到顶点W有路径存在,则称V与W连通。

  4. 连通图:若图G中任意两个顶点都是连通的,称G为连通图,否则为非连通图。

  5. 无向图中的极大连通图称为连通分量。

  6. 强连通图(仅针对有向图),若从顶点V到顶点W和从顶点W到顶点V之间都有路径,则称这两个顶点强连通,则称。

  7. 强联通分量(仅针对有向图),图中极大强连通子图称为有向图的强连通分量。

  8. 生成树:连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为$n$,则它的生成树有$n-1$条边。

    对生成树:若砍去一条边则为非连通图,加上一条边为回路。

    • 度:边数
    • 出度:“起点边数”
    • 入度:“终点边数”
    • 无向图中,度为$\sum_{i=1}^n TD(V_i)=2e$
    • 有向图中,$TD(V_i)=ID(V)+OD(V)$
    • $e$条边有向图,$\sum_{i=1}^n ID(V_i)=\sum_{i=1}^n OD(V_i)=e$
  9. 稠密图与稀疏图:边数很少($e<nlog_2n$),称为稀疏图。

  10. 路径:顶点$v_0$到顶点$v_q$之间的一条路径,即顶点序列$v_1,v_2,v_3,……,v_n$。

  11. 路径长度:路径上边的数目。

  12. 回路:第一个顶点和最后一个顶点相同的路径。
    若一个图有n个顶点,且有大于$n-1$条边,则此图一定有环。

  13. 简单路径:在路径序列中,顶点不重复出现的路径。

  14. 简单回路:除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路。

  15. 图的存储结构:邻接矩阵、邻接表、逆邻接表、十字链表、邻接多重表。(邻接多重表仅适用于存储无向图)。

§2.邻接矩阵表示法

  1. 邻接矩阵法:一位数组存储顶点+二维数组存储图的边+顶点数+弧数

  2. 1
    2
    3
    4
    5
    6
    7
    8
    #define MaxVertexNum 100 // 顶点数目最大值
    typedef char VertexType; // 顶点数据类型
    typedef int EdgeType; //带权图中边上权值的数据类型
    typedef struct Graph{
    VertexType vex[MaxVertexNum]; //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; //矩阵边表
    int Vexnum,arcnum; //图中当前顶点数与弧数
    }MGraph;//空间复杂度O(n²),n为顶点数
  3. 无向图的邻接矩阵一定是对称矩阵(且唯一)。在世纪应用可以压缩存储(上/下三角矩阵)。

  4. 无向图邻接矩阵第$i$行(第$j$列)非0元素的个数为第$i$个顶点的度。

  5. 有向图邻接矩阵第$i$行(第$j$列)非0元素的个数为第$i$个顶点的出度(入度)。

  6. 用临街矩阵法存储图,很容易确定图中任意两个顶点是否有边相连。但要确定途中有多少条便需按行、列对每个元素检测。

§3.邻接表表示法

  1. 邻接表法:数组(弧尾顶点)+链表(邻接点)+个数

    • 顶点表:
Datafirstarc
顶点域头指针
  • 边表:
adjVexnextarc
邻接点域指针域
  1. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #define MaxVertexNum 100
    typedef struct ArcNode{//边表结点
    int adjVex;
    struct ArcNode *next;//指向下一条弧的指针
    InfoType info;//网的边权值
    }ArcNode;
    typedef struct VNode{
    VertexType data;
    ArcNode *first;
    }VNode,AdjList[MaxVertexNum];
    typedef struct{
    AdjList vertices;
    intVexnum arcnum;
    }ALGroph
  2. 若G为无向图,则所需存储空间为$O(|V|+2|e|)$,
    若为有向图,则所需存储空间为$O(|V|+|e|)$,
    前者的2是因为无向图中每条边出现了两次。

  3. 对于稀疏图,适用于邻接表存储,节约存储空间。
  4. 在邻接表中,给定顶点能容易的找到领边,反之矩阵不行($O(n)$)
    在邻接矩阵中,可以快速查找两个顶点是否存在边。
  5. 在有向图的邻接表表示中,求给定节点出度仅需计算其邻接表中结点个数,但入度需要遍历整个邻接表。因此有逆邻接表表示,不唯一。

§4.十字链表表示法

    • 弧结点
tailVexheadVexhlinxtlinkinfo
尾域头域弧头相同弧尾相同
  • 顶点结点
datafitstinfistout
  1. 示例 示例

  2. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #define MaxVertexNum 100
    typedef struct ArcNode{ //边表结点
    int tailVex,headVex; //头尾节点
    struct ArcNode *hlink,*tlink; //指向弧头相同与弧尾相同节点
    //InfoType info; //相关信息指针
    }ArcNode;
    typedef struct VNode{ //顶点表结点
    VertexType data; //顶点信息
    ArcNode *firstin,*firstout; //指向第一条弧与出弧
    }VNode;
    typedef struct{ //邻接表
    VNode *list[MaxVertexNum];
    int Vexnum,arcnum; //顶点数与弧数
    }GlGraph;

§5.邻接多重表

  1. 临接多重表:无向图的另一种链式存储结构。“数组(顶点)+边结点”

  2. 容易求得顶点和边的各种信息,但在邻接表中求两个顶点是否存在边,或需对边执行删除等操作,需分别在两个顶点的边表遍历。

markivexilinkjvexjlinkinfo
标志域(是否遍历)下一顶点ivex边下一顶点jvex边
  • 顶点
datafirstdye
  1. 示例

    示例

  2. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #define MaxVertexNum 100
    typedef struct ArcNode{
    bool Mark; //访问标记
    int ivex,jvex; //指向弧结点
    struct ArcNode *ilink,*jlinkl //分别指向两个结点下一条边
    //InfoType info; //相关信息指针
    }ArcNode
    typedef struct VNode{ //顶点表结点
    VertexType data; //顶点信息
    ArcNode *firstedge //指向第一条弧与出弧
    }VNode;
    typedef struct{ //邻接表
    VNode adjmulist[MaxVertexNum];
    int Vexnum,arcnum; //顶点数与弧数
    }GlGraph;

§6.最小生成树

  1. 最小生成树(MST):图的极小连通子图,包含所有顶点和尽可能少的边。

  2. 对最小生成树,砍去一条边构成非连通图,增加一条边则形成回路。

  3. 性质:

    • 最小生成树不唯一
    • 权值之和为1
    • 边数=顶点数-1
  4. 普里姆(Prim)算法:

    1. 开始时,$U={v_0},TE=\varnothing$,
    2. 计算$U$到某余顶点$V-U$的最小代价,纳入$U$,边纳入$TE$
    3. 重复 2 知道$U=V$
  5. 克鲁斯卡尔(Kruskal)算法:“不够成环情况下,每次先选择最小边”,适用于边稀疏且顶点多的树,结果不唯一。

算法普里姆克鲁斯卡尔
时间复杂度$O(n^2)$$O(e\log{e})$
特点只与顶点个数n有关只与边数e有关
与边数e无关与顶点个数n无关
适用于稠密图适用于稀疏图
  1. Dijkstra 算法(单源带权图)

    1. 初始化:用起点$V$到该顶点$w$的直接边(弧)初始化最短路径,否则设为$\infty$,用$dist[]$ 记录,$dist[i]$ 处置$arcs[VD][i]$;
    2. 从未求得最短路径的终点中选择长度最小终点$V$,求$V→U$最短路径;
    3. 修改最短路径:计算$U$的邻接点的最短路径,若$(V,\dots,U)+(u,v)<(V,\dots,W)$,以$(V,\dots,V,W$代替;
    4. 重复2,3,知道求出$v$到其余所有结点的最短路径。
  2. 若用邻接矩阵表示,则时间复杂度为$O(|v|2)$。若求源点到其他所有结点最短路径,其时间复杂度为$O(|v|^2)$。若找出所有结点对之间的最短距离,时间复杂度$O(|v|^3)$.

  3. Dijstra算法不适用边上有负权值的图。

  4. Floyd算法。依次计算$A^{(0)},A^{(1)},A^{(2)},\dots,A^{(n)}$。计算$A^{(k)}_{ij}=\min{A^{(k-1)}}(i,j),A^{(k-1)}(i,k)+A^{(k-1)}(k,j)$

  5. 时间复杂度$O(|V|^3)$

§7.其他

  1. 拓扑排序:“每次删除入度为0的顶点并输出”

  2. 有向无环图(DAG):一个有向图中不存在环

  3. AOV网:用有向边$<V_i,V_j>$表示活动$V_i$必须先于活动$V_j$进行的一种关系,将这种有向图称为顶点表示活动的网络。

  4. 关键路径:在带权有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成活动的开销(如:花费时间),则称这种有向图为用边表示活动的网络,简称为AOE网。

-------文章到此结束  感谢您的阅读-------