最后更新时间： 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难题以及智能算法的扩展。