【数据结构】课堂复习笔记5——图

Kendal2024-12-042024-12-05

学习的网课是青岛大学-王卓的数据结构与算法基础系列课程，可在bilibili上观看。并配合zjut课堂笔记整理，仅用于学习和复习

五、图

5.1 图的基本概念和术语

图：Graph=(V,E)
- V：顶点(数据元素)的有穷非空集合
- E：边的有穷集合。
无向图：每条边都是无方向的
有向图：每条边都是有方向的
完全图：任意两个点都有一条边相连
- 无向完全图：n(n-1)/2 条边
- 有向完全图：n(n-1) 条边
稀疏图：有很少边或弧的图
稠密图：有较多边或弧的图。
网：边/弧带权的图。
邻接：有边/弧相连的两个顶点之间的关系。
- 存在(vi, vj)，则称vi和vj互为邻接点；
- 存在<vi, vj>，则称vi邻接到vj， vj邻接于vi
关联（依附）：边/弧与顶点之间的关系。
- 存在(vi, vj)/ <vi, vj>，则称该边/弧关联于vi和vj
顶点的度：与该顶点相关联的边的数目，记为TD(v)
- 在有向图中, 顶点的度等于该顶点的入度与出度之和。
  - 顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v)
  - 顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)

当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状？

是树！而且是一棵有向树！

路径：接续的边构成的顶点序列。
路径长度：路径上边或弧的数目/权值之和。
回路(环)：第一个顶点和最后一个顶点相同的路径。
简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径。
简单回路(简单环)：除路径起点和终点相同外，其余顶点均不相同的路径。
连通图（强连通图）：在无向图G=( V, {E} )中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图；在有向图中，则称为强连通图。
权与网：图中边或弧所具有的相关数称为权（权值），表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。
子图：设有两个图G=（V，{E}）、G1=（V1，{E1}），若V包含 V1，E包含E1，则称 G1是G的子图。
连通分量（强连通分量）：
- 无向图G 的极大连通子图称为G的连通分量。
  - 极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。
- 有向图G 的极大强连通子图称为G的强连通分量。
极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。（边最少）
生成树：对于无向连通图，包含其所有顶点的极小连通子图。
生成森林：对非连通图，由各个连通分量的生成树的集合

5.2 图的存储结构

5.2.1 数组表示法（邻接矩阵）

建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组

无向图：

分析1：无向图的邻接矩阵是对称的；
分析2：顶点i 的度＝第 i 行 (列) 中1 的个数；
特别：完全图的邻接矩阵中，对角元素为0，其余1。

有向图： 在有向图的邻接矩阵中，第i行含义：以结点vi为尾的弧（即出度边）；第i列含义：以结点vi为头的弧（即入度边）。

分析1：有向图的邻接矩阵可能是不对称的。
分析2：
- 顶点的出度=第i行元素之和
- 顶点的入度=第i列元素之和
- 顶点的度=第i行元素之和+第i列元素之和

网：邻接矩阵定义为：

优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边、找顶点的邻接点等等。
缺点：n个顶点需要n*n个单元存储边;空间效率为O(n2)。对稀疏图而言尤其浪费空间。

邻接矩阵的存储表示：

#define MaxInt 32767                    	//表示极大值，即∞
#define MVNum 100                       	//最大顶点数 
typedef char VerTexType;              	//假设顶点的数据类型为字符型 
typedef int ArcType;                  	//假设边的权值类型为整型 
typedef struct{ 
  VerTexType vexs[MVNum];            		//顶点表 
  ArcType arcs[MVNum][MVNum];      	//邻接矩阵 
  int vexnum,arcnum;                		//图的当前点数和边数 
}AMGraph;

例：采用邻接矩阵表示法创建无向网

Status CreateUDN(AMGraph &G){ 
    //采用邻接矩阵表示法，创建无向网G 
    cin>>G.vexnum>>G.arcnum; 	//输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i)    
      cin>>G.vexs[i];                        	//依次输入点的信息 
    for(i = 0; i<G.vexnum;++i) 	//初始化邻接矩阵，边的权值均置为极大值
       for(j = 0; j<G.vexnum;++j)   
         G.arcs[i][j] = MaxInt;   
    for(k = 0; k<G.arcnum;++k){                     //构造邻接矩阵 
      cin>>v1>>v2>>w;         //输入一条边依附的顶点及权值 
      i = LocateVex(G, v1); 
      j = LocateVex(G, v2);          //确定v1和v2在G中的位置
      G.arcs[i][j] = w;                   //边<v1, v2>的权值置为w 
      G.arcs[j][i] = G.arcs[i][j];    //置<v1, v2>的对称边<v2, v1>的权值为w 
   }//for 
   return OK; 
}//CreateUDN 

