Data Structures and Algorithms-Graph

基础知识

邻接矩阵

用A(G)表示图G的邻接矩阵，$a_{ij}$指的是顶点$v_i$和$v_j$的连接信息。

如果是有向图，$a_{ij}$指的是顶点$v_i$到$v_j$有无有向边。

无向图的邻接矩阵对称，可压缩存储；有向图邻接矩阵不一定对称。

有向图中， 顶点Vi的出度是邻接矩阵中第i行元素之和

顶点Vi的入度是邻接矩阵中第i列元素之和。

有向图和无向图中不邻接的顶点是0，但是对于带权图，不不邻接的顶点是无穷。

优缺点：

• 优点
  • 便于判断两个顶点之间是否有边。
    便于计算各个顶点的度。
• 缺点
  • 不便于增加和删除顶点。
  • 不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为0(n2)。
  • 空间复杂度高。对于稀疏图而言尤其浪费空间。

邻接表

思路是，为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧)，再用一个顶点数组指向每个单链表。

• 定点表结点：
  • vexinfo:顶点信息
  • firstarc:第一条关联边结点
• 边表结点：
  • adjvex:临接结点位置
  • arcinfo：边的信息
  • nextarc:下一条关联边边表结点

typedef struct Arcnode{
    int adjvex; //该弧所指向的顶点的位置
    struct Arcnode* nextarc;  //指向下一条弧的指针
}Arcnode;

• 无向图中，单链表中,Arc结点个数=边数*2

  有向图中，单链表中,Arc结点个数=弧数

• 无向图中顶点Vi的度为：第i个单链表中的结点数

  有向图中顶点Vi的出度为：第i个单链表中的结点数,顶点Vi的入度为：整个单链表中邻接点域为i的结点个数;

逆邻接表

有向图中对每个结点建立以Vi为头的弧的单链表

找逆邻接点容易

邻接表（网）

网：边上带有权值的图

adjvex	weight	nextarc

优缺点

• 优点

  • 便于增加和删除顶点

  • 便于统计边的数目

  • 空间效率高

• 缺点

  • 不便于判断定点之间是否有边
  • 不便于计算有向图各个顶点的度

十字链表

• 头节点
  • vexinfo:顶点的信息
  • firstin:第一条关联入狐结点
  • firstout:第一条关联出弧结点
• 表结点
  • tailvex:弧尾结点位置
  • headvex:弧头结点位置
  • arcinfo:弧的信息
  • tnext:弧尾相同的下一条弧
  • hnext:弧头相同的下一条弧

多重邻接链表

• 头节点存储
  • vexinfo:顶点的信息
  • firstedge:第一条关联边结点
• 边结点存储
  • flag:标志域，是否遍历过
  • einfo:边的信息
  • ivex:边的第一个顶点位置
  • inext:边的另一个顶点位置
  • jvex:边的另一个顶点位置
  • jnext:顶点j的下一条关联边

十字链表和邻接多重表的比较

十字链表：

专门用于表示有向图。

每个顶点都有两个链表：一个是出弧链表，用于存储从该顶点出发的所有边；另一个是入弧链表，用于存储指向该顶点的所有边。

这种表示法使得查询任何顶点的入度和出度都变得非常简单和快速。

工程应用：

适用于需要频繁查询顶点入度或出度的应用场景，例如某些依赖性分析、工作流管理等。**

用于网络流算法中，需要快速访问入弧和出弧，如最大流问题。

邻接多重表：

专门用于表示**无向图。**

相较于邻接表，邻接多重表只为每条边存储一次，从而更加节省空间。

便于判断边是否存在，以及快速删除边。

工程应用：

适用于需要频繁添加或删除边的应用场景。

在网络设计和拓扑结构分析中，这种数据结构可以帮助有效地查询和管理连接。

在无向图的算法中，如最小生成树、图的双连通分量分析等，都可以考虑使用邻接多重表。

图的遍历

深度遍历

• 访问一个顶点V，然后访问该顶点邻接到的未被访问过的顶点V’，
• 再从V’出发递归地按照深度优先的方式周游，
• 当遇到一个所有邻接于它的顶点都被访问过了的顶点U时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，
• 再从W出发递归地按照深度优先的方式周游，
• 最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则周游结束。

图的遍历顺序未必唯一。

广度优先遍历

它的基本思想是

• 访问顶点V0，
• 然后访问V0邻接到的所有未被访问过的顶点V01，V02，…V0i，
• 再依次访问V01，V02，…V0i邻接到的所有未被访问的顶点，
• 如此进行下去r，直到访问遍所有的顶点。

用队列 实现广度优先遍历。

因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两种遍历方法的不同之处仅仅在于对顶点访问的顺序不同。

