图

1.图的定义

  图G由顶点集V和边集E组成，记为G=（V,E），其中V（G）表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系（边）集合。若V={V1,V2,V3,···,Vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u,v)|u∈V,v∈V}，则|E|表示图G中边的条数

  注意：线性表可以是空表，数可以说空树，但是u不可以是空，也就是其中的V一定是非空集

• 有向图

• 无向图

• 度

• 路径

• 连通图

• 子图

• 连通分量

• 强连通分量

• 特殊的图

 

2.图的存储——邻接矩阵法

#define MaxVertexum 100
typedef struct
{
    char Vex[MaxVertexNum];     //顶点表
    int Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵边表
    int vexnum,arcnum;              //图当前顶点数和边数
}MGraph;

• 邻接矩阵法存储带权图

#define MaxVertexum 100
#define INFINITY 最大的int值  //可用int的上限值表示“无穷”
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
    VertexType Vex[MaxVertexNum];     //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  //邻接矩阵边表
    int vexnum,arcnum;              //图当前顶点数和边数
}MGraph;

• 性能分析

  空间复杂度为：O(|V|²) ——只和顶点数相关，和实际的边数无关

  可以看见在矩阵图存储中，会存在没有边的情况，如果一个图的边过少，则会浪费大量的存储空间，所以这种存储方式适用于存储稠密图，注：无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

• 性质分析

 

3.邻接表法（顺序+链式）

//用邻接表存储的图
typedef struct
{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

//边
typedef struct ArcNode
{
    int adjvex;       //边指向哪个结点
    struct ArcNode *next; //指向下一条边的指针
}ArcNode；
    
//顶点
typedef struct VNode
{
    VertexType data;    //顶点信息
    ArcNode *first;    //第一条边
}VNode,AdjList[MaxVertexNum];

• 与邻接矩阵的对比

 

4.十字链表法

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

  空间复杂度：O(|V|+|E|)

 

5.邻接多重表

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

  空间复杂度：O(|V|+|E|)

 

6.四种方法比较

 

7.图的基本操作

  Adjacent(G,x,y)：判断图G是否存在边或(x, y)。

  Neighbors(G,x)：列出图G中与结点x邻接的边。

  InsertVertex(G,x)：在图G中插入顶点x。

  DeleteVertex(G,x)：从图G中删除顶点x。

  AddEdge(G,x,y)：若无向边(x, y)或有向边不存在，则向图G中添加该边。

  RemoveEdge(G,x,y)：若无向边(x, y)或有向边存在，则从图G中删除该边。

  FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点 或图中不存在x，则返回-1。

  NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一 个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

  Get_edge_value(G,x,y)：获取图G中边(x, y)或对应的权值。

  Set_edge_value(G,x,y,v)：设置图G中边(x, y)或对应的权值为v。

8.图的广度优先遍历算法

• 起初版

bool visited[MAX_VERTEX_NUM];

//广度优先遍历
void BFS(Graph G,int v)          //从顶点v出发，广度优先遍历图G
{
    visit(v);                   //访问初始结点v
    visited[v]=TRUE;            //对v做已访问标记
    Enqueue(Q,v);               //顶点v入队伍Q
    while(!isEmpty(Q))          
    {
        DeQueue(Q,v);        //顶点v 出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有的邻接点
            if(!visted[w])
            {
                visit(w);            //访问顶点w
                visit[w]=TRUE;       //对w做已访问标记
                EnQueue(Q,w);       //顶点w入队伍
            }
    }
}

• Final版

bool visited[MAX_VERTEX_NUM];  //访问标记数组
void BFSTraverse(Graph,G)   //对图G进行广度优先遍历
{	
    for(i=0;i<G.vexnum;++i)
        visited[i]=FALSE;    //访问标记数组初始化
    InitQueue(Q);            //初始化辅助队列
    for(i=0;i<G.vexnum;++i)  //从0号顶点开始遍历
        if(!visited[i])     //对每一个连通分量调用一次BFS
            BFS(G,i);      //vi未访问过，从vi开始BFS
}

//广度优先遍历
void BFS(Graph G,int v)          //从顶点v出发，广度优先遍历图G
{
    visit(v);                   //访问初始结点v
    visited[v]=TRUE;            //对v做已访问标记
    Enqueue(Q,v);               //顶点v入队伍Q
    while(!isEmpty(Q))          
    {
        DeQueue(Q,v);        //顶点v 出队列
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            //检测v所有的邻接点
            if(!visted[w])
            {
                visit(w);            //访问顶点w
                visit[w]=TRUE;       //对w做已访问标记
                EnQueue(Q,w);       //顶点w入队伍
            }
    }
}

• 复杂度分析

• 广度优先生成树

• 注：有向图的BFS过程

 

9.图的深度优先遍历

• 起初版

bool visited[MAX_VERTEX_NUM];

void DFS(Grah G,int v)
{
    visir(v);     //从顶点v出发，深度优先遍历图G
    visited[v]=TURE;   //访问顶点v
    for(W=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visit[w])         //w为u的尚未访问的邻接顶点
        {
            DFS(G,w);
        }
}

• Final版

bool visited[MAX_VERTEX_NUM];

void DFSTraverse(Graph,G)   //对图G进行深度优先遍历
{	
    for(v=0;v<G.vexnum;++v)
        visited[v]=FALSE;    //访问标记数组初始化
    for(v=0;v<G.vexnum;++v)  //从0号顶点开始遍历
        if(!visited[v])     //对每一个连通分量调用一次BFS
            DFS(G,v);      //vi未访问过，从vi开始BFS
}

void DFS(Grah G,int v)
{
    visir(v);     //从顶点v出发，深度优先遍历图G
    visited[v]=TURE;   //访问顶点v
    for(W=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,w))
        if(!visit[w])         //w为u的尚未访问的邻接顶点
        {
            DFS(G,w);
        }
}

  解决了非连通图无法遍历完所有结点的问题

