计算机中所说的图是指离散数学中的图
如下图：
tu.jpg
上图中的圆圈叫作顶点，也叫作结点，链接顶点的线叫作边。也就是说，由顶点和连接每对顶点的边所构成的图形就是图。
图可以用来表现各种关系，如果将车站作为顶点，相邻两个站点用边连接，就能用来表示路线了。
另外，还可以在计算机网络中把路由器作为顶点，将相互连接的两个路由器用边连接，这样就能用图来表现网络的连接关系了。
加权图
图是由顶点和边连接而成，我们还可以给边添加一个值。
这个值叫做权重或者权，加了权的图叫作加权图。没有权的边只能表示两个顶点的连接状态，而有权的边就可以表示顶点之间的连接程度。
根据图点的内容不同，这个连接程度也不同。比如在计算机网络中，给两台路由器之间的边添加传输数据所需要的时间，这张图就能表示网络之间的通信时间了。
而在路线途中，如果把地铁在两个车站之间的行驶时间加上，这张图就能表现整个路线的移动时间，如果把这两个车站间的票价加上，就能表现乘车费用了。
有向图
当我们想在路线图中表示该路线只能单向行驶时，就可以给边加上箭头，这样的图就是有向图。与此想对应，边上没有箭头的图便是无向图。
下图中我们可以从顶点A到B但是不能从B到A,而B和C之间有两条分指向两个方向，因此可以双向移动。
和无向图一样，有向图的边可以加上权重。
在下图中，从顶点B到顶点C的权重为5，而从顶点C到顶点B的权重是7。
如果做得是一个表示移动时间的图，而从B到C是下坡路，就有可能是这种情况。这种情况属于有向图中的非对称的权重。
图的便利
假设图有两个顶点s和t,而我们设置了一种算法，可以找出从s到t的权重之间和最小的那条路径。
那么这种算法就可以泳道这些问题中：
寻找计算机网络中通信时间最短的路径；
寻找路线图中耗时最短的路径；
寻找路线图中最省车费的路径等。
网友评论