格式约定:
用邻接表的方式来存储图,在文件中,每一行数据代表图的一个节点,行的格式可以采用
一下格式:
ID Edges
其中 ID 代表节点的标识,Edges 代表从某一节点出发的所有的边(对于有向图)Edges 又
可以用从该节点出发的边的另一端的节点表示。例如图 1.1 就可以用邻接表表示。
在求解图的问题时,图中的节点和边往往含有更多的信息,在用标色法求解单元最短路径
时,节点的信息还包括节点的颜色、节点到源点的距离等,边的信息包括边的权值等。对
以上邻接表作稍微改进便可满足要求。更新后的图文件的每一行的格式如下:
ID distance color
Edges(weight)
图 1.1 所示有向图加上权值信息后如图 1.2 所示,用邻接表表示如下
其中 MAX 表示无穷大,颜色域,0:白色;1:灰色;2:黑色