【数据结构】图

博主：本当迷
发布时间：2021 年 10 月 04 日
1351 次浏览
1 条评论
5410字数
分类：数据结构

# 图：

## 介绍：

### 概念：

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为：G（V,E）,其中，G表示一个图，V表示图G中顶点的集合，E表示图G中边的集合。

### 无向边：

若顶点vi到vj之间的边没有方向，则称这条边为无向边，用无序偶对（vi,vj）来表示。

### 无向图：

如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。

### 有向边：

若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧。

#### 注意：

例如：< A, D>，连接A到D的有向边就是弧，A是弧尾，D是弧头，< A, D>表示弧，但是不能写成：

< D, A>。

### 有向图：

如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。

### 注意：

无向边用小括号"（）"表示，而有向边则是用尖括号" <> "表示

### 无向与有向完全图：

#### 无向完全图：

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图

#### 有向完全图：

在有向图中，如果任意两个顶点之间都存在边，则称该图为有向完全图

### 权与网：

#### 权：

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫权

#### 网：

带权的图通常称为网

### 图的顶点与边间的关系：

* 边数等于各顶点度数和的一半
* 在有向图中，各顶点的入度和等于各顶点的出度和

### 回路与路径：

#### 回路（环）：

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

#### 简单路径：

序列中顶点不重复出现的路径称为简单路径

#### 简单回路（简单环）：

除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

## 图的抽象数据类型：

```cpp
ADT 图（Graph）
Data
	顶点的有穷非空集合和边集合。
Operation
	CreateGraph（*G, V, VR）;//按照顶点集V和边弧集VR的定义构造图G
	DestroyGraph（*G）;//图G存在则销毁
	LocateVex（G, u）;//若图G存在顶点u，则返回图中位置
	GetVex（G, V）;//返回G中顶点v的值
	PutVex（G, v, value）;//将G中顶点v赋值value
	FirstAdjVex（G, *v）;//返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空
	NextAdjVex（G, v, *w）;//返回顶点v相对于顶点w的下一个邻接顶点，若w是v的最后一个邻接点则返回空
	InsertVex（*G, v）;//在图G中增添新顶点v
	DeleteVex（*G, v）;//删除图G中顶点v及其相关的弧
	InsertArc（*G, v, *w）;//在图中增添弧<v, w>,若G是无向图，还需添加对称弧<w, v>
	DeleteArc（*G, v, w）;//在图G中删除弧<v,vw>, 若G是无向图，还需删除对称弧<w, v>
	DFSTraverse（G）;//对图G中进行深度优先遍历，在遍历过程中对每个顶点调用
	HFSTraverse（G）;//对图G中进行广度优先遍历，在遍历过程中对每个顶点调用
endADT
```

## 图的存储结构：

### 邻接矩阵：

#### 概念：

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

#### 存储的结构代码：

```cpp
typedef char VertexType;//顶点类型
typedef int EdegType;//边上的权值类型
#define MAXVEX 100//最大顶点数
#define INFINITY 65535//用65535代替不存在该权值
typedef struct
{
	VertexType vexs[MAXVEX];//顶点表
	EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵，可看做边表
	int numNodes, numEdges; //图中当前的顶点数和边数
}MGragh;
```

#### 创建的无向网图代码：

```cpp
void CreateMGraph(MGraph *G)
{
	int i, j, k, w;
	printf("输入顶点数和边数：\n");
	scanf("%d %d", &G->numNodes, &G->numEdges);//输入顶点数和边数
	for(i = 0; i < G->numNodes; i++)//输入顶点信息，建立顶点表
	{
		scanf("%c", &G->vexs[i]);
	}
	for(i = 0; i < G->numNodes; i++)
	{
		for(j = 0; j < G->numNodes; j++)
		{
			G->arc[i][j] = INFINITY;//邻接矩阵初始化
		}
	}
	for(k = 0; k < G->numEdges; k++)//输入numEdges条边，建立邻接矩阵
	{
		printf("输入边(vi, vj)上的下标i, 下标j和权w\n");
		scanf("%d %d %d", &i, &j, &w);
		G->arc[i][j] = w;
		G->arc[j][i] = G->arc[i][j];//因为是无向图，矩阵对称
	}
}
```

