数据结构(六)图

2021-08-23 本文已影响0人 AdRainty

6.1 图的基本概念

6.1.1 图的定义

图G由顶点集V和边集E组成，记为
$G=(V,E)$
线性表可以是空表，树可以是空树，但图不可以是空，V一定是非空集

图

若E是无向边的有限集合时，则G为无向图 $(V,W)=(W,V)$

若E是有向边的有限集合时，则G为无向图 $<V,W>=<W,V>$

有向图.png

6.1.2 顶点的度、入度和出度

对于无向图：顶点V的度是指依附于该顶点边的条数，记为 $TD(V)$

在具有n个顶点，e条边的无向图中，无向图的全部顶点度和等于边数的两倍，即
$\sum_{i=1}^{n}{v_i}=2le$
对于有向图：

入度是以顶点v为终点的有向边数，记为 $ID(V)$
出度是以顶点V为起点的有向边数，记为 $OD(V)$

顶点V的度等于入度和出度之和，即 $TD(V)=ID(V)+OD(V)$

在具有n个顶点，e条边的有向图中，入度和出度相等且等于边数，即
$\sum_{i=1}^{n}{ID(v_i)}=\sum_{i=1}^{n}{OD(v_i)=e}$

6.1.3 顶点-顶点的关系和概念

路径：顶点v_p到顶点v_q之间的一条路径，即顶点序列 $v_pv_1v_2\cdots v_q$

回路：第一个顶点和最后一个顶点相同路径称为回路或者环

路径长度：路径上边的数目

点到点的距离：从顶点u出发到顶点v的最短路径若存在，则称为从u到v的距离，若u到v不存在路径，记为无穷(∞)

连通：无向图中，若从顶点v到顶点w有路径存在，称v和w连通

强连通：有向图中，若从顶点v到顶点w，顶点w到顶点v之间都有路径，则称v和w强连通

对于n个顶点的连通图，最少有n-1条边

对于n个顶点的非连通图，最多有 $C_{n-1}^2$ 条边

对于n个顶点的强连通图，最少有n条边(形成回路)

连通分量：无向图中的极大连通子图

强连通分量：有向图中的极大连通子图

极大连通子图：子图必须连通，且包含尽可能多的顶点和边

连通图的生成树：包含图中全部顶点的一个极小连通子图

极小连通子图：边尽可能少，但要保证连通

网：边上带有权值的图

6.1.4 几种特俗形态的图

无向完全图：无向图中任意两个顶点有存在边

n个顶点的无向完全图有 $C_n^2$ 条边

有向完全图：有向图中任意两个顶点有存在方向相反的两条边

n个顶点的有向完全图有 $2C_n^2$ 条边

树：不存在回路，但连通的无向图

n个顶点的树有n-1条边

有向树：一个顶点的入度为0，其余顶点的入度均为1

n个顶点的图，若 $e>n-1$ 则一定有回路

6.2 图的存储及基本操作

6.2.1 邻接矩阵法

无向图的一边对应矩阵两个1，有向图只对应一个1

邻接矩阵法.png

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

邻接矩阵法求顶点的度、入度、出度的时间复杂度均为O(|V|)

设G的邻接矩阵为A，则Aⁿ的元素 $A^n[i][j]$ 等于由顶点i到顶点j的长度为n的路径的数目

6.2.2 邻接表法

邻接表法.png

typedef struct ArcNode{  // 边/弧
    int adjvex; // 边/弧指向哪个结点
    struct ArcNode *Next; //指向下一条弧的指针
}ArcNode;

typedef struct VNode{ //顶点
    VertexTyoe data; // 顶点信息
    ArcNode *first; //第一条边/弧
}VNode,AdjList[MaxVertexNum];

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

邻接表的空间复杂度对有向图 $O(|V|+|E|)$ ,对无向图 $O(|V|+2|E|)$

邻接表找有向图的入边不方便

6.2.3 十字链表

十字链表是专门对于有向图的一种存储

十字链表的存储.png

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

6.2.4 邻接多重表

邻接多重表是专门对于无向图的一种存储

邻接多重表的存储.png

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

6.2.5 图的基本操作

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

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

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

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

AddEdge(G,x,y)：若(x,y)或<x,y>不存在，则添加该边

RemoveEdge(G,x,y)：若(x,y)或<x,y>存在，则删除该边

FirstNeighbor(G,x)：求图G顶点x的第一个邻接点，若不存在返回-1

NextNeighbor(G,x,y)：y是x一个邻接点，返回除y之外顶点x下一个邻接点的顶点号

Get_Edge_value(G,x,y)：获取边(x,y)或<x,y>对应的权值

Set_Edge_value(G,x,y,v)：给(x,y)或<x,y>赋权值

6.3 图的遍历

6.3.1 广度优先搜索

广度优先搜索类似于树的层序遍历

找到与一个顶点相邻的所有顶点
标记哪些顶点被访问过
需要一个辅助队列

