最后更新时间: 2018/09/06 09:48
图
线性结构研究的是一对一的关系
树形结构研究的是一对多的关系
图研究的是数据元素之间多对多的关系
有向图 和 无向图
最小生成树(满足最小代价)、最短路径的意义和算法思想
图的存储方式和图的遍历
广度优先搜索
深度优先搜索
概念
对1个源点S,先访问它,接着遍历它的邻接表s.adj,先出现的先访问,如果s.adj被耗尽,递归返回到s所属于的邻接表所关联的源点s’
s是s’的邻接点
应用例子:
社交网络,朋友之间的一切关系。
路由当中的网络的一个节点。
地图应用中这个路口、建筑、地标、路很多
邻接表法:
用一个数组存储所有的顶点,对每个顶点,用一个链表存储该点的临接点。
邻接矩阵法:
使用一个二维数组A[][],对于一个边(u,v),置A[u][v]=1,否则就置A[u][v]=0
对于带权图,可以置A[u][v]=weight,weight表示权重。
优点:直观,适合稠密图
缺点:如果图的变数很少,或者说图是稀疏的,浪费很多空间
将图看作为二元组,V(vertex)是定点集,E(edge)是边集,每条边就是一个顶点对(v,w)
生成树是包含了图的所有顶点的连通子图
TSP(旅行商)的问题
并利用只能搜索算法中的遗传算法求TSP问题的近似解。结合图中最优路径、NP难题以及智能算法的扩展。