1.有向图和无向图
注:实现图的相关操作之前首先了解图的相关概念(有必要)
(1)有向图
V={V1,V2,V3,V4},A={<V1,V2>,<V1,V3>,<V4,V1>,<V3,V4>}
如上图所示:其中<V1,V2>表示有向图的V1->V2的一条弧,其中V1为弧尾,V2为弧头。
其中使用n表示有向图的顶点数,e表示边数或者弧的数目。
路径的长度:路径上的边数或者弧的数目(如果带有权值的话,那么是路径的权值之和)。
比如上面的V1->V2路径长度为1.
回路:第一个顶点和最后一个顶点相同的路径;比如上面的V1->V3->V4->V1。
(2)无向图
V={V1,V2,V3,V4,V5},A={(V1,V2),(V1,V3),(V3,V4),(V2,V4),(V4,V5)}
如上图所示:其中(V1,V2)表示V1和V2之间的一条边。
其中使用n表示有向图的顶点数,e表示边数或者弧的数目。
路径的长度:路径上的边数或者弧的数目(如果带有权值的话,那么是路径的权值之和)。
比如上面的V1->V2->V4路径长度为2.
回路:第一个顶点和最后一个顶点相同的路径;比如上面的V1->V3->V4->V2->V1。
2.有向图和无向图的邻接矩阵和邻接表
(1)有向图
邻接矩阵表示法:
邻接表表示法:
(2)无向图
邻接矩阵表示法:
邻接表表示法: