CSGNAK的博客

数据结构——图

数据结构
Word count: 1.9kReading time: 8 min
2021/11/17 Share

认识图

图的各种基本术语

  • 图(Graph)，又称为网络 (Network)，由一个节点集合和边集合构 成，记作 G = (V, E)，其中 V 是顶点集，E 是边集

  • 节点/结点(node)，又称顶点(vetex) 边(edge)，又称链接(link)，联系(tie)，弧(arc)

图的 ADT

  • 数据对象：具有相同特性的数据元素的集合，称为顶点集V。
  • 数据关系：R = {< v,w > |v,w ∈ V&&P(v,w)},< v,w >表示从v到w的一条弧,v为弧尾，w为弧头;
    P(v, w)定义了弧< v, w >的意义或信息 }

基本操作:

Create_Graph()： 图的创建操作，生成一个没有顶点的空图G

GetVex(G, v) ：求图中的顶点v的值

DFStraver(G,v)：从v出发对图G深度优先遍历, 每个顶点访问且只访问一次

BFStraver(G,v)：从v出发对图G广度优先遍历, 每个顶点访问且只访问一次

图的实现

图的存储结构

图存储时要考虑的问题

任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不 同的结构，又会影响操作。

常见的图存储结构

  • 邻接矩阵/数组表示法
  • 邻接链表
  • 十字链表
  • 邻接多重表
  • 边表

邻接矩阵/数组表示法

顶点表 + 邻接矩阵包括：一个记录各个顶点信息的顶点表 + 一个表示各个顶点之间关系的邻接矩阵。或者更准确地说是“数组表示法”，一个一维顶点数组 + 一个二维边数组。

有向图和无向图的不同 1：对称性

  • 无向图的邻接矩阵是对称的; 有向图的邻接矩阵可能是不对称的。

有向图和无向图的不同 2：求度的差异

  • 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 i 列 1的个数可得顶点 i 的入度。
  • 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点 i 的度。

邻接矩阵的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define INFINITY INT_MAX //最大值
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKind; //图的类型

typedef struct ArcCell{
	WType w; // WType为边权值类型 
  InfoType *info; //该弧相关信息指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
	VexType vexs[MAX_VERTEX_NUM]; //顶点向量 
  AdjMatrix adj; //邻接矩阵
	int vexnum,arcnum; //顶点数和弧数 
  GraphKind kind; //图的种类标志
} MGraph;

图的构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status CreateUDN(Mgraph &G){
	//无向网的构造 
	scanf(&G.vexnum,&G.arcnum,&IncInfo); 
	for(i=0;i<G.vexnum;++i) 
		scanf(&G.vexs[i]); 
	for (i=0 ;i<G.vexnum;++i) //初始化邻接矩阵
     for (j=0;j<G.vexnum;++j)
       G.adj[i][j]={INFINITY,NULL};
	for(k=0 ;k<G.arcnum;++k){ 
		scanf(&v1,&v2,&w); //读入边依附的顶点和权值 
		i=LocateVex(G,v1);
		j=LocateVex(G,v2); //顶点定位 
		G.adj[i][j].w=w; //弧<v1,v2>的权值
		if (IncInfo)
			Input(*G.adj[i][j].info); //输入弧的相关信息 
    G.adj[j][i]=G.adj[i][j]; //置对称弧<v2,v1>
  }
	return OK; 
}

图的顶点定位

  • 确定一个顶点在 vexs 数组中的位置 (下标) ，其过程完全等同于在顺序存储的线性表中查找一个数据元素
1
2
3
4
5
6
7
int LocateVex(MGraph *G , VexType *vp){ 
	intk;
	for (k=0;k< G->vexnum; k++)
  	if (G->vexs[k]==*vp)
			return(k);
	return(-1); //图中无此顶点
}

向图中增加一个顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int AddVertex(ALGraph *G ,VexType *vp){
	int k, j;
	if (G->vexnum>=MAX_VEX){
		printf(“Vertex Overflow !\n”); 
		return(-1);
	}
	if(LocateVex(G , vp)!=-1){
		printf(“Vertex has existed !\n”);
		return(-1);
  }
	G->vertices[G->vexnum].data=*vp;
	G->vertices[G->vexnum].degree=0;
	G->vertices[G->vexnum].firstarc=NULL;
	k=++G->vexnum;
	return(k);
}////在顶点数组vertices末尾增加一个数据元素

