1）.熟悉图的各种存储方法。 2）.掌握遍历图的递归和非递归的算法。 3）.理解图的有关算法。

1. 图的各种存储方法
- 邻接矩阵：用一个二维数组表示图中各个顶点之间的关系，矩阵中的元素表示顶点之间是否有边相连，适用于稠密图。
- 邻接表：用一个数组表示图中各个顶点，数组中的每个元素是一个链表，表示该顶点所连接的其他顶点，适用于稀疏图。
- 十字链表：由两个链表构成，分别表示正向边和反向边，适用于有向图。
- 邻接多重表：每个顶点用一个结构体存储，结构体中有两个指针分别指向与该顶点相连的边和下一个顶点，适用于无向图。

2. 遍历图的递归和非递归的算法
- 深度优先遍历（DFS）：从一个顶点开始，访问它的一个未被访问过的邻接点，然后递归地访问该邻接点的邻接点，直到所有与该顶点有路径相连的顶点都被访问过为止。
- 广度优先遍历（BFS）：从一个顶点开始，先访问它的所有未被访问过的邻接点，然后按照宽度优先的顺序逐层访问与该顶点有路径相连的其他顶点。

递归实现深度优先遍历的代码：

visited = [False] * n  # 标记每个顶点是否被访问过

def dfs(v, adj_list):
    visited[v] = True  # 标记当前顶点为已访问
    print(v)  # 输出当前顶点
    for u in adj_list[v]:  # 遍历当前顶点的邻接点
        if not visited[u]:  # 如果邻接点未被访问，则递归访问
            dfs(u, adj_list)

非递归实现深度优先遍历的代码：

visited = [False] * n  # 标记每个顶点是否被访问过

def dfs(v, adj_list):
    stack = [v]  # 使用栈来实现非递归遍历
    while stack:
        u = stack.pop()  # 取出栈顶元素
        if not visited[u]:
            visited[u] = True  # 标记当前顶点为已访问
            print(u)  # 输出当前顶点
            for w in adj_list[u]:  # 将未访问过的邻接点入栈
                if not visited[w]:
                    stack.append(w)

广度优先遍历的代码：

visited = [False] * n  # 标记每个顶点是否被访问过

def bfs(v, adj_list):
    queue = [v]  # 使用队列来实现广度优先遍历
    visited[v] = True  # 标记当前顶点为已访问
    while queue:
        u = queue.pop(0)  # 取出队首元素
        print(u)  # 输出当前顶点
        for w in adj_list[u]:  # 将未访问过的邻接点入队
            if not visited[w]:
                visited[w] = True
                queue.append(w)

3. 图的有关算法
- 最短路径算法：Dijkstra算法、Bellman-Ford算法、Floyd算法等，用于求解图中两个顶点之间的最短路径。
- 最小生成树算法：Prim算法、Kruskal算法等，用于求解图的最小生成树。
- 拓扑排序算法：用于有向无环图中对顶点进行排序，保证每个顶点的前驱都排在它的后面。
- 强连通分量算法：Tarjan算法、Kosaraju算法等，用于将图分解为强连通分量。
- 欧拉回路算法：用于求解无向图中的欧拉回路。
- 哈密顿回路算法：用于求解有向图或无向图中的哈密顿回路。