### 邻接表：

#### 概念：

数组与链表相结合的存储方法称为邻接表

#### 邻接表处理办法：

* 图中顶点用一个以为数组存储，当然，顶点也可以用单链表来储存，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要储存指向第一个邻接点的指针，以便于查找该顶点的边信息。
* 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表储存，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

#### 存储的结构代码：

```cpp
typedef char VertexType;//顶点类型
typedefint EdgeType;//边上的权值类型

typedef struct EdgeNode//边表结点
{
	int adjvex;//邻接点域，存储该顶点对应的下标
	EdgeType info;//用于存储权值，对于非网图可以不需要
	struct EdgeNode *next;//链域，指向下一个邻接点
}EdgeNode;

typedef struct VertexNode//顶点表结点
{
	VertexType data;//顶点域，存储顶点信息
	EdgeNode *firstedge;//边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numNodes, numEdges;//图中当前顶点数和边数
}GraphAdjList;

```

#### 创建的无向网图代码:

```cpp
void CreateALGraph(GraphAdjList *G)
{
	int i, j, k;
	EdgeNode *e;
	printf("输入顶点数和边数：\n");
	scanf("%d %d", &G->numNodes, &G->numEdges);
	for(i = 0; i < G->numNodes; i++)
	{
		scanf("%c", &G->adjList[i].data);
		G->adjList[i].firstedeg = NULL;
	}

for(k = 0; k< G->numEdges; k++)
	{
		printf("输入边（vi, vj）上的顶点序号：\n");
		scanf("%d %d", &i, &j);
		e = (EdgeNode *)malloc(sizeof(EdgeNode));//向内存申请空间，生成边表结点
		e->adjvex = j;//邻接序号为j
		e->next = G->adjList[i].firstedge;//将e的指针指向当前顶点指向的结点
		G->adjList[i].firstedge = e;//将当前顶点的指针指向e
		e = (EdgeNode *)malloc(sizeof(EdgeNode));//向内存申请空间，生成边表结点
		e->adjvex = i;//邻接序号为i
		e->next = G->adjList[j].firstedge;//将e的指针指向当前顶点指向的结点
		G->adjList[j].firstedge = e;//将当前顶点的指针指向e
	}

}
```

## 深度优先遍历：

#### 介绍：

深度优先遍历，也称深度优先搜索，简称DFS。

它从图中某个顶点V出发，访问此顶点，然后从V的未访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到。

若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述操作，直至图中所有顶点都被访问到为止。

### 邻接矩阵的深度优先递归算法：

```cpp
#define MAXVEX 9
Boolean visited[MAXVEX];//访问标记的数组

void DFS(MGraph G, int i)
{
	int j;
	visited[i] = TRUE;
	printf("%c", G.vexs[i]);//打印顶点，也可以做其他操作
	for(j = 0; j < G->numVertexes; j++)
	{
		if(G.arc[i][j] == 1 && !visited[j])
		{
			DEF(G, j);//对未访问的邻接顶点递归调用
		}
	}
}
```

### 邻接矩阵的深度遍历操作：

```cpp
void DFSTraverse(MGraph G)
{
	int i;
	for(i = 0; i < G.numVertextes; i++)
	{
		visited[i] = FALSE;//初始所有顶点都是未访问过的状态
	}
	for(i = 0; i < G.numVertestes; i++)
	{
		if(!visited[i])//对未访问过的顶点调用DFS，若为连通图仅执行一次
		{
			DFS(G, i);
		}
	}
}
```

### 邻接表的深度优先递归算法：

```cpp
void DFS(GraphAdjList GL, int i)
{
	EdgeNode *p;
	visited[i] = TRUE;
	printf("%c", GL->adjList.data);//打印顶点，也可以做其他操作
	p = GL->adjList[i].firstedge;
	while(p)
	{
		if(!visited[p->adjvex])
		{
			DEF(GL, p->adjvex);//对未访问的邻接顶点递归调用
		}
		P = P->next;
	}
}
```

