存储结构:邻接矩阵(有向图和无向图均可存储),邻接表(不易删除某个顶点,而且对于有向图不易存储),十字链表(结合邻接表以及逆邻接表的存储方式,存储有向图)
十字链表存储的不是顶点,而是从顶点出的弧,或者入的弧
图的遍历
分为深度优先遍历(Depth-First Search DFS)(会有回走的步骤)邻接矩阵的时间复杂度为O(n2),邻接表的时间复杂度为O(n)代码使用遍历实现
以及广度优先遍历(Breadth-First Search BFS)
存储结构:邻接矩阵(有向图和无向图均可存储),邻接表(不易删除某个顶点,而且对于有向图不易存储),十字链表(结合邻接表以及逆邻接表的存储方式,存储有向图)
十字链表存储的不是顶点,而是从顶点出的弧,或者入的弧
分为深度优先遍历(Depth-First Search DFS)(会有回走的步骤)邻接矩阵的时间复杂度为O(n2),邻接表的时间复杂度为O(n)代码使用遍历实现
以及广度优先遍历(Breadth-First Search BFS)