-
array
查看全部 -
great
查看全部 -
看!虎头虎尾
查看全部 -
十字链表方式存储图的数据结构和存储内容
查看全部 -
链式存储图的一些表示方法。
存储的数据比较多
查看全部 -
邻接表-链式存储
顶点的表示:顶点索引+出弧链表头指针+顶点数据
弧:弧头顶点索引+下一条弧指针+弧数据
逆邻接表:记录的是 入弧链表头指针 和 弧尾顶点索引
struct Node{顶点索引;该顶点弧链表的头结点;顶点数据;}
struct Arc{指向的顶点索引;指向下一条弧的指针;弧信息;}
struct Map{顶点数组;}
查看全部 -
顶点:
顶点索引 出弧链表头指针 顶点数据
| | |
顶点索引 第一个出弧的指针(可以是NULL) 顶点数据
弧的表示方法:
弧头顶点索引 下一条弧指针 弧数据
| | |
弧头顶点(指向的点) 一个点有多个弧 弧数据
每个弧保存下一条弧的指针
查看全部 -
连通图:对于任何顶点都有通往其它顶点的边,即任意两个点之间都是连通的
完全图:任意顶点与其它顶点之间都能直接连接,边数与顶点间的数量关系:n(n-1)/2
生成树:顶点和仅能够连接这些顶点的边组成的,边数与顶点间的数量关系:n-1
查看全部 -
Prim算法:
选了F点后:
Kruskal算法:(最先选最小的边,再选次笑的边,前提是选边后不要造成闭环)
因为选的边没有交集,所以点集合分为两个集合
查看全部 -
图的遍历:深度搜索(前序遍历)和广度搜索
深度搜索(前序遍历):
广度搜索(较好理解,一层一层地搜索)
不同的搜索方式得到的生成树不同,上述较为简单,未涉及到权的问题。
若有权:最小生成树
两种算法:Prim算法 & Kruskal算法
查看全部 -
查看全部
-
邻接矩阵用数组进行表达,相对来说比较简单。
邻接表和十字链表都是用链表表达,主要用于表示有向图。
邻接多重表则用于表示无向图。
领接矩阵:
自身不能到达自身,所以为0,以上是有向图,无向图的矩阵是对称的,所以克制抵只记录上或者下三角矩阵
数据结构用代码进行表示:
邻接表(记录出弧的链表的头指针):逆-入弧
这样的数据结构方式如何通过数据结构的代码来实现呢?
查看全部 -
可以把无向图中每一条连线当成有向图中的两条连线(去、回)
有向图中:
出度:一个顶点发出去的箭头数量
无向图中:
对于无向图来说,如果满足每一个顶点,都有通往其他顶点的连线(直接或间接)这样的图称为连通图。
在无向图中,如果任意顶点 与其他顶点都有连线,这样的图称为完全图。
查看全部 -
2. demo.cpp
查看全部 -
1. demo.cpp
查看全部
举报