基本操作

Adjacent(G,x,y)

判断图G是否存在边<x,y>或(x,y),邻接矩阵法的效率更高

无向图

有向图

Neighbors（G，x）

列出图中与结点X相邻的边

无向图

无向图中邻接表法直接搜索这个顶点的边表就可以了，效率比邻接矩阵效率高

有向图

有向图中邻接表法搜索出边很容易，但是搜索入边就很难了，效率不如邻接矩阵法

InsertVertex(G,x)

在图中插入顶点X

DleteVertex(G,x)

从图G中删除顶点X

AddEdge(G,x,y)

若无向边(x,y)或者有向边<x,y>不存在，则向图中添加该边

RemoveEdge(G,x,y)

若无向边(x,y)或者有向边<x,y>存在，则在图G中删除该边

FirstNeighbor(G,x)和NextNeihbor(G,x)

Get_edge_value(G,x,y)和Set_edge_value(G,x,y)

图的遍历

从图中某一顶点出发，按照某一规则，访问所有顶点且仅访问一次

广度优先搜索（BFS）

在无环状结构的情况下，类似与树的层次遍历，通过队列在访问邻接结点，通过辅助数组来标记是否未访问 入队顶点结点1，并且访问，访问之后入队顶点结点中未入队过的邻接结点。（2.3） 出队结点2，入队结点2未入队过的邻接结点（4.5） 出队结点3，入队结点3未入队过的邻接结点（6） 出队顶点4，入队顶点4未入队过的邻接结点（7） 出队5，出队7，他们都没有未入队过的邻接结点。

广搜实现

第一个函数是初始化的过程，第一个for把所有的visited修改为false 然后初始化一个队列，第二个for是找出第一个未被访问过的结点作为顶点开始广度搜索，如果出现有未连通图的情况就会通过这个循环确保能够遍历完每一个元素，第二个函数就是广度优先搜索的算法（BFS）

BFS算法的性能分析

空间复杂度O（v） 时间复杂度：如果是邻接矩阵法则为O(V²)，如果是邻接表法则为O(V+E)

广度优先搜索的应用

无权图单源最短路径问题，广度优先搜索优先访问边最近的结点，所以可以找到初始顶点到每个顶点的最短路径 广度优先生成树

深度优先搜索（DFS）

类似与树的先序遍历

深度优先搜索实现

通过递归栈来是实现

DFS算法的性能分析

空间复杂度O(v) 邻接矩阵时间复杂度为O(V²),邻接表法为O(V+E)

深度优先搜索的应用

深度优先生成树 遍历与连通性的问题 在有向图中没有这个结论

题型

2020：DFS在执行输出语句后立刻退出递归or在退出递归后输出相应结点，会得到逆拓扑有序。