Skip to content

Latest commit

 

History

History
439 lines (239 loc) · 9.89 KB

05图.md

File metadata and controls

439 lines (239 loc) · 9.89 KB
Raw

图的基本概念

  • 有向图：弧室定点的有序对 <v,w>

  • 无向图：无向边的有限集合

  • 简单图：

    • 不存在重复边
    • 没有到自己的边

  • 完全图：

    • n个顶点，无向完全图有n(n-1)/2条边
    • 有向完全图n(n-1)条边

  • 连通

    • 在无向图中，若v到w有路径存在，v和w是连通的。若图G中任意两个顶点时连通的，则是连通图
    • 极大连通子图是无向图的连通分量，要求包含所有的边。
    • 极小连通子图是连通的但边最少。

  • 强连通

    • 在有向图中，从顶点v到w相互有路径，这两个点强连通
    • 任何一对顶点都强连通->强连通图

  • 生成树和生成森林

    • 连通图的生成树是包含全部顶点的极小连通子图
    • 若有n个顶点，就是在生成树中有n-1条边
    • 当砍一条边就变成非连通，加上一条边可以形成回路
    • 在非连通图中，连通分量的生成树构成了非连通图的生成森林

  • 顶点的度/入度/出度

    • 无向图中只有度：度是边数的2被
    • 入度：以顶点v为终点

  • 边的权和网

    • 边上有权值的图：网
    • 当|E| < |v|log|v|的时候，G为稀疏图

  • 路径和路径长度

    • 顶点Vp到顶点Vq之间的一条路径是顶点Vp，Vi，Vj...Vq
    • 路径上边的数目是路径长度

  • 简单路径/简单回路

    • 简单路径：顶点不重复出现的路径
    • 简单回路：除了首尾顶点，其余顶点不重复

  • 距离

    • u到v最短路径若存在，就是u到v的距离

图的存储和基本操作

  • 邻接矩阵法

    • #define MaxVertexNum 100
typedef char VertexType;  //顶点
typedef int EdgeType; //边上权值
typedef struct
{
    VertexType Vex[MaxVertexNum]; //顶点表
    EdgeType Edge[MaxvertexNum][MaxvertexNum]; //邻接矩阵
    int vexnum,arcnum; //顶点and弧数
}MGraph;

  • 邻接表法

    • 特点

      • 无向图，存储空间O(|V|+2|E|)
      • 有向图，存储空间O(|V|+|E|)
      • 稀疏图，邻接表可以节省大量空间
    • #define MaxVertexNum 100
typedef struct ArcNode
{
    //边表
    int adjvex; //弧指向的顶点的位置
    struct ArcNode *next; //指向下一条弧的指针
}ArcNode;
typedef struct VNode
{
    //顶点表
    VertexType data;
    ArcNode *first;  //指向第一条依附该顶点的弧
}VNode,Adjlist[MaxVertexNum];
typedef struct
{
    AdjList vertices; // 邻接表
    int vexnum,arcnum; //图的顶点和弧
}ALGraph;

  • 十字链表

    1.tailvex和headvex分别指示弧尾和弧头这两个顶点在图中的位置。hlink指向弧头相同的下一条弧，tlink指向弧尾相同的下一条弧。

    2.顶点结点中，data放顶点相关的数据信息，firstin和firstout分别指向该顶点为弧头或弧尾的第一个弧结点。

​ 3.图的十字链表

#define MaxVertexNum 100
typedef struct ArcNode //边表结点
{
    int tailvex,headvex; //弧的头尾结点
    struct ArcNode *hlink,*tlink; //指向弧头相同和弧尾相同的结点
}ArcNode;
typedef struct VNode
{//顶点表结点
    VertexType data;
    ArcNode *firstin, *firstout; //指向第一条入弧和出弧
}VNode；
typedef struct
{
    VNode xlist[MaxVertexNum]; //邻接表
    int vexnum，arcnum; // 图的顶点数和弧数
}GLGraph;

​ 4.既容易找到vi为尾的弧，又容易找到vi为头的弧，所以容易求得顶点的出度和入度。

  • 邻接多重表
    1. 是无向图的一种链式存储结构
    2. 在邻接表中，容易求得顶点和边的各种信息，但是邻接表中求两个顶点之间是否存在边而对边执行删除等操作时，需要分别在两个顶点的边表中遍历，效率低。
    3. 每条边也用一个结点表示，mark标记该边是否被搜过，ivex和jvex为该边依附的两个顶点在图中的位置。ilink指向下一条依附于顶点ivex的边，jlink指向下一条依附于顶点jvex的边。
    4. data域存储该顶点信息，firstedge域指示第一条依附于该顶点的边。
#defin MaxVertexNum 100
typedef struct ArcNode
{ //边表结点
    bool mark; //访问标记
    int ivex,jvex; //分别指向该弧的两个结点
    struct ArcNode *ilink,*jlink; //分别指向两个顶点的下一条边
}ArcNode;
typedef struct VNode
{//顶点表结点
    VertexType data;//顶点信息
    ArcNode *firstedge;//指向第一条依附该顶点的边
}VNode;
typedef struct
{
    VNode adjmulist[MaxVertexNum];//邻接表
    int vexnum,arcnum;//图的顶点数和弧数
}AMLGraph;

