图的搜索技术是图算法领域的核心。
1、图的表示
通常采用两种方法表示一个图G=(V, E)，即邻接表和邻接矩阵。
邻接表，表示稀疏图，需要的存储空间为O(V+E)
邻接矩阵，表示稠密图，需要的存储空间为O(V^2)
2、广度优先搜索
广度优先搜索是Prim最小生成树算法和Dijkstra单源最短路径算法中的主要思想。广度优先搜索始终将已发现和未发现顶点之间的边界，沿其广度方向向外发展。因此，每一轮向外扩展都将节点分为三个集合：已搜索集合（BLACK）、未搜索集合（WHITE）、边缘集合（GRAY）。在程序中，用队列保存每一轮向外扩展的节点，保证向外扩展的有序性。
伪代码：
BFS(G, s) for each vertex u in V[G] - {s} do color[u] = WHITE d[u] = NAN pi[u] = NIL color[s] = GRAY d[s] = 0 pi[s] = NIL Q = NULL ENQUEUE(Q, s) while Q != NULL do u = DEQUEUE(Q) for each v in Adj[u] //扩展邻接节点 do if color[v] == WHITE then color[v] = GRAY //边缘节点 d[v] = d[u] + 1 pi[v] = u ENQUEUE(Q, v) //边缘节点入队列 color[u] = BLACK
dijkstra单源最短路径
对于一个图，假设有N个节点。
初始化distance[N]数组，保存节点到源点的距离，有直接连接的为边长，没有直接连接的为无穷大；
初始化path[N]数组，保存节点路径的前驱节点；
初始化visited[N]数组，将节点集合划分为以访问和未访问两类
进行N轮迭代：
首先用最近纳入已访问的节点来更新未访问节点的distance，distance[x]+vetex[x,y]<distance[y]?
选取当前未访问节点中distance最小的节点纳入已访问节点，path[x]=前一个纳入的节点
迭代的输出路径，用递归的方法处理正序变倒序的问题。