图论初探
Eqvpkbz's Site

图论初探

图论的约定和表述

给定图$G \ = \ (V,E)$,以图的结点数$|V|$与边的条数$|E|$作为输入的规模,同时,仅当在渐近符号(如大$O$表示或大$\Theta$表示)中,符号$V$表示$|V|$,符号$E$表示$|E|$,比如我们说算法的时间复杂度为$O(VE)$,同时,用$G.V$表示图$G$的结点集,用$G.E$表示图$G$的边集合

图论的表示

对于$G \ = \ (V,E)$可以用三种方式来表示

邻接链表

邻接矩阵

链式前向星

基本图算法

广度优先算法$(BFS)$

复杂度$O(V + E)$

最短路径
广度优先树

深度优先搜索$(DFS)$

拓扑排序