6.4 图的存储结构

6.4 图的存储结构

6.4.1邻接矩阵

1.邻接矩阵表示法

邻接矩阵:表示顶点之间相邻关系的矩阵。

邻接矩阵表示法:运用二维数组

用两个数组分别存储顶点信息和邻接矩阵

一维:存储顶点信息

二维:存储邻接矩阵

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

2.采用邻接矩阵表示法创建无向网

已知一个图的点和边, 使用邻接矩阵表示法来创建此图的方法比较简单, 下面以一个无向网为例来说明创建图的算法。

算法6.1 采用邻接矩阵表示法创建无向网

1.步骤

①输入总顶点数和总边数。

②依次输入点的信息存入顶点表中。

③初始化邻接矩阵, 使每个权值初始化为极大值。

④构造邻接矩阵。依次输入每条边依附的顶点和其权值,确定两个顶点在图中的位置之后,使相应边赋予相应的权值,同时使其对称边赋予相同的权值。

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

3.邻接矩阵的优缺点

(1)优点

①便于判断两个顶点之间是否有边, 即根据A[i] [j]= 0或1来判断。

②便于计算各个顶点的度。对于无向图,邻接矩阵第i行元素之和就是顶点i的度;对于有向图,第i行 元素之和就是顶点 i 的出度,第i 列元素之和就是顶点i的入度。

(2) 缺点

①不便于增加和删除顶点。

②不便于统计边的数目,需要扫描邻接矩阵所有元素才能统计完毕,时间复杂度O(n^2)

③空间复杂度高。如果是有向图,n个顶点需要n2个单元存储边。如果是无向图,因其邻接矩阵是对称的,所以对规模较大的邻接矩阵可以采用压缩存储的方法,仅存储下三角(或上三角)的元素,这样需要n(n-1)/2个单元即可。但无论以何种方式存储,邻接矩阵表示法的空间复杂度均为0(n^2),这对千稀疏图而言尤其浪费空间。

6.4.2邻接表

1.邻接表表示法

在邻接表中,对图中每个顶点V; 建立一个单链表,把与 V;相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息, 把这一结点看成链表的表头, 其余结点存放有关边的信息, 这样邻接表便由两部分组成:表头结点表和边表。

(1)表头结点表:由所有表头结点以顺序结构的形式存储, 以便可以随机访问任一顶点的边链表。表头结点包括数据域 (data)链域 (firstarc) 两部分。

(2)边表:由表示图中顶点间关系的 2n个边链表组成。 边链表中边结点包括邻接点域(adjvex)数据域 (info)链域 (nextarc)三部分。

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

 

2.采用邻接表表示法创建无向图

基于上述的邻接表表示法, 要创建一个图则需要创建其相应的顶点表和边表。下面以一个无向图为例来说明采用邻接表表示法创建无向图的算法。

算法6.2 采用邻接表表示法创建无向图

1.步骤

①入总顶点数和总边数。

②依次输入点的信息存入顶点表中,使每个表头结点的指针域初始化为NULL。

③创建邻接表。依次输入每条边依附的两个顶点, 确定这两个顶点的序号l和)之后, 将此边结点分别插入 Vi和vj对应的两个边链表的头部。

2.实现
Status CreateUDG(ALGraph &G) 
{//采用邻接表表示法, 创建无向图 G
cin>>G.vexnum>>G.arcnum; //输入总顶点数, 总边数
for(i=O;i<G.vexnum;++i) //输入各点,构造表头结点表
{
cin»G.vertices[i] .data; //输入顶点值
G.vertices[i] .firstarc=NULL;//初始化表头结点的指针域为NULL
}//for
for(k=O;k<G.arcnum;++k) //输入各边, 构造邻接表
{
cin>>vl>>v2; //输入一条边依附的两个顶点
i=LocateVex(G,vl); j =LocateVex(G,v2); //确定vl和 v2在G中位置, 即顶点在G.vertices中的序号
pl=new ArcNode;//生成一个新的边结点*pl
pl->adjvex=j; //邻接点序号为
pl->nextarc=G. vertices [i] . firstarc; G. vertices [i] . firstarc= pl; //将新结点*pl插入顶点Vi的边表头部
p2=new ArcNode; //生成另一个对称的新的边结点*p2
p2->adjvex=i; //邻接点序号为1
p2->nextarc=G.vertices[j] .firstarc; G.vertices[j] .firstarc=p2; //将新结点*p2插入顶点Vj的边表头部
}//for
return OK;
}

3.邻接表表示法的优缺点

(1) 优点

①便于增加和删除顶点。

②便于统计边的数目,按顶点表 顺 序扫描 所 有边表可得到边的数目,时间复杂度为O(n + e)。

③空间效率高。对于一个具有n个顶点e条边的图 G, 若 G 是无向图,则在其邻接表表示中有 n 个顶点表结点和 2e 个边表结点;若 G 是有向图,则在它的邻接表表示或逆邻接表表示中均有 n 个顶点表结点和e个边表结点。因此,邻接表或逆邻接表表示的空间复杂度为 O(n + e), 适合表示稀疏图。对于稠密图,考虑到邻接表中要附加链域,因此常采取邻接矩阵表示法。

(2)缺点

①不便于判断顶点之间是否有边,要判定 Vi和vj之间是否有边,就需扫描第i个边表,最坏情况下要耗费 O(n)时间。

