graph traversal is a exhaustive search
- 图遍历的两种方法
depth-first
breadth-first search
4.1 定义
7-3 some concepts
Undirected Graph：Edges do not have directions associated with them 无向图
Directed Graph：Each edge has an associated direction 有向图
Connected Graph：Each node is reachable from all others by following edges. 所有节点都可以连接起来，没有独立节点，或多个子部分
Not Connected Graph：with 2 Components
7-8 有向图
7-9 无向图
Degree of a node v：连接v的边
In-degree of v: 指向v的边
Out-degree of v:指出v的边
path: 是一串节点数列，每个节点属于V(v0,v1,...,vk from V)，每个相邻节点的边属于E.((vi,vi+1) ∈ E).路程的长度为k，是使用节点数减一
A simple path：路程没有经过相同的节点
A cycle：是 a path，其开始和结束节点相同，并且不遍历相同的边。
Weighted Graphs：每条边都有权重
Dense Graph：相对于节点的数量有很多边
Sparse Graph：相对于节点的数量有很少的边
Cyclic：有cycle
Acyclic: 没有cycle
Directed Acyclic Graph(a dag)
A rooted tree: 是一个树，有 一个被标识为特殊的节点(根节点)。其他所有节点都可以从根节点到达。当根被删除时，一组根(子)树仍然存在。
- 两种相邻边的表达方式
Adjacency Matrix：对于无向图来说，相邻表对称。适用于Dense Graph
Adjacency List：链表数组，红色为数组(从0开始)，黄色为链表。适用于Sparse Graph
7-23
4.2 遍历方法
当我们想要写“mark v with count“时会实现“mark[v] := count”
8-27 DFS
8-83 BFS
8-2 DFS：a b d f e c g h BFS：a b c d e f g h
depth-first search(DFS):从深度访问当前节点的邻居，当没有深度邻居时，原路返回（当回溯时，我们返回到最近访问的节点，该节点仍然有未访问的邻居。这是通过在访问每个节点时将其压入堆栈来模拟的。然后，回溯对应于取出堆栈）。用stack存储，先进后出
breadth-first search(BFS)：遍历一个节点后遍历其所有的邻居节点，直至没有邻居节点在向下一层遍历。用queue存储，先进先出
8-52 第一个数字代表写入stack的顺序，第二个数字代表移出stack的顺序
总结
1.DFS和BFS都可以用于有向图和无向图
2.时间复杂度取决于图相邻节点的表达方式如果是adjacency matrix，复杂度为 Θ(|V|^2),遍历相邻表的每一个节点，如果是 adjacency lists，复杂度是 Θ(|V| + |E|)，，其节点遍历V，遍历每个节点的边总和为E。
3.DFS用stack存储，先进后出；BFS用queue存储，先进先出。
4.DFS用back edge来表示非tree edge；BFS用cross edge来表示非tree edge
4.3Topological Sorting(top-sort problem)
The graph must be a dag(Directed Acyclic Graph),有顺序，有步骤的题，例如装修房子，刷墙这道工序被认为是要首先完成的，完成后才能进行一下步。
- 两种解决方法
1.执行DFS并注意节点从堆栈中弹出的顺序。按照与此相反的顺序列出节点。
2.在图中找一个源（其没有入度只有出度），列出它并将其和其相关的边从图中移出，重复此步骤。采用了decrease-and-conquer方法
