数据结构与算法~图

博主： Xherlock
发布时间：2021 年 11 月 14 日
548 次浏览
暂无评论
5098字数
分类：数据结构与算法

# 图

## 定义

G=(V, E)

V：顶点的有穷非空集合	V(G)为图G的顶点集合

E：V中顶点偶对（边）的有穷集合	E(G)为图G的边集合

E(G)为空时，图G只有顶点而没有边

### 无向图

顶点对(x,y)和(y,x)是同一条边，每条边都是无方向的

### 有向图

顶点对<x,y>是有序的，称为从顶点x到顶点y的一条有向边，每条边都是有方向的

## 基本术语

* 完全图：任意两个点都有一条边相连，分为无向n\*(n-1)/2条边，和有向n\*(n-1)条边
* 子图：G=(V, E)，G'=(V', E')，V'包含于V，E'包含于E'，则称G'为G的子图
* 稀疏图：有很少的边或弧的图
* 稠密图：和稀疏图相反
* 权：图上每条边可以带上数值，表示从一个顶点到另一个的距离或耗费等
* 网：边/弧带权的图
* 邻接点：对无向图，(v, v')属于E，则称顶点v和v'互为邻接点，即它俩相邻接，边(v, v')依附于俩顶点，或说边(v, v')与俩顶点相关联
* **顶点的度**：与该顶点相关联的边的数目，记为TD(v)

有向图中，顶点的度等于入度与出度的和

* 入度：以v为终点的有向边的条数，记为ID(v)
  * 出度：以v为始点的有向边的条数，记为OD(v)
* 路径：连续的边构成的顶点序列
* 路径长度：路径上边或弧的数目/权值之和
* 回路（环）：第一个顶点和最后一个顶点相同的路径
* 简单路径：序列中顶点均不相同的路径
* 简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径
* **连通图**：无向图中任意两个顶点连通（有路径），则称G为连通图，否则为非连通图
* 连通分量：无向图中的极大连通子图
* 强连通图：有向图（无向图）任意两个顶点间都存在路径
* 强连通分量：有向图中的极大连通子图
* 极小连通子图：G的连通子图，在该子图中删除任何一条边，子图不再连通
* **连通图的生成树**：包含无向图G的所有顶点的极小连通子图
* 有向树：有一个顶点的入度为0，其余顶点的入度均为1的有向图
* 生成森林：若干有向树组成，包含图中全部顶点

## 图的存储结构

### 顺序存储结构

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

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

A.Edge\[i]\[j]=1, 若\<i, j>属于E或(i, j)属于E

##### 无向图

* 无向图的邻接矩阵是对称的
* 顶点i的度=第i行（列）中1的个数
* 完全图中除主对角线为0，其余均为1

![image-20211111090453146.png](http://xherlock.top/usr/uploads/2021/11/1216260770.png)

##### 有向图

* 第i行：以结点v~i~为出度的有向边
* 第i列：以结点v~i~为入度的有向边
* 顶点的出度等于第i行元素之和
* 顶点的入度等于第i列元素之和

![image-20211111090701035.png](http://xherlock.top/usr/uploads/2021/11/4026459543.png)

##### 网（有权图）

![image-20211111091058079.png](http://xherlock.top/usr/uploads/2021/11/3813108751.png)

##### 算法描述

创建无向网

* 输入总顶点数和总边数
* 依次输入点的信息存入顶点表中
* 初始化邻接矩阵，是每个权值初始化为极大值
* 构造邻接矩阵

~~~C
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 
~~~

##### 优点

* 便于判断两个顶点间是否有边
* 便于计算各个顶点的度

##### 缺点

* 不便于增加和删除顶点
* 不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为O(n^2^)
* 空间复杂度高，对稀疏图来说浪费空间

### 链式存储结构

#### 邻接表（链式）表示法

对每个顶点v~i~都建立一个单链表，把所有与v~i~关联的边的信息链接起来，每个结点设置三个域

![image-20211111103212930.png](http://xherlock.top/usr/uploads/2021/11/1916127265.png)

设图为n个顶点，e条边结点

##### 无向图

![请输入图片描述](http://xherlock.top/usr/uploads/2021/11/2785462072.png)

**注意**：里面的数字表示的是数组下标

邻接表不唯一，各个边结点链入顺序不一样

**空间效率O(n+2e)**，比邻接矩阵节省空间

##### 有向图

![image-20211111103509516.png](http://xherlock.top/usr/uploads/2021/11/4215155412.png)

**空间效率O(n+e)**

##### 邻接表存储表示

~~~C
#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; 
~~~

创建无向网

* 输入总顶点数和总边数
* 依次输入点的信息存入顶点表中 ，是每个表头结点的指针域初始化为NULL
* 创建邻接表

~~~C
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(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的边表头部 
    } 
    return OK; 
}//CreateUDG 
~~~

##### 优点

* 便于增加和删除结点
* 便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目
* 空间效率高

##### 缺点

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

**邻接矩阵多用于稠密图，邻接表多用于稀疏图**

#### 十字链表

有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表

##### 有向图

![image-20211111105207444.png](http://xherlock.top/usr/uploads/2021/11/1735917995.png)

![image-20211111105319073.png](http://xherlock.top/usr/uploads/2021/11/1834675342.png)

##### 无向图

![image-20211111105804111.png](http://xherlock.top/usr/uploads/2021/11/2919354271.png)

![image-20211111105817813.png](http://xherlock.top/usr/uploads/2021/11/205545288.png)

## 图的遍历

### 深度优先（DFS）

步骤

* 访问起始点v
* 若v的第一个邻接点没访问过，深度遍历此邻接点w~1~
* 再重w~1~出发，访问与w~1~邻接但还未访问的顶点w~2~
* 再从w~2~出发，进行类似的访问……
* 直到所有邻接顶点都被访问过为止

中间如果没有其他没有被访问过的邻接顶点，就退回一步进行搜索，并重复

#### 邻接矩阵

递归

~~~C
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 
} 
~~~

#### 邻接表

递归

~~~C
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指向下一个边结点 
    } 
} 
~~~

### 广度优先

分层搜索，不是递归

步骤

* 访问起始点v后，依次访问v的邻接点，访问过的置visited[v]为true，并将v入队
* 然后依次访问这些顶点中未被访问过的邻接点
* 直到所有顶点都被访问过（即队空）为止

~~~C
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 
~~~

### DFS和BFS比较

* 空间复杂度相同，O(n)
* 时间复杂度于存储结构相关（是邻接矩阵还是邻接表）与搜索路径无关

## 图的应用

### 最小生成树

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

最小生成树目标：寻找各边权值之和最小的生成树

#### Prim算法

归并顶点，与边数无关，适于稠密网

* 从某顶点起，选择与它关联的最小权值的边，将其顶点加入到生成树的顶点集合
* 每一个顶点都如此，选择没有选过且具有最小权值的边
* 直到所有顶点都加入生成树的顶点集合

#### Kruskel算法

归并边，适于稀疏网

* 构造n个顶点的非连通图
* 选取其中权值最小边，两个顶点相连
* 重复直到所有顶点在同一连通分量上为止

### 最短路径

与最小生成树区别是不用包含全部n个顶点

#### 单源最短路径

一顶点到其他顶点最短距离

* 初始化：先找出从源点v~0~到各终点v~k~的直达路径(v~0~, v~k~)
* 选择：从这些路径中找出一条长度最短的路径(v~0~, u)

```
  if    (v
  ```

~0~, u) + (u, v~k~) < (v~0~, v~k~)

```
  (v
  ```

~0~, u, v~k~)代替(v~0~, v~k~)
* 更新：对其余各条路径进行调整

#### 所有顶点间最短路径

任意两顶点间

### 拓扑排序

### 关键路径

最后修改：2021 年 11 月 22 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

运输层（二）
浏览次数: 502
机器学习3
浏览次数: 381
CSS1
浏览次数: 530
pytorch数据处理
浏览次数: 360
Vue（一）
浏览次数: 485

数据结构与算法~图

Xherlock • 2021 年 11 月 14 日

# 图

## 定义

G=(V, E)

V：顶点的有穷非空集合	V(G)为图G的顶点集合

E：V中顶点偶对（边）的有穷集合	E(G)为图G的边集合

E(G)为空时，图G只有顶点而没有边

### 无向图

顶点对(x,y)和(y,x)是同一条边，每条边都是无方向的

### 有向图

顶点对<x,y>是有序的，称为从顶点x到顶点y的一条有向边，每条边都是有方向的

## 基本术语

有向图中，顶点的度等于入度与出度的和

## 图的存储结构

### 顺序存储结构

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

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

A.Edge\[i]\[j]=1, 若\<i, j>属于E或(i, j)属于E

##### 无向图

* 无向图的邻接矩阵是对称的
* 顶点i的度=第i行（列）中1的个数
* 完全图中除主对角线为0，其余均为1

![image-20211111090453146.png](http://xherlock.top/usr/uploads/2021/11/1216260770.png)

##### 有向图

* 第i行：以结点v~i~为出度的有向边
* 第i列：以结点v~i~为入度的有向边
* 顶点的出度等于第i行元素之和
* 顶点的入度等于第i列元素之和

![image-20211111090701035.png](http://xherlock.top/usr/uploads/2021/11/4026459543.png)

##### 网（有权图）

![image-20211111091058079.png](http://xherlock.top/usr/uploads/2021/11/3813108751.png)

##### 算法描述

创建无向网

* 输入总顶点数和总边数
* 依次输入点的信息存入顶点表中
* 初始化邻接矩阵，是每个权值初始化为极大值
* 构造邻接矩阵

##### 优点

* 便于判断两个顶点间是否有边
* 便于计算各个顶点的度

##### 缺点

### 链式存储结构

#### 邻接表（链式）表示法

对每个顶点v~i~都建立一个单链表，把所有与v~i~关联的边的信息链接起来，每个结点设置三个域

![image-20211111103212930.png](http://xherlock.top/usr/uploads/2021/11/1916127265.png)

设图为n个顶点，e条边结点

##### 无向图

![请输入图片描述](http://xherlock.top/usr/uploads/2021/11/2785462072.png)

**注意**：里面的数字表示的是数组下标

邻接表不唯一，各个边结点链入顺序不一样

**空间效率O(n+2e)**，比邻接矩阵节省空间

##### 有向图

![image-20211111103509516.png](http://xherlock.top/usr/uploads/2021/11/4215155412.png)

**空间效率O(n+e)**

##### 邻接表存储表示

创建无向网

* 输入总顶点数和总边数
* 依次输入点的信息存入顶点表中 ，是每个表头结点的指针域初始化为NULL
* 创建邻接表

##### 优点

* 便于增加和删除结点
* 便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目
* 空间效率高

##### 缺点

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

**邻接矩阵多用于稠密图，邻接表多用于稀疏图**

#### 十字链表

有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来的一种链表

##### 有向图

![image-20211111105207444.png](http://xherlock.top/usr/uploads/2021/11/1735917995.png)

![image-20211111105319073.png](http://xherlock.top/usr/uploads/2021/11/1834675342.png)

##### 无向图

![image-20211111105804111.png](http://xherlock.top/usr/uploads/2021/11/2919354271.png)

![image-20211111105817813.png](http://xherlock.top/usr/uploads/2021/11/205545288.png)

## 图的遍历

### 深度优先（DFS）

步骤

中间如果没有其他没有被访问过的邻接顶点，就退回一步进行搜索，并重复

#### 邻接矩阵

递归

#### 邻接表

递归

### 广度优先

分层搜索，不是递归

步骤

### DFS和BFS比较

* 空间复杂度相同，O(n)
* 时间复杂度于存储结构相关（是邻接矩阵还是邻接表）与搜索路径无关

## 图的应用

### 最小生成树

最小生成树目标：寻找各边权值之和最小的生成树

#### Prim算法

归并顶点，与边数无关，适于稠密网

#### Kruskel算法

归并边，适于稀疏网

* 构造n个顶点的非连通图
* 选取其中权值最小边，两个顶点相连
* 重复直到所有顶点在同一连通分量上为止

### 最短路径

与最小生成树区别是不用包含全部n个顶点

#### 单源最短路径

一顶点到其他顶点最短距离

* 初始化：先找出从源点v~0~到各终点v~k~的直达路径(v~0~, v~k~)
* 选择：从这些路径中找出一条长度最短的路径(v~0~, u)

```
  if    (v
  ```

~0~, u) + (u, v~k~) < (v~0~, v~k~)

```
  (v
  ```

~0~, u, v~k~)代替(v~0~, v~k~)
* 更新：对其余各条路径进行调整

#### 所有顶点间最短路径

任意两顶点间

### 拓扑排序

### 关键路径

发表评论 取消回复

数据结构与算法~图

发表评论取消回复