数据结构之图的基本概念

数据结构之图的基本概念"/>

数据结构之图的基本概念

图的基本概念

1、图的定义

图 G G G由顶点集 V V V和边集 E E E组成，记为 G = ( V , E ) G=(V,E) G=(V,E)，其中 V ( G ) V(G) V(G)表示图 G G G中顶点的有限非空集； E ( G ) E(G) E(G)表示图 G G G中顶点之间的关系（边）集合。若 V = { v 1 , v 2 , . . . , v n } V=\{v_1,v_2,...,v_n\} V={v1​,v2​,...,vn​}，则用 ∣ V ∣ |V| ∣V∣表示图 G G G中顶点的个数，也称图 G G G的阶， E = { ( u , v ) ∣ u ∣ ∈ V , v ∈ V } E=\{(u,v)|u|\in V,v \in V\} E={(u,v)∣u∣∈V,v∈V}，用 ∣ E ∣ |E| ∣E∣表示图 G G G中边的条数。

注：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集。

2、无向图、有向图

3、简单图、多重图

4、顶点的度、入度、出度

• 无向图：顶点 v v v的度是指依附于该顶点的边的条数，记为 T D ( v ) TD(v) TD(v)。
• 有向图：入度是以顶点 v v v为终点的有向边的数目，记为 I D ( v ) ID(v) ID(v)；出度是以顶点 v v v为起点的有向边的数目，记为 O D ( v ) OD(v) OD(v)。

5、顶点—顶点的关系描述

• 路径：顶点 v p v_p vp​到顶点 v q v_q vq​之间的一条路径是指顶点序列。
• 回路：第一个顶点和最后一个顶点相同的路径。
• 简单路径：顶点不重复出现的路径。
• 简单回路：除第一个顶点和最后一个顶点外，顶点不重复出现的路径。
• 路径长度：路径上边的数目。
• 点到点距离：最短路径的长度；若不存在，记为无穷。
• 无向图的连通，有向图的强连通。

6、连通图、强连通图

• 对于n个顶点的无向图G，若G是连通图，则最少有n-1条边；若G是非连通图，则最多可能有
• 对于n个顶点的有向图G，若G是强连通图，则最少有n-1条边

7、子图

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

9、强连通分量：有向图的极大强连通子图。

10、边的权、带权图

• 边的权：在一个图中，每条边都可以标上具有某种含义的数值。
• 带权图：边上带有权值的图。
• 带权路径长度：带权图上的一条路径上所有边的权值之和。

图的存储

邻接矩阵法

• 不带权的图

#define MaxVertexNum 100                  //顶点数目的最大值
typedef struct {                          char vex[MaxVertexNum];               //顶点表int edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表int vexNum, arcNum;                   //图的当前顶点数和边数
}MGraph;

• 带权图

#define MaxVertexNum 100                          //顶点数目的最大值
#define INFINITY INT_MAX                          //宏定义常量“无穷”
typedef char VertexType;                          //顶点的数据类型
typedef int EdgeType;                             //带权图中边上权值的数据类型
typedef struct {VertexType vex[MaxVertexNum];                 //顶点表EdgeType edge[MaxVertexNum][MaxVertexNum];    //边表int vexNum, arcNum;                           //图的当前顶点数和边数
}Mgraph;

缺点：数组实现的顺序存储，空间复杂度高，不适合存储稀疏图。

邻接表法（顺序+链式存储）

#define MaxVertexNum 100                          //顶点数目的最大值
typedef char VertexType;                          //顶点的数据类型
typedef int InfoType;                             //带权图中边上权值的数据类型
//"边"
typedef struct ArcNode {int adjVex;                                   //边指向哪个顶点struct ArcNode* next;                         //指向下一条边的指针//InfoType info;                              //边权值
}ArcNode;//"顶点"
typedef struct VNode {VertexType data;           //顶点信息ArcNode* first;            //第一条边
}VNode, AdjList[MaxVertexNum];//用邻接表存储的图
typedef struct {AdjList vertices;int vexNum, arcNum;
}ALGraph;

图的广度优先遍历

BFS要点：

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

伪代码

bool visited[MAX_VERTEX_NUM];      //访问标记数组
void BFSTraverse(Graph G) {        //对图G进行广度优先遍历for(int i = 0; i < G.vexNum; i++) {visited[i] = FALSE;        //访问标记数组初始化}InitQueue(Q);        //初始化辅助队列Q                  for(int i = 0; i < G.vexNum; i++) { if (!visited[i]) {BFS(G, i);}}
}void BFS(Graph G, int v) { //从顶点v出发，广度优先遍历图Gvisit(v);              //访问初始顶点vvisited[v] = TRUE;     //对v做已访问标记Enqueque(Q,v);         //顶点v入队列Qwhile(!isEmpty(Q)) {DeQueue(Q,v);                 //顶点v出队列for (w=FirstNeighbor(G,v); w >= 0; w=NextNeighbor(G,v,w)) {//检测v所有邻接点if(!visited[w]) {         //w为v的尚未访问的邻接顶点visit(w);             //访问顶点wvisited[w] = TRUE;    //对w做已访问标记EnQueue(Q,w);         //顶点w入队列}}}
}

图的深度优先遍历

伪代码

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