P4-

• 连通图、有向图、计算出度入度

有向图的定义

• If the edges are directed, the graph is said to be a directed graph. + 画图举例

无向图的定义

• An undirected graph is a graph that is not directed. + 画图解释

入度 indegree

• The indegree of vertex v is the number of edges that ends in v.
• P6 有例子

P7.Path

• A path in a graph is a sequence of vertices
• A simple path(简单路径) is a path that does not contains same vertex more than once(except for the first and last vertices, which may be the same).
• The length of a path is the number of edges in a path.

P8.Cycle in directed graph

• 回路存在即不能进行拓扑排序
• A cycle is a path of length at least one, and it starts and ends in the same vertex.

DAG

• a directed graph contains no cycles

P10.Connected undirected graph

• 概念判断、什么是强连通图、连通图、判断这个图是不是强连通的、判断是不是完全图
• 完全的无向图里面的边数的关系

连通图(针对无向图而言的)

• A connected graph is an undirected graph where is at least one path between each pair of vertices.

强连通图(针对有向图而言的)

• A strongly connected graph is a directed graph where is at least one path between each pair of vertices.

弱连通图(针对有向图而言)

• A directed graph is a weakly connected graph that is not strongly connected, but its underlaying graph is an undirected that is connected.

完全图(注意，此处是edge)

• A complete graph is a graph where there is an edge between each pair of vertices.

P15.Tree

什么是树、判断是不是树
什么是树

• 两种定义方式
  • A tree is an undirected graph where each pair of vertices is connected by exactly one path.
  • A tree connected with n vertices and n-1 edges.

判断是不是树🎄

• A directed tree is a directed graph which would be a tree if the
  directions on the edges were ignored.（有向树不算树）

P18.Graph representation

• 图的两种存储方式、把选择的那一种画出来
• 各自的优缺点
  • 矩阵索引快，但是空间消耗大（存储较多无用的值0）
  • 链表查找慢，但是节省空间，没有无效存储

• There are two different ways to represent graphs:
  • Adjacency matrix(还可细分为有向，无向，带权，带权的把1改成对应权值即可)
    • Space requirement:
  • Adjacency list P.22 具体是怎么样的要会画
    • Space requirement:
      Which of the representations that is best depends on the density of the network.
  • Adjacency matrix is best if the graph is dense(|E|约等于)
  • Adjacency list is best if the graph is sparse(E<)

The Shortest Path Problem

• 算法要求
  • 无环
  • 有向
• Dijkstra's algorithm

P29.Spanning Tree

• A spanning tree of a graph is a subgraph of that graph, which:
  • Is a tree
  • connects to all vertices(如果是树，不是已经满足这个条件了吗？)

P30.MST最小生成树

根据这两个算法、画出MST、会画就可以了

Kruskal's algorithm

在不构成环的情况下，依次选择最短边。

Prim's algorithm

首先任意选择一个节点放入集合V，在不构成环的情况下，选择与这个集合中的点形成最短边的那个点。

P35.Topological ordering

• 找出拓扑排序、并且解释为什么不能有环、彼此是彼此的依赖结点

• A topological ordering of a DAG is an ordering of vertices such that if there is an edge(u, v) between u and v, then u comes before v in the ordering.

怎么求拓扑排序

1. 求各个点的入度
2. 将入度为0加入列表（顺序）
3. 循环1.2，直到求完所有点

P42有例子