软装设计网站有哪些,最大的网站建设公司排名,动漫设计和动漫制作技术哪个更好,口腔医院网站建设文章目录 1. 引言2. 邻接表表示图的原理2.0 图的基础知识a. 类型b. 表示 2.1 有向权图2.2 无向权图2.3 无向非权图2.4 有向非权图 3. 实验内容3.1 实验题目#xff08;一#xff09;数据结构要求#xff08;二#xff09;输入要求#xff08;三#xff09;输出要求 3.2 算… 文章目录 1. 引言2. 邻接表表示图的原理2.0 图的基础知识a. 类型b. 表示 2.1 有向权图2.2 无向权图2.3 无向非权图2.4 有向非权图 3. 实验内容3.1 实验题目一数据结构要求二输入要求三输出要求 3.2 算法实现 4. 实验结果 1. 引言 图是一种常见的数据结构用于表示对象之间的关系。在图的表示方法中邻接表是一种常用的形式特别适用于稀疏图。 本实验将介绍如何使用邻接表表示图并通过C语言实现图的邻接表创建。 2. 邻接表表示图的原理
2.0 图的基础知识
a. 类型 图Graph是由节点Vertex和节点之间的边Edge组成的一种数据结构。图可以用来表示不同对象之间的关系或连接方式。在图中每个节点代表一个对象而边则表示节点之间的关系或连接。根据边的性质图可以分为有向图Directed Graph和无向图Undirected Graph两种类型。 有向图是指图中的边具有方向性表示节点之间的单向关系。例如如果节点A指向节点B的边存在则从节点A可以到达节点B但从节点B无法直接到达节点A。有向图中的边可以是单向的也可以是双向的。 无向图是指图中的边没有方向性表示节点之间的双向关系。无向图中的边是双向的即从节点A可以到达节点B同时从节点B也可以到达节点A。
b. 表示 图可以用多种方式表示常见的有邻接矩阵Adjacency Matrix和邻接表Adjacency List两种形式。 邻接矩阵是一个二维数组用于表示节点之间的连接关系。对于有向图邻接矩阵的元素表示从一个节点到另一个节点的边的存在与否对于无向图邻接矩阵是对称的。 邻接表是一种链表数组的形式用于表示每个节点和与之相连的边。对于每个节点邻接表中存储了与该节点直接相连的所有节点的信息。
2.1 有向权图 有向权图Directed Weighted Graph是指图中的边具有方向性和权重Weight表示节点之间的单向关系以及边的权值。每条边都有一个与之关联的权重用于表示节点之间的某种度量或成本。 2.2 无向权图 无向权图Undirected Weighted Graph是指图中的边没有方向性但具有权重表示节点之间的双向关系以及边的权值。无向权图中的边是双向的权重可以用于表示节点之间的某种度量或成本。
2.3 无向非权图 无向非权图Undirected Unweighted Graph是指图中的边没有方向性也没有权重表示节点之间的双向关系但没有额外的权值信息。无向非权图中的边是双向的仅表示节点之间的连接关系不含其他度量或成本信息。 2.4 有向非权图 有向非权图Directed Unweighted Graph是指图中的边具有方向性但没有权重表示节点之间的单向关系但没有额外的权值信息。有向非权图中的边可以是单向的表示从一个节点指向另一个节点的关系但不包含其他度量或成本信息。
3. 实验内容
3.1 实验题目 将邻接矩阵存储转换为邻接表存储
一数据结构要求 邻接表中的顶点表用Head 数组存储顶点表中元素的两个域的名字分别为 VerName和 Adjacent边结点的两个域的名字分别为 VerAdj 和 link。边链表中的边结点按照顶点序号从小到大的顺序存储。
二输入要求
{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}三输出要求
按照顶点编号从小到大的顺序依次输出每个顶点的边链表。形如 “顶点 0 的边链表为1-2-3-4-5-6-7-8”
3.2 算法实现
#includestdio.h
#includestdlib.h
#define N 7
int 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 struct P{int VerAdj ;struct P *link;
}P;
typedef struct Q{int VerName;P *Adjacent;
}Q;
typedef struct{Q Head[20];
}Graph;
void Create(Graph *g)
{int 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 j;q-linkNULL;p-linkq;pq;}}}}
}
void Output(Graph g)
{int i;for(i0;iN;i){printf(顶点%d的边链表为,i);P *pg.Head[i].Adjacent;while(p){printf(%d,p-VerAdj );pp-link;if(p) printf(—);}printf(\n);}
}
int main()
{Graph g;Create(g);Output(g);
}
4. 实验结果
