有关有向图和无向图

发布于:2023-01-10 ⋅ 阅读:(297) ⋅ 点赞:(0)

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)无向图

邻接矩阵表示法:

 邻接表表示法:

3.有向图和无向图的深度优先遍历和广度优先遍历

广度优先搜索算法(有向图和无向图)

深度优先搜索算法(有向图和无向图)