• 复杂度分析

• 深度优先生成树

 

10.最小生成树

• 生成树的定义

  连通图的生成树是包括图中全部顶点的一个极小连通子图，若图中的顶点数维n，则它的生成树含有n-1条边，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路

• 最小生成树的定义

  对于一个带权连通无向图G(V,E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树

 

• Prim算法（普利姆）

  从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有的顶点都纳入为止

• Kruskal算法（克鲁斯卡尔）

  每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的不选），直到所有的结点都连通

• 算法对比

 

11.最短路径

• BFS算法——单源最短路径问题

//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(Graph G,int u)
{
    //d[i]表示从u到i结点的最短路径
    for(i=0;i<G.vexnum;++i)
    {
        d[i]=∞;    //初始化路径长度
        path[i]=-1;   //最短路径从哪个顶点过来
    }
    d[u]=0;    //自己到自己的距离为0
    visited[u]=TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q))     //BFS算法主过程         
    {
        DeQueue(Q,u);        //队头元素u出队列
        for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
            if(!visted[w])        //w为u的尚未访问的邻接顶点
            {
                d[w]=d[u]+1;         //路径长度加1
                path[w]=u            //最短路径应从u到w
                visit[w]=TRUE;       //设置已访问标记
                EnQueue(Q,w);       //顶点w入队伍
            }
    }
}

  BFS算法求单源最短路径只适⽤于⽆ 权图，或所有边的权值都相同的图

• Dijkstra算法

  注：Dijkstra算法不适合用于有负权值的带权图

• Floyd算法

  使用了动态规划思想，将问题的求解分为了多个阶段

//准备工作，根据图的信息初始化矩阵A和path

for(int k=0;k<n;k++)     //考虑以VK作为中转点
{
    for(int i=0;i<n;i++)   //遍历整个矩阵，i为行号，j为列号
    {
        for(int j=0;j<n;j++)
        {
            if(A[i][j]>A[i][k]+A[k][j])
            {
                A[i][j]=A[i][k]+A[k][j];  //更新最短路径长度
                path[i][j]=k;           //中转点
            }
        }
    }
}

  这种算法的时间复杂度是|V|³，空间复杂度是|V|²

• 三种算法对比

 

12.有向无环图（DAG）

  有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图

 

13.拓扑排序

• AOV网的定义

  ⽤顶点表示活动的⽹，⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边表示活动<Vi,Vj>，必须先于活动Vj进⾏

• 拓扑排序的定义

  在图论中，由⼀个有向⽆环图 的顶点组成的序列，当且仅当满⾜下列条 件时，称为该图的⼀个拓扑排序：

   ① 每个顶点出现且只出现⼀次。

  ② 若顶点A在序列中排在顶点B的前⾯，则 在图中不存在从顶点B到顶点A的路径。

• 拓扑排序实现代码

 

14.逆拓扑排序

• 逆拓扑排序定义

  对⼀个AOV⽹，如果采⽤下列步骤进⾏排序，则称之为逆拓扑排序：

   ① 从AOV⽹中选择⼀个没有后继（出度为0）的顶点并输出。

   ② 从⽹中删除该顶点和所有以它为终点的有向边。

   ③ 重复①和②直到当前的AOV⽹为空。

• 逆拓扑排序实现代码

  第一种方法是参考拓扑排序将入度的比较改变为出度的比较即可，第二种是利用DFS算法实现

 

15.关键路径

• AOE网的定义

  在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如 完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹

  在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它代表整个工程的开始；也仅有一个出度为0的顶点，称为结束顶点（汇点），它代表整个工程的结束

  从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为 关键路径，⽽把关键路径上的活动称为关键活动

• 事件vk的最早发⽣时间ve(k)

  决定了所有从vk开始的活动能够开⼯的最早时间

• 事件vk的最迟发⽣时间vl(k)

  它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间

• 活动ai的最早开始时间e(i)

  指该活动弧的起点所表⽰的事件的最早发⽣时间

• 活动ai的最迟开始时间l(i)

  它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差

• 活动ai的时间余量d(i)

  d(i)=l(i)-e(i)，表⽰在不增加完成整个⼯程所需总时间的情况下，活动ai可以拖延的时间 若⼀个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i) = e(i)的活动ai是关键活动 由关键活动组成的路径就是关键路径

• 关键活动、关键路径

  若关键活动耗时增加，则整个⼯程的⼯期将增⻓

  缩短关键活动的时间，可以缩短整个⼯程的⼯期

  当缩短到⼀定程度时，关键活动可能会变成⾮关键活动