数据结构第六讲:图(上)

6.1 什么是图

什么是图

怎么在程序中表示一个图

邻接矩阵

找到Gij在数组中的对应下标很容易,反过来貌似还是挺困难的。

邻接表

6.2 图的遍历

深度优先搜索(DFS)

对于邻接表,N个顶点需要遍历,每个顶点只需要遍历该链表上的结点,也就是一共2E(一条边会被在不同的链表各存一次)个结点,所以是O(N+2E)

对于邻接矩阵,每个顶点都需要遍历,而对于每个顶点,都需要遍历它和所有其他顶点的对应值才能知道是否是邻接点,因此是$O(N^2)$

广度优先搜索(BFS)

类似于层序遍历

为什么需要两种遍历?

不同的情况下不同的遍历方式会更有优势

图不连通怎么办?

强连通图依旧是有向图,虽然任意两顶点之间都可以互通往来,存在性质上的区别,不能和无向图中的连通图混为一谈。

对于非连通图,需要遍历所有顶点去实现bfs或者dfs,对于连通图,只需要从一个初始点出发就可以。

6.3 应用实例:拯救007

6.4 应用实例:六度空间

小白专场:如何建立图