以此可使用算法方便的计算出如航班线路中的最短路径、如火车线路中的最佳中转方案,如社交圈中谁与谁关系最好、婚姻网中谁与谁最般配……
2.1 图的概念
----
顶点:顶点也称为节点,顶点本身是有数据含义的...因路径不只一条,所以,从一个项点到另一个项点的路径描述也不仅只一种。
在图结构中如何计算路径?
无权重路径的长度是路径上的边数。
有权重路径的长度是路径上的边的权重之和。...所有的边构成关系集合信息,这里用 E 表示(城市与城市之间的关系描述)。
如何描述边?
边用来表示项点之间的关系。所以一条边可以包括 3 个元数据(起点,终点,权重)。...如上的图结构可以描述如下:
# 5 个顶点
V={A0,B1,C2,D3,E4}
# 7 条边
E={ (A0,B1,3),(B1,C2,4),(C2,D3,6),(C2,E4,1),(D3,E4,2)...人的思维是知识性、直观性思维,在路径查找时不存在所谓的尝试或碰壁问题。而计算机是试探性思维,就会出现这条路不通,再找另一条路的现象。
所以最短路径算法中常常会以错误为代价,在查找过程中会走一些弯路。