❤️详解「 邻接表 」原理、算法实现及其深度优先遍历、广度优先遍历(C/C++描述) |
您所在的位置：网站首页 › 深度优先搜索和遍历 › ❤️详解「 邻接表 」原理、算法实现及其深度优先遍历、广度优先遍历(C/C++描述) |
❤️详解「 邻接表 」原理、算法实现及其深度优先遍历、广度优先遍历(C/C++描述)
|
目录 图的表示：邻接表 邻接表结构原理 邻接表的数据结构 邻接表的初始化 邻接表的创建 邻接表的深度遍历 1）深度优先遍历算法原理 2）深度优先遍历算法实现 邻接表的广度遍历 1）广度优先遍历算法原理 2）广度优先遍历算法实现 算法验证 程序清单 图的表示：邻接表 邻接表结构原理在邻接列表实现中，每一个顶点会存储一个从它这里开始的相邻边的列表。比如，如果顶点 B 有一条边到 A、C 和 E，那么 A 的列表中会有 3 条边。 邻接列表只描述指向外部的边。B 有一条边到 A，但是 A 没有边到 B，所以 B 没有出现在 A 的邻接列表中。 查找两个顶点之间的边或者权重会比较费时，因为遍历邻接列表直到找到为止。
邻接表的数据结构 typedef struct _EdgeNode//与结点连接的边 { int adjvex;//邻接的顶点 int weight;//权重 struct _EdgeNode *next;//指向下一个顶点/边 }EdgeNode; typedef struct _VertexNode//顶点结点 { char data;//结点数据 struct _EdgeNode *first; }VertexNode,*AdjList; typedef struct _AdJListGraph { AdjList adjList;//顶点数组 int numVex; int numEdg; }AdjListGraph; 邻接表的初始化 bool Init(AdjListGraph &gh) { gh.adjList = new VertexNode[MAXSIZE];//分配顶点数组地址 if (!gh.adjList) return false; gh.numEdg = 0; gh.numVex = 0; } 邻接表的创建 //寻找顶点的数据找到数组的下标 int Location(AdjListGraph gh, char c) { if (gh.numVex > gh.numEdg; if (gh.numVex > MAXSIZE) return; cout vj; i = Location(gh, vi); j = Location(gh, vj); if (i>=0 && j>=0) { //头插法插入边 EdgeNode *temp = new EdgeNode; temp->adjvex = j; temp->next = gh.adjList[i].first; gh.adjList[i].first = temp; } } } 邻接表的深度遍历 1）深度优先遍历算法原理 ❤️ 首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点； ❤️ 当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直到所有的顶点都被访问过。
|
【本文地址】
今日新闻 |
推荐新闻 |