②不便于计算有向图各个顶点的度。对千无向图,在邻接表表示中顶点V;的度是第i个边表 中的结点个数。 在有向图的邻接表中,第 i 个边表上的结点个数是顶点 V;的出度,但求 vi;的入度较困难,需遍历各顶点的边表。若有向图采用逆邻接表表示,则与邻接表表示相反,求顶点的入度容易,而求顶点的出度较难。

6.4.3十字链表

十字链表 (Orthogonal List)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。 在十字链表中,对应千有向图中每一条弧有一个结点,对应于每个顶点也有一个结点。

#define MAX_ VERTEX_NUM 20 
typedef strut ArcBox
{
int tailvext,headvex; //该弧的尾和头顶点的位置
struct ArcBox *hlink, *tlink; //分别为弧头相同和弧尾相同的弧的链域
InfoType *info; //该弧相关信息的指针
}ArcBox;
typedef struct VexNode
VertexType data;
ArcBox *firstin,*firstout; //分别指向该顶点第一条人弧和出弧
}VexNode;
typedef struct

VexNode xlist [MAX_VERTEX_NUM]; //表头向扯
int vexnnm, arcnum; //有向图的当前顶点数和弧数
}OLGraph;

6.4.4邻接多重表

邻接多重表 (Adjacency Multilist) 是无向图的另一种链式存储结构。

#define MAX_VERTEX_NUM 20
typedef enum{unvisited,visited} Visitlf;
typedef struct EBox
{
Visitlf mark; //访问标记
int ivex, jvex; //该边依附的两个顶点的位置
struct EBox *ilink, *jlink; //分别指向依附这两个顶点的下一条边
InfoType *info; //该边信息指针
} Ebox;
typedef struct VexBox

VertexType data;
EBox *firstedge; //指向第一条依附该顶点的边
}VexBox;
typedef struct{
VexBox adjmulist [MAX_VERTEX_NUM];
int vexnum, edgenum;//无向图的当前顶点数和边数
}AMLGraph;

 

推荐这些文章:

数据结构---图的定义和存储结构

目录图的定义和基本术语基本术语图的类型定义图的存储结构1.邻接矩阵表示法无向图的邻接矩阵有向图的邻接矩阵图的邻接矩阵存储表示创建无向网创建无向图创建有向网创建有向图邻接矩阵优缺点:优点缺点2.邻接表表头结点表:边表:图的邻接表的存储表示创建无向图创建有向图创建有向/无向网邻接表表示法的优缺点优点:缺点:邻接矩阵和邻接表表示法的关系区别:3.十字链表十字链表的存储表示4.邻接多重表邻接多重表存储表示
图的定义和基本术语
图(Graph) G由两个集合V和E组成,记为G=(V,E) , 其中V是顶点的有穷非空集合,E是V中顶点偶对的有穷集合,这些顶点偶对称为边。其中点不能为空,边可以为空。
无向...

数据机构之图

一、图的概念

通常图表示为偶对,是顶点和边的集合
G = (V,E)V:顶点(数据元素)的又穷非空集合G:边的又穷集合

1.图的分类
1.通常根据边有无方向分为:又向图和无向图。
2.根据任意两个顶点之间是否有边相连称为:完全图其中:无向完全图中  n个顶点有 n(n-1)/2 条边          有向完全图中  n个顶点有 n(n-1) 条边
3.稀疏图:有很少边或弧的图(e<n logn)   稠密图:有较多边或弧的图   网:边/弧带权的图   ...

10.伙伴系统(伙伴系统的结构)

struct zone {
...
  /*
  * 不同长度的空闲区域
  */
  struct free_area free_area[MAX_ORDER];
...
};

 

free_area是一个辅助数据结构,我们此前尚未遇见。其定义如下:

<mmzone.h>
  struct free_area {
  struct list_head   free_list[MIGRATE_TYPES];
  unsigned long    nr_free;
};

 

nr_free指定了当前内存区中空闲页块的数目(对0阶内存区逐页计算,...

前端数据结构--线性结构-链表

链表
  标准数组是一块连续的内存地址,所以在做插入、删除时会对数据进行大量的移动,如果数据量很大那么效率会比较低。如果我们把每一个元素都记录着下一个元素的地址,那我们在做插入、删除时是不是只需要改变下一个元素的地址即可, 如

 从存储结构来看链表不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用 

 常见的链表结构有单链表、双向链表、循环链表、双向循环链表。
单链表
  链表中的每一个节点都具备两个功能:一个功能是存储数据,另外一个功能是记录下一个节点的地址。当结点只记录下一个结点的地址且最后一个结点指向null,这种链表叫单链表。

...

35.图

1.定义变量
private ArrayList<String> vertexList; //存储顶点集合
private int[][] edges; //存储图对应的邻结矩阵
private int numOfEdges; //表示边的数目
//定义给数组boolean[], 记录某个结点是否被访问
private boolean[] isVisited;
 
2.构造器
public Graph(int n) {
//初始化矩阵和vertexList
edges = new int[n][n];
vertexList = new ArrayLis...

【Rust】结构体 struct

【Rust】结构体 struct

...

文章标题:6.4 图的存储结构
文章链接:https://www.dianjilingqu.com/51023.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>