int LocateVex(MGraph G,VertexType u)
 {//存在则返回u在顶点表中的下标;否则返回-1
   int i;
   for(i=0;i<G.vexnum;++i)
     if(u==G.vexs[i])
       return i;
   return -1;
 }

5.2.2 邻接表（链式）表示法

无向图：

对每个顶点vi 建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域；
每个单链表有一个头结点（设为2个域），存vi信息；
每个单链表的头结点另外用顺序存储结构存储。注：
邻接表不唯一，因各个边结点的链入顺序是任意的
空间效率为。
- 若是稀疏图(e<<)，比邻接矩阵表示法省空间。
=单链表中链接的结点个数

有向图： 出边

空间效率为
出度：＝单链出边表中链接的结点数
入度：＝邻接点域为Vi的弧个数
度：

邻接表的存储表示：

#define MVNum 100                        	//最大顶点数 
typedef struct ArcNode{                		//边结点  或 弧结点
    int adjvex;                          		//该边所指向的顶点的位置 
    struct ArcNode * nextarc;          		//指向下一条边的指针 
    OtherInfo info;                      	              //和边相关的信息 
}ArcNode; 
typedef struct VNode{ 
    VerTexType data;                    		//顶点信息 
    ArcNode * firstarc;                		//指向第一条依附该顶点的边的指针 
}VNode, AdjList[MVNum];               	//AdjList表示邻接表类型 
typedef struct{ 
    AdjList vertices;                 		//邻接表 
    int vexnum, arcnum;              		//图的当前顶点数和边数 
}ALGraph;

例：采用邻接表表示法创建无向网

Status CreateUDG(ALGraph &G){ 
　//采用邻接表表示法，创建无向图G 
　cin>>G.vexnum>>G.arcnum;       //输入总顶点数，总边数 
    for(i = 0; i<G.vexnum; ++i){        //输入各点，构造表头结点表 
       cin>> G.vertices[i].data;            //输入顶点值 
       G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL 
    }//for 

    for(k = 0; k<G.arcnum;++k){        	//输入各边，构造邻接表 
       cin>>v1>>v2;                 		//输入一条边依附的两个顶点 
       i = LocateVex(G, v1);  
       j = LocateVex(G, v2);    
        p1=new ArcNode;               			//生成一个新的边结点*p1 
　      p1->adjvex=j;                   			//邻接点序号为j 
　      p1->nextarc= G.vertices[i].firstarc;  
        G.vertices[i].firstarc=p1;  
       //将新结点*p1插入顶点vi的边表头部 

        p2=new ArcNode; //生成另一个对称的新的边结点*p2 
　      p2->adjvex=i;                   			//邻接点序号为i 
　      p2->nextarc= G.vertices[j].firstarc;  
        G.vertices[j].firstarc=p2;  
       //将新结点*p2插入顶点vj的边表头部 
    }//for 
    return OK; 
}//CreateUDG

与邻接矩阵的关系：
- 联系：邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。
- 区别：
  - 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
  - 邻接矩阵的空间复杂度为，而邻接表的空间复杂度为。
- 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图

5.2.3 十字链表

用于有向图：

结点表中的结点的表示：
- data：结点的数据域，保存结点的数据值。
- firstin: 指向以该结点为弧头的第一个边结点。
- firstout：指向以该结点为弧尾的第一个边结点
边结点表中的结点的表示：
- info:边结点的数据域，保存边的权值等。
- tailvex: 本条边的出发结点的地址。
- headvex:本条边的终止结点的地址。
- hlink:终止结点相同的边中的下一条边的地址。
- tlink:出发结点相同的边中的下一条边的地址。

用于无向图：

结点表中的结点的表示：
- data:结点的数据域，保存结点的数据值。
- firstedge: 结点的指针域，给出自该结点出发的的第一条边的边结点的地址。
边结点表中的结点的表示：
- ivex: 本条边依附的一个结点的地址。
- ilink: 依附于该结点（地址由ivex给出）的边中的下一条边的的地址。
- jvex: 本条边依附的另一个结点的地址。
- jlink: 依附于该结点（地址由jvex给出）的边中的下一条边的的地址。
- info: 边结点的数据域，保存边的权值等。
- mark:边结点的标志域，用于标识该条边是否被访问过。

