做移动网站点击软件,北京专业网站设计公司,永久开源的免费建站系统,最新国际新闻10条1.图的存储 图用来对关系建模#xff0e;图是节点和边构成的集合#xff0e;节点反映图的元素集合#xff0c;边反映图的元素集合中元素间的关系#xff0e; 上述是由五个节点#xff0c;三条边构成的结构#xff0e;我们可以用图对其建模#xff0e;
对由节点#x…1.图的存储 图用来对关系建模图是节点和边构成的集合节点反映图的元素集合边反映图的元素集合中元素间的关系 上述是由五个节点三条边构成的结构我们可以用图对其建模
对由节点边构成的集合采用图结构表示时候我们可以有两种基本选择这两种基本选择引出图结构两种基本存储方式邻接表存储矩阵存储
(1). 邻接表存储 我们依次存储图中每个节点对节点间关系采用邻接表方式 针对上述实例具体为
#include stdio.h
#include stdlib.h
templateclass EdgeInfo
class AdjNode{
public:AdjNode* m_pNext nullptr;EdgeInfo m_stInfo;int m_nId;
};
templateclass T, class EdgeInfo
class Node{
public:T m_stEle;AdjNodeEdgeInfo* m_pList nullptr;
};
int main(){Nodeint, int stNodes[5];AdjNodeint stAdjNode[3];stAdjNode[0].m_nId 2;stAdjNode[0].m_stInfo 11;stAdjNode[1].m_nId 1;stAdjNode[1].m_stInfo 14;stAdjNode[2].m_nId 1;stAdjNode[2].m_stInfo 12;stNodes[0].m_pList stAdjNode[0];stNodes[3].m_pList stAdjNode[1];stNodes[4].m_pList stAdjNode[2];
}这种表示方法下通过节点可以找到以该节点为起点的所有边的信息 (2). 矩阵存储 我们依次存储图中每个节点对节点间关系采用矩阵方式存储 针对上述实例具体为
#include stdio.h
#include stdlib.h
templateclass T
class Node{
public:T m_nEle;
};
templateclass EdgeInfo
class Edge{
public:bool m_bValid false;EdgeInfo m_stInfo;
};
int main(){Nodeint stNodes[5];Edgeint stEdges[5][5];stEdges[0][2].m_bValid true;stEdges[0][2].m_stInfo 11;stEdges[4][1].m_bValid true;stEdges[4][1].m_stInfo 12;stEdges[3][1].m_bValid true;stEdges[3][1].m_stInfo 14;
}这种表示方法下通过矩阵来存储所有边的信息
(3). 总结 当图的边的数量较少时采用邻接表方式比较节省空间 当图的边的数量较多时采用矩阵方式有助于快速定位边的信息和存在性
2.图的转置 即逆转图中的关系 针对上述实例转置处理后示意图如下 3.拓扑排序 (1). 定义 拓扑排序是对一个有向无环图的顶点进行排序的过程。这个排序的目的是将图中的所有顶点排成一个线性序列使得对于图中的任意一对顶点u和v如果存在一条从u到v的边那么u在线性序列中的位置就出现在v之前。这样的线性序列被称为满足拓扑次序的序列简称拓扑序列。
拓扑排序在计算机科学和图论中具有重要的应用。它常被用来确定一个依赖关系集中事物发生的顺序。例如在一个工程项目中各个子工程或任务之间可能存在一定的依赖关系即一个子工程必须在另一个子工程完成后才能开始。通过拓扑排序我们可以得到一个合理的子工程执行顺序从而确保项目能够顺利进行。 (2). 实例 拓扑排序的一个实例可以是一个课程安排的场景。假设我们有一个学校的课程安排其中一些课程是其他课程的前置课程也就是说在修读某些课程之前必须先完成其他特定的课程。我们可以将这些课程看作有向无环图中的顶点而将前置课程关系看作图中的有向边。
例如假设我们有以下课程及其前置课程关系 课程A是课程B的前置课程 课程B是课程C和课程D的前置课程 课程C是课程E的前置课程 这可以表示为以下的有向无环图 现在我们想要对这些课程进行拓扑排序以确定一个学生可以按照该顺序完成所有课程的合理学习路径。使用拓扑排序算法我们可以得到以下的一个可能的拓扑序列A - B - C - D - E (3). 算法实现 a. 创建一个队列并将所有入度为0的顶点加入队列一个存储拓扑排序结果的集合。 b. 当队列非空时循环执行以下步骤 b.1. 从队列中取出一个顶点。 b.2. 将其添加到结果集合尾部。 c.2. 对于该顶点的所有邻接顶点将其入度减1。如果入度变为0则将该邻接顶点加入队列。 c. 如果图中还有顶点未被输出则图中存在环无法进行拓扑排序否则算法结束