bool visit[MAX_VERTEX_NUM]; //访问标记数组
void BFS(Graph G, int v){// 广度优先遍历
    visit(v);
    visited[v]=true;
    Enqueue(Q,v);
    while(!isEmpty(Q)){
        Dequeue(Q,v);
        for (w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
            if (!visited[w]){
                visit(w);
                visited[w]=true;
                Enqueue(Q,w);
            }
    } 
}

void BFSTraverse(Graph G){
    for (i=0; i<G.vexnum; i++)
        visited[i]=false;
    InitQueue(Q);
    for(i=0;i<G.vexnum;i++)
        if(!visit[i])
            BFS(G,i)
}

算法空间复杂度： $O(|V|)$

算法时间复杂度：

若用邻接矩阵存储 $O(|V^2|)$
若用邻接表存储 $O(|V+E|)$

6.3.2 深度优先遍历

深度优先遍历类似于树的先根遍历

bool visited[MAX_VERTEX_NUM];
void DFS(Graph G, int v){
    visit(v);
    visited[v]=true;
    for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
        if(!visited[w]) DFS(G,w)
}

void DFSTraverse(Graph){
    for(v=0;v<G.vexnum;++v) visited[v]=false;
    for(v=0;v<G.vexnum;++v) 
        if(!visited[v]) DFS(G,v);
}

6.4 图的应用

6.4.1 最小生成树(MST)

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

获取最小生成树有两种算法：

①Prim算法

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

时间复杂度为 $O(|V^2|)$ 适用于边稠密图

②Kruskal算法

每次选择一条权值最小的边，使这两条边两头连通，直到所有的结点都连通

时间复杂度为 $O(|Elog_2|E||)$ 适用于边稀疏图

6.4.2 最短路径

6.4.2.1 Dijkstra算法

Dijkstra算法适用于单源最短路径，需要数组dist[]最小路径长度和path[]路径前驱

思想：循环遍历所有结点，找到还没确定的最短路径

时间复杂度为 $O(|V^2|)$ 不适合带有负权值的带权图

6.4.2.2 Floyd算法

Floyd算法适用于各顶点之间的最短路径

伪代码如下：

若 $A^{k-1}[i][j]>A^{k-1}[i][k]+A^{k-1}[k][j]$

则 $A^{k}[i][j]=A^{k-1}[j][k]+A^{k-1}[k][j]$

$path^k[i][j]=k$

其中A为邻接矩阵，path的初始值设为-1

时间复杂度为 $O(|V^3|)$ ，空间复杂度为 $O(|V|^2)$

Floyd可以解决带有负权值的带权图，但不能解决带有负权回路的图

6.4.3 有向无环图(DAG)

有向无环图：若一个图中不存在环，则称为有向无环图

应用：二叉树中，相同部分可以合并

6.4.4 拓补排序(AOV网)

若有向图的顶点不能构成一个拓补序列，则判定是一个强连通图

从AOV网中选择一个入度为0的顶点并输出
从网中删除该顶点和所有以它为终点的边
重复1和2直到当前的AOV网为空

bool TopologicalSort(Graph G){
    InitStack(S);
    for(int i=0; i<G.vexnum; i++)
        if(indegree[i]==0) Push(S,i); //将入度为0的顶点入栈
    int count = 0;
    while(!isEmpty(S)){
        Pop(S,i);
        print[count++]=i;
        for(p=G.vertices[i].firstarc;p;p->nextarc){
            // 将所有指向顶点入度减一，并将入度为0的顶点压入栈s
            v=p->adjvex;
            if(!(--indegree[v])) Push(S,v)
        }
    }
    if (count<G.vexnum) return false;
    else return true;
}

若一个顶点已经排在一个线性有序的序列，每个顶点有唯一的后继关系，只有在这种情况下，拓补排序是唯一的，并且对于一般的图，如果其邻接矩阵是三角矩阵，则一定存在拓补序列，反之不成立

6.4.4 关键路径(AOE网)

以顶点表示事件，以有向边表示活动，以边上的权值表示活动的开销

只有在某顶点的所代表事件发生后，从该顶点出发的各有向边所代表活动才能开始
只有在进入某顶点的各有向边所代表的活动都已经结束后，该顶点代表的事件才能开始

在AOE网中仅有一个入度为0的顶点，也只有一个出度为0的顶点

从源点到汇点的所有路径中，具有最大路径称为关键路径

求关键路径的步骤：

求所有事件发生的最早发生时间：按拓补排序序列求时间v_k的最早发生时间ve(k)
求所有时间的最迟发生时间：按逆拓补序列，求时间v_k的最迟发生时间vl(k)
求所有活动最早发生时间：活动a_i最早开始时间e(i)=ve(k)
求所有活动最迟发生时间：活动a_i最迟开始时间l(i)=vl(i)-weight(v_k-v_i)
求时间余量d()，d(i)=0的活动称为关键活动，由关键活动组成的路径即为关键路径