用邻接矩阵表示图的时候，查找每个顶点的邻接点的复杂度为$O(n^2)$, $n$为顶点数。

当以邻接表做图的存储结构时，查找邻接点的时间复杂度为O(e),其中e为图中边数，深度优先搜索 遍历图的时间复杂度为O(n+e)。

拓扑排序和关键路径

拓扑排序

拓扑排序（Topological Sort）就是从某积和上的一个偏序得到该集合的一个全序。、

用顶点表示活动，用弧表示活动之间优先级关系的有向图成为顶点表示活动的网络（Activity On Vertex Network）即AOV-网。

在AOV-网中，不应该出现有向环，因为存在有向环证明某项活动以自己为先决条件，这显然是谬误的。

实现拓扑排序：

• 在有向图中选一个没有前驱的顶点输出之；
• 从图中删除该顶点和所有以它为尾的弧。
• 重复上述两步，直至全部顶点都已经输出，或者当前图中不存在无前驱的顶点为止，后一种情况说明无向图中存在环。

有向图的邻接表实现：

注：邻接表是尾每一个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点$v_i$的边（对于有向图是以顶点$v_i$为尾的弧）

//边的结构体
typedef struct Arcnode{
    int adjvex;//该弧指向的顶点的位置
    struct Arcnode* nextarc;//指向下一条弧的指针
    InfoType* info;//该弧相关信息的指针
}Arcnode;

//顶点的结构体
//对于该任务，我们新增一个域，即入度域
typedef struct Vnode{
    VertexType data;//数据域
    int in;//入度域
    Arcnode* firstarc;  //指向该顶点的第一条出边
}Arcnode,AdjList[Max_Vertex_Num];

//图的结构体
typedef struct{
    AdjList vertices;//图的顶点集合（邻接表）
    int vexnum, arcnum; // 图的顶点数图的边数
}ALGraph;

AdjList 定义了一个数组类型，数组大小是 Max_Vertex_Num，表示图中最多可以存储 Max_Vertex_Num 个顶点。AdjList vertices;表示

求各个顶点入度的函数

void CountInDegreee(ALGraph *G){
    int i; 
    Arcnode* p；//设一个指针用于表示弧
    for(i=1;i<=G.vexnum;i++){
        G.vertices[i]->in=0;
    }//初始时全部设置为0
    for(i=1;i<=G.vexnum;i++){//遍历结点
        for(p=G.vertices[i].firstarc;p;p=p->nextarc){//遍历所有有向弧
            G.vertices[p->adjvex]->in++;//该弧指向的结点的入度+1
        }
    }
}

拓扑排序的时候，

• 1）求出各顶点的入度存入数组indegree［i］中，并将入度为0的顶点入栈。

• 2）只要栈不空，则重复以下操作： 将栈顶顶点vi出栈并保存在拓扑序列数组topo中; 对顶点vi的每个邻接点vk的入度减1,如果vk的入度变为0,则将n入栈。

• 3）如果输出顶点个数少于AOV-网的顶点个数，则网中存在有向环，无法进行拓 扑排序，否则拓扑排序成功。

拓扑排序函数:

Status TopologicalSort(ALGraph G){
    int i,j,k;
    int count; //记载排好序的数量
    ArcNode *p; //由于表示某一个结点的弧
    int S[max];//栈，用于存储入度为0的结点
    int top=0;//栈顶
    
    //1.计算每一个顶点的入度
    CountInDegree(G);
    
    //2.入度为0的结点入栈
    for(i=1;i<=G.vexnum;i++){
        if(G.vertices[i].in==0){
            S[top++]=i; //入栈，栈顶指针+1
        }
    }
    //3.重复检测栈是否为空
    while(top!==0){
        j=S[--top]; //得到栈顶元素的结点编号
        count++;//出栈了一个元素，计数器+1
        printf("顶点%d",j);
        //3.1 将出栈顶点的所有边断开，然后更新与之相连的结点的度
        for(p=G.vertices[j].firstarc;p;p=p->nextarc){
            k=p->adjvex;//弧p 指向的顶点编号
            if(--G.vertices[k].in==0){//将弧p指向的结点的入度-1，检测此时入度是否为0
                S[top++]=k;//结点k入栈               
            }
        }      
    }
    //4.判断输出结点是否小于图的结点个数
    if(count<G.vexnum){
            return ERROR;
    }
    return OK;
}

关键路径

与AOV-网相对应的是AOE-网（Activity On Edge）即边表示活动的网。AOE-网是一个带权的有向无环图。

在AOE-网中，弧表示活动，顶点表示事件，权表示活动持续时间。事件必须要等到活动完成后才会发生。

比如：

