网站 开发 语言,安居客二手房,软件开发服务税率,产品创新设计方案目录 6.3 储存结构#xff08;邻接表表示法#xff09;1. 储存方式2. 结构3. 图的邻接表存储表示#xff08;算法#xff09;4. 结论5. 邻接矩阵和邻接表的对比邻接矩阵优点#xff1a;缺点#xff1a; 邻接表优点#xff1a;缺点#xff1a; 邻接矩阵与邻接表的关系 6… 目录 6.3 储存结构邻接表表示法1. 储存方式2. 结构3. 图的邻接表存储表示算法4. 结论5. 邻接矩阵和邻接表的对比邻接矩阵优点缺点 邻接表优点缺点 邻接矩阵与邻接表的关系 6.4.拓展存储结构十字链表邻接多重表很绕多理解1. 十字链表存储有向图2. 邻接多重表存储无向图 6.5 四种存储结构的对比 6.3 储存结构邻接表表示法
1. 储存方式 2. 结构
【1】顶点的结点结构 ——————— | data | firstarc | ———————
data数据域储存顶点vi firstarc链域指向链表中第一个结点 【2】弧的结点结构 —————————— | adjvex | info | nextarc | ——————————
adjvex邻接点域与顶点vi邻接的点在图中的位置 info数据域储存和边相关的信息如权值 nextarc链域与顶点vi的点在图中的位置
3. 图的邻接表存储表示算法
#define MAX_VERTEXT_NUM 20
//建立边结点
typedef struct ArcNode {int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧InfoType *info; // 该弧相关信息可选
}ArcNode;
// 顶点结点
typedef struct VNode{VertexType data; // 顶点信息ArcNode *firstarc; // 指向第一条依附该顶点的弧
}VNode,AdjList[MAX_VERTEXT_NUM];
//邻接表
typedef struct {Adjlist vertices;int vexnum,arcnum;int kind;
}ALGraph;
//建立邻接表算法
//初始化一个结点总数为num的图k为图的类型num为结点总数
void InitG(ALGraph G,enum GraphKind k,int num)
{G.kindk;G.vexnumnum;G.verticesnew VNode[vexnum];for(int i0;iG.vexnum;i){G.vertices[i].FirstarcNULL;cinG.vertics[i].data;}
}//有向图(网)增加弧的算法将弧(from,to,weight)加入图
void InsertArc(ALGragh G,int from,int to,int weight)
{ArcNode *snew ArcNode;s-weightweight;s-adjvexto;s-nextarcG.vertices[from].firstarc;//插到链表vertices[from]的头G.vertices[from].firstarcs;
}
4. 结论
1在邻接表中同一条边对应两个结点。 2无向图中顶点v的度等于v 对应的链表的长度但是在有向图中要求顶点A的的入度则需要遍历所有的顶点连接的链表判断有几个存在顶点A求出度则是A顶点链表有几个点。 3判定两顶点vw是否邻接要看v对应的链表中有无对应的结点w相反判断也行 4对于一个图给定的邻接表是并不唯一的区分与邻接矩阵 5增减边要在两个单链表插入、删除结点 6占用存储空间与顶点数、边数均有关适用于边稀疏的图
注意在有向图的邻接表中不易找到指向该顶点的弧。 邻接矩阵表示唯一邻接表表示不唯一
5. 邻接矩阵和邻接表的对比 图是计算机科学中重要的数据结构之一用于表示多对多的关系。在实际应用中图可以用于表示网络拓扑、社交关系、路由算法等。对于图的存储结构有两种常见的方式邻接矩阵和邻接表。本文将介绍这两种存储结构的原理和特点并对比它们之间的关系。
邻接矩阵
邻接矩阵是一种使用二维数组来表示图的存储结构。对于有n个节点的图邻接矩阵是一个n*n的矩阵其中的元素表示节点之间的关系。如果图中的节点i和节点j之间有边相连则邻接矩阵中的第i行第j列的元素为1否则为0。
优点
查询快速由于邻接矩阵是一个二维数组可以通过下标直接访问节点之间的关系查询操作的时间复杂度为O(1)。空间效率在稠密图边数接近节点数平方中邻接矩阵的存储效率较高。
缺点
空间复杂度高对于稀疏图边数远小于节点数平方邻接矩阵会浪费大量空间来表示不存在的边。
class Graph {
private:int V; // 节点数int** adjMatrix; // 邻接矩阵public:Graph(int vertices) {V vertices;adjMatrix new int*[V];for (int i 0; i V; i) {adjMatrix[i] new int[V];for (int j 0; j V; j) {adjMatrix[i][j] 0;}}}void addEdge(int src, int dest) {adjMatrix[src][dest] 1;adjMatrix[dest][src] 1;}// 其他操作...
};邻接表
邻接表是一种使用链表来表示图的存储结构。对于有n个节点的图邻接表是一个包含n个链表的数组每个链表存储与节点i相邻的节点。
优点
空间效率高在稀疏图中邻接表可以节省大量空间只存储存在的边。插入和删除快速在邻接表中插入或删除边相对较快。
缺点
查询效率低在邻接表中查询节点i和节点j之间是否有边需要遍历链表平均时间复杂度为O(V)。
class Graph {
private:int V; // 节点数vectorlistint adjList; // 邻接表public:Graph(int vertices) {V vertices;adjList.resize(V);}void addEdge(int src, int dest) {adjList[src].push_back(dest);adjList[dest].push_back(src);}// 其他操作...
};邻接矩阵与邻接表的关系
邻接矩阵和邻接表是两种不同的图的存储结构各自有着优缺点。对于边稠密的图邻接矩阵可以提供较好的查询效率和空间效率而对于边稀疏的图邻接表则更加节省空间。
在实际应用中我们需要根据具体的图的特点和操作需求来选择合适的存储结构。如果图是边稠密的且需要频繁进行查询操作邻接矩阵可能是一个不错的选择如果图是边稀疏的邻接表可以更好地节省空间。在有些情况下我们也可以结合使用邻接矩阵和邻接表充分发挥它们各自的优势以满足实际需求。
综上所述邻接矩阵和邻接表是图的两种常见存储结构它们各自有着优缺点。在实际应用中需要根据图的特点和操作需求进行选择以达到最优的性能和空间效率。
6.4.拓展存储结构十字链表邻接多重表很绕多理解
1. 十字链表存储有向图
空间复杂度O(|V||E|) 同层可找所有出边即出度绿色不同层相连的即所有入边橙色比邻接表空间复杂度的 v 2 v^2 v2更小
2. 邻接多重表存储无向图
解决无向图冗余信息的问题空间大删除边删除结点操作更简单只要顺着指针找就跟删除链表结点一样空间复杂度O(|V||E|)比邻接表的v2e因为不存储无关的结点
6.5 四种存储结构的对比