5.3 图的遍历

5.3.1 深度优先搜索

邻接矩阵：

void DFS(AMGraph G, int v){        	//图G为邻接矩阵类型 
  cout<<v;  visited[v] = true;  		//访问第v个顶点
  for(w = 0; w< G.vexnum; w++)  	//依次检查邻接矩阵v所在的行  
        if((G.arcs[v][w]!=0)&& (!visited[w]))  
            DFS(G, w); 
      //w是v的邻接点，如果w未访问，则递归调用DFS 
}

邻接表：

    void DFS(ALGraph G, int v){       // 图G为邻接表类型 
    cout<<v;  visited[v] = true;          // 访问第v个顶点
    p= G.vertices[v].firstarc;             // p指向v的边链表的第一个边结点 
    while(p!=NULL){              	      // 边结点非空 
    w=p->adjvex;               	      // 表示w是v的邻接点 
    if(!visited[w])  DFS(G, w); 	      // 如果w未访问，则递归调用DFS 
    p=p->nextarc;                	      // p指向下一个边结点 
    } 
}

算法效率分析：

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为。
用邻接表来表示图，虽然有 2e 个边结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为。

5.3.2 广度优先搜索

void BFS (Graph G, int v){ 
    //按广度优先非递归遍历连通图G 
    cout<<v; visited[v] = true;     		//访问第v个顶点
    InitQueue(Q);              			//辅助队列Q初始化，置空         
    EnQueue(Q, v);            			//v进队 
    while(!QueueEmpty(Q)){   		//队列非空 
       DeQueue(Q, u);        			//队头元素出队并置为u 
       for(w = FirstAdjVex(G, u); w>=0; w = NextAdjVex(G, u, w)) 
       if(!visited[w]){               	//w为u的尚未访问的邻接顶点 
             cout<<w; visited[w] = true;	EnQueue(Q, w); //w进队 
          }//if 
    }//while 
}//BFS

算法效率分析：

如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。
用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。

5.4 图的应用

5.4.1 最小生成树

极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。
生成树：包含图G所有顶点的极小连通子图（n-1条边）。
最小生成树：权值和最小的生成树。
MST性质：必有一棵最小生成树包含最小权值的边

求最小生成树：

使用不同的遍历图的方法，可以得到不同的生成树
从不同的顶点出发，也可能得到不同的生成树。
按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。

目标： 在网的多个生成树中，寻找一个各边权值之和最小的生成树。

构造最小生成树的准则： 不一定唯一

必须只使用该网中的边来构造最小生成树；
必须使用且仅使用n-1条边来联结网络中的n个顶点
不能使用产生回路的边

Prim（普里姆）算法： 归并顶点，从局部角度，与边数无关，适于稠密网。

设连通网络 N = { V, E }

从某顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其邻接顶点v加入到生成树的顶点集合U中
每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到U中
直到所有顶点都加入到生成树顶点集合U中为止

克鲁斯卡尔算法： 归并边（全局优先思维），

设连通网络 N = { V, E }

构造一个只有 n个顶点，没有边的非连通图 T = { V,  },每个顶点自成一个连通分量
在 E 中选最小权值的边,若该边的两个顶点落在不同的连通分量上，则该边加入 T 中；否则舍去，重新选择
重复下去，直到所有顶点在同一连通分量上为止。

5.4.2 最短路径

问题抽象：在带权有向图中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径。

单源最短路径—用Dijkstra（迪杰斯特拉）算法
所有顶点间的最短路径—用Floyd（弗洛伊德）算法
Dijkstra算法的思想：
- 初始化：先找出从源点v0到各终点vk的直达路径（v0,vk），即通过一条弧到达的路径。
- 选择：从这些直达路径中找出一条长度最短的路径（v0,u）。
- 更新：然后对其余各条路径进行适当调整：
有向无环图：
- AOV网(Activity On Vertices)—用顶点表示活动的网络:拓扑排序算法的思想－重复选择没有直接前驱的顶点
  - 输入AOV网络。令 n 为顶点个数。
  - 在AOV网络中选一个没有直接前驱的顶点, 并输出之;
  - 从图中删去该顶点, 同时删去所有它发出的有向边;
  - 重复以上 2、3 步, 直到：
    - 全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或：
    - 图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。
- AOE网(Activity On Edges)—用边表示活动的网络:关键路径
  - 关键路径：全部由关键活动构成的路径，或者从源点到收点的最长的一条路径。