### 邻接表的深度遍历操作：

```cpp
void DFSTraverse(GraphAdjList, GL)
{
	int i;
	for(i = 0; i < GL->numVertextes; i++)
	{
		visited[i] = FALSE;//初始所有顶点都是未访问过的状态
	}
	for(i = 0; i < GL->numVertestes; i++)
	{
		if(!visited[i])//对未访问过的顶点调用DFS，若为连通图仅执行一次
		{
			DFS(GL, i);
		}
	}
}
```

## 广度优先遍历：

#### 介绍：

广度优先遍历，又称广度优先搜索，简称BFS。

最后修改：2021 年 10 月 05 日

如果文章有用，请随意打赏。

1 条评论

梦一帆
October 7th, 2021 at 06:10 pm

滴！学生卡！打卡时间：下午6:10:11，请上车的乘客系好安全带~

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

【数据结构】图

本当迷 • 2021 年 10 月 04 日

# 图：

## 介绍：

### 概念：

### 无向边：

若顶点vi到vj之间的边没有方向，则称这条边为无向边，用无序偶对（vi,vj）来表示。

### 无向图：

如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。

### 有向边：

若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧。

#### 注意：

例如：< A, D>，连接A到D的有向边就是弧，A是弧尾，D是弧头，< A, D>表示弧，但是不能写成：

< D, A>。

### 有向图：

如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。

### 注意：

无向边用小括号"（）"表示，而有向边则是用尖括号" <> "表示

### 无向与有向完全图：

#### 无向完全图：

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图

#### 有向完全图：

在有向图中，如果任意两个顶点之间都存在边，则称该图为有向完全图

### 权与网：

#### 权：

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫权

#### 网：

带权的图通常称为网

### 图的顶点与边间的关系：

* 边数等于各顶点度数和的一半
* 在有向图中，各顶点的入度和等于各顶点的出度和

### 回路与路径：

#### 回路（环）：

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

#### 简单路径：

序列中顶点不重复出现的路径称为简单路径

#### 简单回路（简单环）：

除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

## 图的抽象数据类型：

## 图的存储结构：

### 邻接矩阵：

#### 概念：

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

#### 存储的结构代码：

#### 创建的无向网图代码：

### 邻接表：

#### 概念：

数组与链表相结合的存储方法称为邻接表

#### 邻接表处理办法：

#### 存储的结构代码：

```cpp
typedef char VertexType;//顶点类型
typedefint EdgeType;//边上的权值类型

typedef struct VertexNode//顶点表结点
{
	VertexType data;//顶点域，存储顶点信息
	EdgeNode *firstedge;//边表头指针
}VertexNode, AdjList[MAXVEX];

typedef struct
{
	AdjList adjList;
	int numNodes, numEdges;//图中当前顶点数和边数
}GraphAdjList;

```

#### 创建的无向网图代码:

}
```

## 深度优先遍历：

#### 介绍：

深度优先遍历，也称深度优先搜索，简称DFS。

它从图中某个顶点V出发，访问此顶点，然后从V的未访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到。

若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述操作，直至图中所有顶点都被访问到为止。

### 邻接矩阵的深度优先递归算法：

```cpp
#define MAXVEX 9
Boolean visited[MAXVEX];//访问标记的数组

### 邻接矩阵的深度遍历操作：

### 邻接表的深度优先递归算法：

### 邻接表的深度遍历操作：

## 广度优先遍历：

#### 介绍：

广度优先遍历，又称广度优先搜索，简称BFS。

【数据结构】图

1 条评论

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【修仙之路】JAVA学习路线

对于异或运算的初步认识与auto用法

【JAVA经典例题】生产者/消费者问题

最近某音挺火的代码实现爱心形状

再见Swagger！拥抱smart-doc无侵入生成接口文档

ps-仿制图章

【java】mybatis和mybatisplus常用注解

MapStruct属性拷贝工具

【英语学习】每日10词

restful风格易错以及一些奇葩请求

【数据结构】图

1 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【数据结构】图

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款