基础知识a.

图是一种常见的数据结构用于表示对象之间的关系。

在图的表示方法中邻接表是一种常用的形式特别适用于稀疏图。

本实验将介绍如何使用邻接表表示图并通过C语言实现图的邻接表创建。

2.0

图Graph是由节点Vertex和节点之间的边Edge组成的一种数据结构。

图可以用来表示不同对象之间的关系或连接方式。

在图中每个节点代表一个对象而边则表示节点之间的关系或连接。

根据边的性质图可以分为有向图Directed

Graph和无向图Undirected

有向图是指图中的边具有方向性表示节点之间的单向关系。

例如如果节点A指向节点B的边存在则从节点A可以到达节点B但从节点B无法直接到达节点A。

有向图中的边可以是单向的也可以是双向的。

无向图是指图中的边没有方向性表示节点之间的双向关系。

无向图中的边是双向的即从节点A可以到达节点B同时从节点B也可以到达节点A。

Matrix和邻接表Adjacency

邻接矩阵是一个二维数组用于表示节点之间的连接关系。

对于有向图邻接矩阵的元素表示从一个节点到另一个节点的边的存在与否对于无向图邻接矩阵是对称的。

邻接表是一种链表数组的形式用于表示每个节点和与之相连的边。

对于每个节点邻接表中存储了与该节点直接相连的所有节点的信息。

2.1

Graph是指图中的边具有方向性和权重Weight表示节点之间的单向关系以及边的权值。

每条边都有一个与之关联的权重用于表示节点之间的某种度量或成本。

2.2

Graph是指图中的边没有方向性但具有权重表示节点之间的双向关系以及边的权值。

无向权图中的边是双向的权重可以用于表示节点之间的某种度量或成本。

2.3

Graph是指图中的边没有方向性也没有权重表示节点之间的双向关系但没有额外的权值信息。

无向非权图中的边是双向的仅表示节点之间的连接关系不含其他度量或成本信息。

2.4

Graph是指图中的边具有方向性但没有权重表示节点之间的单向关系但没有额外的权值信息。

有向非权图中的边可以是单向的表示从一个节点指向另一个节点的关系但不包含其他度量或成本信息。

实验内容

A[N][N]{{0,1,1,1,1,0,0},{0,0,1,1,0,0,0},{1,0,0,0,0,0,0},{0,0,1,0,0,0,0},{0,0,0,0,0,1,1},{0,0,0,0,0,0,1},{0,0,0,0,0,0,0}

typedef

i,j,n,t;for(i0;iN;i){g-Head[i].VerNamei;g-Head[i].AdjacentNULL;P

*p(P*)malloc(sizeof(P));t0;for(j0;jN;j){if(A[i][j]){if(t0){//printf(%d%d

,A[i][j],j);g-Head[i].Adjacentp;p-VerAdj

j;p-linkNULL;t1;}else{//printf(%d%d

,A[i][j],j);P

*q(P*)malloc(sizeof(P));q-VerAdj

void

i;for(i0;iN;i){printf(顶点%d的边链表为,i);P

*pg.Head[i].Adjacent;while(p){printf(%d,p-VerAdj

);pp-link;if(p)