双公示 网站专栏建设,常见的cms网站,贸易公司注册多少钱,wordpress分类目录发不了文章邻接矩阵#xff1a;
1.概念#xff1a;
邻接矩阵是图的存储结构之一#xff0c;通过二维数组表示顶点间的连接关系。
2.具体例子 #xff1a;
一.无向图邻接矩阵示例#xff1a;
示例图#xff08;顶点#xff1a;A、B、C#xff0c;边#xff1a;A-B、B-C… 邻接矩阵
1.概念
邻接矩阵是图的存储结构之一通过二维数组表示顶点间的连接关系。
2.具体例子
一.无向图邻接矩阵示例
示例图顶点A、B、C边A-B、B-C
邻接矩阵A B C
A 0 1 0
B 1 0 1
C 0 1 0
特点
矩阵对称主对角线为0无自环边。顶点B的度为2对应第2行/列非零元素数量。非零元素总数边数×2无向图双向性。
二、有向图邻接矩阵示例
示例图顶点V1→V2、V2→V3、V3→V1
邻接矩阵V1 V2 V3
V1 0 1 0
V2 0 0 1
V3 1 0 0
特点
矩阵不对称边方向性。V3的入度1第3列非零数出度1第3行非零数。
三、带权图网邻接矩阵示例
示例图顶点A、B、C边A-B权2B-C权5
邻接矩阵∞表示无穷A B C
A 0 2 ∞
B 2 0 5
C ∞ 5 0
特点
权值替代0/1主对角线仍为0。对称性保留无向网稀疏图可能用压缩存储。
邻接表
概念
邻接表是图数据结构最常用的链式存储方式通过数组与链表结合实现顶点与边的离散化存储。
组成结构 顶点表头节点表一维数组存储顶点信息每个元素包含顶点值和指向首个邻接点的指针。边表链表节点每个顶点对应的链表存储其所有邻接点的索引或地址及边权重网图。例如顶点A的链表包含C表示存在边AC。
示例图结构
假设存在无向图如下顶点A、B、C、D边A-B、A-C、B-C、B-D、C-D A
/ \
B——C \ /D
邻接表存储实现
1. 顶点表顺序存储
顶点表使用数组存储每个元素包含顶点信息和指向邻接链表的指针
顶点表索引 | 顶点数据 | 边表头指针
---------------------------------
0 | A | → 1 → 2 → NULL
1 | B | → 0 → 2 → 3 → NULL
2 | C | → 0 → 1 → 3 → NULL
3 | D | → 1 → 2 → NULL
2. 边表链表存储
每个顶点的边表以链表形式存储邻接顶点本例使用头插法
顶点A的邻接链表B索引1、C索引2顶点B的邻接链表A索引0、C索引2、D索引3顶点C的邻接链表A索引0、B索引1、D索引3顶点D的邻接链表B索引1、C索引2
// C语言实现无向图
typedef struct ArcNode { // 边表节点 int adjvex; // 邻接顶点索引 struct ArcNode *next; // 指向下一邻接点
} ArcNode;typedef struct VNode { // 顶点表节点 char data; // 顶点数据 ArcNode *firstarc; // 指向第一个邻接点
} VNode, AdjList[MAX_VERTEX];typedef struct {AdjList vertices; // 顶点表数组 int vexnum, arcnum; // 顶点数和边数
} ALGraph;
