【摘要】：如果点对是有序的,那么,图的边是有方向的,称为有向图。图中的一条路径是一个顶点序列(w1,w2,…如果无向图中的任意一个顶点到另一个其他顶点都存在一个路径,则称为连通图。如果一个有向图也有此性质,则称为强连通图。可以用一个二维数组,称为邻接矩阵表达图,每个行或列表示结点,数组元素表达结点与结点之间的边(的距离),如果距离为∞,表示两个结点不连通。
一个图(Graph)G=(V,E)由顶点(Vertex)集合V 和边(edge)结合E 组成。每条边是点对(v,w),其中v,w∈V。边也称为弧(arc)。如果点对是有序的,那么,图的边是有方向的(directed),称为有向图(digraph)。
图中的一条路径(path)是一个顶点序列(w1,w2,…,wN),且 （wi,wi+1）∈E,1≤i<N。这样一条路径的长度为该路径上的边数,等于N-1。
如果路径不包含任何边,则其长度为零。如果图含有一条从一个顶点到自身的边,那么,这个路径是一个环(loop)。如果无向图中的任意一个顶点到另一个其他顶点都存在一个路径,则称为连通图(connected)。如果一个有向图也有此性质,则称为强连通图。(www.xing528.com)
可以用一个二维数组,称为邻接矩阵(adjacency matrix)表达图,每个行或列(或数组的下标)表示结点,数组元素表达结点与结点之间的边(的距离),如果距离为∞,表示两个结点不连通。
一个图中是否有连通回路,寻找两个结点间是否有一条连通路径,以及寻找最短的路径算法是十分重要和经常使用的。例如,广泛用于航空、铁路、公路运输、邮政路线的规划,数据通信网络(参见第5章)等场合。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