通常，AOE-网可以估算工程的完成时间，比如上述图中，完成活动需要的最短时间就是27.

路径最长的路径叫做关键路径(Critical Path).

一些术语

• e(i) 活动i的最早开始时间
• l(i) 活动i的最晚开始时间
• dut() 活动i用弧表示，持续时间为dut()
• ve(j) 事件j的最早开始时间
• vl(j) 事件j的最晚开始时间

显然我们可以得到，一个活动最早开始的时间就是它的前驱事件的最早开始时间。即e(i)=ve(j),同时这个活动的最晚开始时间，就是他后继事件的最晚开始时间减去活动的持续时间，即v(i)=vl(k)-dut().

ve(j)和vl(j)的求解

对于一个事件j,为了求ve(j)，可以采取前向递推的方法求解:

ve(0)=0

ve(j)=Max{ve(i)+dut()},

∈T，j=1,2,~n-1.

其中，T是所有以第j个顶点为头的弧的集合。

对于一个事件j,为了求vl(j)，可以采取后向递推的方法求解:

vl(n-1)=ve(n-1)

vl(j)=Min{vl(j)-dut()},

∈S，j=n-2,~0

其中，S是所有以第i个顶点为尾的弧的集合。

关键路径算法

算法步骤：

• （1）输入顶点和弧信息，建立其邻接表
• （2）计算每个顶点的入度
• （3）对其进行拓扑排序 排序过程中求顶点（事件）的Ve[i] 将得到的拓扑序列进栈
• （4）按逆拓扑序列求顶点（事件）的Vl[i]
• （5）计算每条弧（活动）的e[i]和l[i],找出e[i]=l[i]的关键活动

首先，在拓扑排序的算法基础上，我们设置一个函数，可以在拓扑排序的同时，找到每一个结点的最长路径。

Status QuiVe(ALGraph G,int ve[M+1],int Sn[M+1]){
    //Sn栈用于存储拓扑排序后的顶点顺序
    int S[M];     //一个栈，用于保存当前入度为0的顶点。
    int top=0;    //S栈指针
    int topnixu=0; //Sn栈的指针
    int i,j,k;
    int count=0;
    ArcNode* p; //弧的指针
    //1.将所有入度为0的结点入栈
    for(i=1;i<=G.vexnum;i++){
        if(G.vertices[i].in==0){
            S[top++]=i;
        }
    }
    //2.循环检测，实现拓扑排序
    while(top!=0){
        //2.1栈顶元素出栈
        j=S[--top];//栈顶元素出栈
        count++;//计数器+1
        Sn[topnixu++] = j;  // 记录拓扑排序结果，Sn存储顺序
        //2.2更新入度
        for(p=G.vertices[j]->firstarc;p=p->nextarc){
            k=p->adjvex;//k是弧p的后继节点
            if(--G.vertices[k].in==0){//如果更新后入度为0
                S[top++]=k; //将该结点入栈
            }
            //2.3更新事件最早开始时间
            if(ve[j]+p->length>ve[k]){
                ve[k]=ve[j]+p->length;
            }            
        }
    }
    if (count<G.vexnum){
        return ERROR;
    }
    return OK;
}

求关键路径

void CriticalPath(ALGraph G,int ve[M+1],int Sn[M+1]){
    int topnixu=M; //拓扑排序结果的指针，将其即为M,因为求vl需要反向递推
    int j,k;
    int ee;    //存储某条边的开始时间
    int el;    //存储某条边的结束时间
    int vl[M+1]; //事件的最晚开始时间
    //1.初始化最晚开始时间
    for(i=1;i<=G.vexnum;++i){//从2开始
        vl[i]=ve[M];    //初始化最晚完成时间为 ve[M]（即最长路径的长度）        
    }
    //2.计算每个顶点的最晚开始时间：
    while(topnixu!=0){
        j=Sn[--topnixu];   //取出栈顶元素
        for(p=G.vertices[j].firstarc;p=p->nextarc){
            k=p->adjvex;
            //更新每个节点的最晚完成时间
            if((vl[k] - p->length) < vl[j]) {
                vl[j]=vl[k] - p->length;
            }
        }
    }
    //计算关键路径
    for(j=1;j<=G.vexnum;j++){
        for(p=G.vertices[j].firstarc;p=p->nextarc){
            k=p->nextarc;
            ee=ve[j];//该边的最早开始时间
            el=vl[k]-p->length;//该边的最晚开始时间，等于后继节点的最晚开始时间减去该边长度
            //如果某一个边的最短开始时间和最晚开始时间相同，就是关键路径。
            if(ee==el){
                printf(("%d到%d长度为%d的边为关键活动\n", j, k, p->length);
            }
        }
    }  
    
}