向图中增加一条弧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int AddArc(ALGraph *G , ArcType *arc){
  int k,j;
  ArcNode*p,*q;
  k=LocateVex(G , &arc->vex1) ;
  j=LocateVex(G , &arc->vex2) ;
	if (k==-1||j==-1) {
    printf(``弧依附的顶点不存在\n''); return(-1) ;
  }
	p=(ArcNode *)malloc(sizeof(ArcNode)) ; 
  p->adjvex=arc->vex1 ; 
  p->info=arc->info ; 
  p->nextarc=NULL ; //边的起始表结点赋值 
  q=(ArcNode *)malloc(sizeof(ArcNode)) ; 
  q->adjvex=arc->vex2 ; 
  q->info=arc->info ; 
  q->nextarc=NULL ; //边的末尾表结点赋值
	if (G->kind==UDG||G->kind==UDN) { 
    q->nextarc=G->vertices[k].firstarc ; 
    G->vertices[k].firstarc=q ; 
    //以上代码实现头插
    p->nextarc=G->vertices[j].firstarc ; 
    G->vertices[j].firstarc=p ;
	}//以上，是无向图, 用头插入法插入到两个单链表
  else{// 以下，建立有向图的邻接链表, 用头插入法
		q->nextarc=G->vertices[k].firstarc ; 
		G->vertices[k].firstarc=q ; //建立正邻接链表用
    //q->nextarc=G->vertices[j].firstarc ; 
    //G->vertices[j].firstarc=q ;}
    //建立逆邻接链表用
	return(1); 
}//根据给定的弧或边所依附的顶点，修改链表。

有向图的十字链表

有向图的链式存储结构：融合(拼接)邻接表和逆邻接表

  • data 域:存储和顶点相关的信息;
  • 指针域 firstin：指向以该顶点为弧头的第一条弧所对应的弧结点;

  • 指针域 firstout：指向以该顶点为弧尾的第一条弧所对应的弧结点;

  • 尾域 tailvex:指示弧尾顶点在图中的位置;

  • 头域 headvex:指示弧头顶点在图中的位置;

  • 指针域 hlink：指向弧头相同的下一条弧;

  • 指针域 tlink:指向弧尾相同的下一条弧;

  • Info 域:指向该弧的相关信息;

    截屏2021-11-17 下午2.32.23

有向图十字链表的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define INFINITY MAX_VAL /*最大值∞*/ 
#define MAX_VEX 30 //最大顶点数 
typedef struct ArcNode{
	int tailvex, headvex; //尾结点和头结点在图中的位置 
  InfoType *info; //与弧相关的信息, 如权值 
  struct ArcNode *hlink, *tlink;
}ArcNode; //弧结点类型定义

typedef struct VexNode{ VexType data; // 顶点信息
	ArcNode *firstin, *firstout;
}VexNode; //顶点结点类型定义

typedef struct{
  int vexnum;
  VexNode xlist[MAX_VEX];
}OLGraph; //图的类型定义

图解十字链表

截屏2021-11-17 下午2.27.55

图：十字链表

十字链表就是把邻接表和逆邻接表融合起来。（然而用的很少）

无向图的邻接多重表

仿造有向图的十字链表 (融合邻接表和逆邻接表);将无向图的邻接 表中的重复边节点去掉

节点结构如下图所示，说明如下：

  • Data 域:存储和顶点相关的信息;
  • 指针域 firstedge:指向依附于该顶点的第一条边所对应的表结点;
  • 标志域 mark:用以标识该条边是否被访问过;
  • ivex 和 jvex 域:分别保存该边所依附的两个顶点在图中的位置;
  • info 域:保存该边的相关信息;
  • 指针域 ilink:指向下一条依附于顶点 ivex 的边;
  • 指针域 jlink:指向下一条依附于顶点 jvex 的边;

截屏2021-11-17 下午2.36.20

无向图的邻接多重表的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define INFINITY MAX_VAL //最大值∞
#define MAX_VEX 30 //最大顶点数
typedef emnu {unvisited, visited} Visitting;
typedef struct EdgeNode{
	Visitting mark; //访问标记
	int ivex, jvex; //该边依附的两个结点在图中的位置
	InfoType *info; //与边相关的信息, 如权值
	struct EdgeNode *ilink, *jlink;
	// 分别指向依附于这两个顶点的下一条边
}EdgeNode; //弧边结点类型定义

typedef struct VexNode{
	VexType data; //顶点信息
	ArcNode *firstedge; //指向依附于该顶点的第一条边
}VexNode; //顶点结点类型定义

typedef struct{
	int vexnum;
	VexNode mullist[MAX_VEX];
}AMGraph;

图解邻接多重表

截屏2021-11-17 下午2.36.58

图：邻接多重表
CATALOG
  1. 1. 认识图
    1. 1.0.1. 图的各种基本术语
  2. 1.1. 图的 ADT
    1. 1.1.1. 基本操作:
  • 2. 图的实现
    1. 2.1. 图的存储结构
      1. 2.1.1. 图存储时要考虑的问题
      2. 2.1.2. 常见的图存储结构
    2. 2.2. 邻接矩阵/数组表示法
      1. 2.2.1. 有向图和无向图的不同 1：对称性
      2. 2.2.2. 有向图和无向图的不同 2：求度的差异
      3. 2.2.3. 邻接矩阵的实现
      4. 2.2.4. 图的构造
      5. 2.2.5. 图的顶点定位
      6. 2.2.6. 向图中增加一个顶点
      7. 2.2.7. 向图中增加一条弧
    3. 2.3. 有向图的十字链表
      1. 2.3.1. 图解十字链表
    4. 2.4. 无向图的邻接多重表
      1. 2.4.1. 图解邻接多重表
    • Total : 9
    2021
    数据结构 心得 计算系统概论 大二上
    数据结构