图数据结构的定义

╰半橙微兮° 2023-03-12 12:19 2阅读 0赞

用邻接矩阵和邻接表存储，将其命名为文件**graph.h头文件**，后续图的所有算法都依赖于该文件。

**1.邻接矩阵存储方法**

邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有*n*（*n*＞0）个顶点的图，顶点的顺序依次为0～*n*\-1，则G的邻接矩阵*A*是*n*阶方阵，其定义如下：

（1）如果G是无向图，则：

A\[*i*\]\[*j*\]=1：若(*i*,*j*)∈E(G)   0:其他

（2）如果G是有向图，则：

A\[*i*\]\[*j*\]=1：若<*i*,*j*>∈E(G)  0:其他

（3）如果G是带权无向图，则：

A\[*i*\]\[*j*\]= wij ：若*i*≠*j*且(*i*,*j*)∈E(G)    0：*i*=*j*    ∞：其他

（4）如果G是带权有向图，则：

A\[*i*\]\[*j*\]=  wij ：若*i*≠*j*且<*i*,*j*>∈E(G)   0：i=j　∞：其他

邻接矩阵的特点如下：

（1）图的邻接矩阵表示是唯一的。

（2）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。

（3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵，因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。

（4）对于无向图，邻接矩阵的第*i*行（或第*i*列）非零元素（或非∞元素）的个数正好是第*i*个顶点的度。

（5）对于有向图，邻接矩阵的第*i*行（或第*i*列）非零元素（或非∞元素）的个数正好是第*i*个顶点的出度（或入度）。

（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。

邻接矩阵的数据类型定义如下：

\#define  MAXV  <最大顶点个数>

typedef struct

\{  int no;  //顶点编号

InfoType info;  //顶点其他信息

\} VertexType;  //顶点类型

typedef struct    //图的定义

\{  int edges\[MAXV\]\[MAXV\];   //邻接矩阵

int n，e;    //顶点数，弧数

VertexType vexs\[MAXV\];  //存放顶点信息

\} MGraph;  //图的邻接矩阵表示类型

**2  邻接表存储方法**

图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。在邻接表中，对图中每个顶点建立一个单链表，第*i*个单链表中的节点表示依附于顶点*i*的边（对有向图是以顶点*i*为尾的边）。每个单链表上附设一个表头节点。

其中，表节点由三个域组成，adjvex指示与顶点*i*邻接的点在图中的位置，nextarc指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。

表头节点由两个域组成，data存储顶点*i*的名称或其他信息，firstarc指向链表中第一个节点。

定义存储结构如下：

typedef struct ANode

\{  int adjvex;  //该边的终点编号

struct ANode \*nextarc;  //指向下一条边的指针

InfoType info;  //该边的相关信息

\} ArcNode;  //边表节点类型

typedef struct Vnode

\{  Vertex data;  //顶点信息

ArcNode \*firstarc;  //指向第一条边

\} VNode;  //邻接表头节点类型

typedef VNode AdjList\[MAXV\];  //AdjList是邻接表类型

typedef struct

\{  AdjList adjlist;  //邻接表

int n,e;  //图中顶点数n和边数e

\} ALGraph;  //完整的图邻接表类型

将其命名为文件**graph.h头文件**

完整定义如下：

typedef int InfoType;
    #define	MAXV 100				//最大顶点个数
    //以下定义邻接矩阵类型
    typedef struct 
    {  	int no;						//顶点编号
    	InfoType info;				//顶点其他信息
    } VertexType;					//顶点类型
    typedef struct  				//图的定义
    {  	int edges[MAXV][MAXV]; 		//邻接矩阵
       	int n,e;   					//顶点数，弧数
    	VertexType vexs[MAXV];		//存放顶点信息
    } MGraph;						//图的邻接矩阵类型
    //以下定义邻接表类型
    typedef struct ANode           	//弧的结点结构类型
    {	int adjvex;              	//该弧的终点位置
       	struct ANode *nextarc; 		//指向下一条弧的指针
       	InfoType info;           	//该弧的相关信息,这里用于存放权值
    } ArcNode;
    typedef int Vertex;
    typedef struct Vnode      		//邻接表头结点的类型
    {	Vertex data;            	//顶点信息
    	int count;             		//存放顶点入度,只在拓扑排序中用
        ArcNode *firstarc;     		//指向第一条弧
    } VNode;
    typedef VNode AdjList[MAXV];	//AdjList是邻接表类型
    typedef struct 
    {	AdjList adjlist;         	//邻接表
        int n,e;                 	//图中顶点数n和边数e
    } ALGraph;                   	//图的邻接表类型