图的遍历

  • 广度优先搜索：是一种分层的查找过程

    • bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G)
{
    for(int i = 0; i < G.vexnum; ++i)
        visited[i] = FALSE; //访问标记数组初始化
    InitQueue(Q); //初始化辅助队列Q
    for(int i = 0; i < G.vexnum; ++i) //从0号顶点开始遍历
        if(!visited[i]) //对每个连通分量调用一次BFS
            BFS(G,i);
}
void BFS(Graph G, int v)
{
    visit(v);//访问初始顶点v
    visited[v] = TRUE;//对v做已访问标记
    Enqueue(Q,v);//顶点v入队
    while(!isEmpty(Q))
    {
        Dequeue(Q,v);//顶点v出队
        for(w = FirstNeighbor(G,v); w >= 0; w = NextNeighbor(G,v,w))
        {//检测v所有邻接点
            if(!visited[w])//w为v尚未访问的邻接顶点
            {
                visit(w);
                visited[w] = TRUE;
                EnQueue(Q,w);
            }
        }
    }
}

    • 广度优先搜索和二叉树的层次遍历是完全一致的

    • 时间复杂度

      • 采用邻接表时O(|V|+|E|)
      • 采用邻接矩阵O(|V|^2)

    • 广度优先生成树

      • 邻接矩阵的存储表示唯一，所以生成树唯一
      • 邻接表的存储表示不唯一，所以生成树不唯一

  • 深度优先：类似于树的先序遍历

    • bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
    for(int v = 0;v < G.vexnum; ++v)
        visited[v] = FALSE;
    for(int v = 0;v < G.vexnum; ++v)
        if(!visited[v])
            DFS(G,v);
}
void DFS(Graph G,int v)
{
    visit(v);
    visited[v] = TRUE;
    for(w = FirstNeighbor(G,v); w>= 0; w = NextNeighor(G,v,w))
        if(!visited[w])
        {
            DFS(G,w);
        }
}

    • 时间复杂度

      • 邻接矩阵，O(|V|^2)
      • 邻接表，O(|V|+|E|)

    • 深度优先的生成树

      • 对连通图调用DFS才能产生深度优先生成树，否则深度优先生成森林
      • 对于邻接表处处的深度优先生成树是不唯一的

    图的应用

  • 最小生成树：是图的极小连通子图，包含了所有顶点和尽可能少的边。

    • 若砍去他的一条边就会变成非连通图。
    • 若增加一条就会形成回路
    • 最小生成树不是唯一的，但是各边权值不同时，最小生成树是唯一的，。
    • 最小生成树的边的权值之和是惟一的
    • 最小生成树的边数为顶点数减1

  • prim算法

    • 类似于寻找图的最短路径，重复去找相连的点中代价最小的一条边，构造最小生成树。
    • 时间复杂度是O(|V|^2)不依赖于|E|，适用于求解边稠密的图的最小生成树。
    • 过程如图

  • Kruskal算法

    • 按照权值的递增次序找合适的边，来构造最小生成树
    • 时间复杂度O(|E|log|E|),所以适合于边稀疏顶点多的图

  • 最短路径

    • 广度优先遍历是找无权图的最短路径
    • 带权图路径长度最短的就是最短路径
    • 分类
      • 单源最短路径 - Dijkstra
      • 每个顶点间的最短路径 - Floyd

  • Dijkstra求单源最短路径

    • 集合S记录最短路径的顶点，s[vi]=1表示顶点Vi放入了S。
    • 辅助数组
      • dist[]:记录V0到其他顶点当前的最短路径长度，dist[i]初始为arcs[v0] [i]
      • path[]:path[i]表示源点到顶点i之间的最短路径的前驱结点，结束时可以追溯整条路径
    • 基于贪心策略，时间复杂度O(|V|^2)

  • Floyd求个顶点直接的最短路径问题

    • 基本思想：列出起始状态后，每次更新经过某个顶点，所有的路径是否变短
    • 允许带负权值，单不允许包含负权值的边组成回路

  • 拓扑排序

    • 有向无环图：有向图中不存在环
    • AOV网：若DAG图表示一个工程，顶点是活动，有向边<Vi,Vj>表示活动Vi必须在Vj前进行，这种顶点表示活动的网络就是AOV网。
    • 拓扑排序满足
      • 每个顶点只出现一次
      • 顶点A在顶点B前面，则不存在顶点B到顶点A的路径
    • 时间复杂度是O(|V|+|E|)
    • 先找一个入度为0的结点，删除他的边，输出，重复。

  • 关键路径

    • 带权有向图中国，顶点表示事件，边表示活动（权值表示开销），叫作AOE网
    • 性质
      • 某顶点时间发生后，从这个顶点出发的各有向边代表的活动才开始
      • 只有进入某一顶点的各有向边所代表的活动结束，该顶点所代表的的时间才能发生
    • 开始顶点（入度为0）是源点，结束顶点（出度为0）是汇点。
    • 最大路径长度的路径叫作关键路径，关键路径上的活动事关键活动
    • 找关键活动的几个定义
      • 事件Vk的最早发生时间Ve(k):开始顶点到Vk的最大路径长度
      • 事件Vk的最迟发生时间V1(k):不推迟整个工程完成的前提下的最迟发生时间
      • 活动最早开始时间
      • 活动最迟开始时间
    • 关键路径上的所有活动都是关键活动，可以通过加快关键活动来缩短工期，但可能会变成非关键
    • 关键路径不是唯一的