# 图

## 1. Introduction

### 1-2. 术语，第1部分

G的子图G'是一个包含G的顶点和边的子集的（较小的）图。例如，三角形 {0, 1, 2} 是当前显示图的子图。

### 1-3. 术语，第2部分

（无向）图G中（长度为n）的路径是顶点序列{v0，v1，...，vn-1，vn}，使得在vivi+1∀i∈[0..n-1]之间存在边缘。

### 1-4. 术语，第3部分

An undirected graph G is called connected if there is a path between every pair of distinct vertices of G. For example, the currently displayed graph is not a connected graph.

An undirected graph C is called a connected component of the undirected graph G if:
1). C is a subgraph of G;
2). C is connected;
3). no connected subgraph of G has C as a subgraph and contains vertices or edges that are not in C (i.e., C is the maximal subgraph that satisfies the other two criteria).

For example, the currently displayed graph have {0, 1, 2, 3, 4} and {5, 6} as its two connected components.

A cut vertex/bridge is a vertex/edge that increases the graph's number of connected components if deleted. For example, in the currently displayed graph, there is no cut vertex, but edge (5, 6) is a bridge.

### 1-5. 术语，第4部分

In a directed graph, some of the terminologies mentioned earlier have small adjustments.

If we have a directed edge e: (uv), we say that v is adjacent to u but not necessarily in the other direction. For example, 1 is adjacent to 0 but 0 is not adjacent to 1 in the currently displayed directed graph.

In a directed graph, we have to further differentiate the degree of a vertex v into in-degree and out-degree. The in-degree/out-degree is the number of edges coming-into/going-out-from v, respectively. For example, vertex 1 has in-degree/out-degree of 2/1, respectively.

### 1-6. Terminologies, Part 5

In a directed graph, we extend the concept of Connected Component (CC) into Strongly Connected Component (SCC). A directed graph G is called strongly connected if there is a path in each direction between every pair of distinct vertices of G.

A directed graph SCC is called a strongly connected component of the directed graph G if:
1). SCC is a subgraph of G;
2). SCC is strongly connected;
3). no connected subgraph of G has SCC as a subgraph and contains vertices or edges that are not in SCCC (i.e., SCC is the maximal subgraph that satisfies the other two criteria).

In the currently displayed directed graph, we have {0}, {1, 2, 3}, and {4, 5, 6, 7} as its three SCCs.

## 2. 图是普遍的

### 2-3. 示例 - 更难看到

[This is a hidden slide]

## 3. 模式

1. U/U = 无向/不加权,
2. U/W = 无向/加权,
3. D/U = 有向/不加权, and
4. D/W = 有向/加权.

## 6. 特殊图形

### 6-3. 特殊图形 - 树，第3部分

1. 0/1/7/9/4的父节点分别是无/0/1/8/3，
2. 0/1/7的子节点分别是 {1,8}/{2,3,6,7}/无，
3. 4/6/8的祖先分别是 {3,1,0}/{1,0}/{0}，
4. 4和6的最低公共祖先是1。
5. 1/8的后代分别是 {2,3,4,5,6,7}/{9}，
6. 以1为根的子树包括1，它的后代和所有相关的边，
7. 0/1/2/3级成员分别是 {0}/{1,8}/{2,3,6,7,9}/{4,5}，
8. 这个有根树的高度是它的最大层级 = 3。

## 7. 三个图形数据结构

### 7-3. 答案

[This is a hidden slide]

### 7-5. Class IntegerPair (in Java)

`class IntegerPair implements Comparable<IntegerPair> {  Integer _f, _s;  public IntegerPair(Integer f, Integer s) { _f = f; _s = s; }  public int compareTo(IntegerPair o) {    if (!this.first().equals(o.first())) // this.first() != o.first()      return this.first() - o.first();   // is wrong as we want to    else                                 // compare their values,      return this.second() - o.second(); // not their references  }  Integer first() { return _f; }  Integer second() { return _s; }}// IntegerTriple is similar to IntegerPair, just that it has 3 fields `

### 7-8. 答案

[This is a hidden slide]

### 7-11. 答案

[This is a hidden slide]

## 8. 简单应用

1. 计数 V,
2. 计数 E,
3. 枚举顶点u的邻居，
4. 检查边缘（u，v）的存在等。

### 8-1. 将V计数

PS：有时这个数字是存储/维护在一个单独的变量中，这样我们就不必每次都重新计算它 - 特别是如果图形在创建之后永远/很少改变，因此我们有O(1)性能，例如：对于上面显示的示例图，我们可以存储（在我们的AM / AL / EL数据结构中）有7个顶点。

### 8-2. 答案

[This is a hidden slide]

### 8-3. 将 E 计数

In an EL, E is just the number of its rows that can be counted in O(E) or even in O(1) — depending on the actual implementation. Note that depending on the need, we may store a bidirectional edge just once in the EL but on other case, we store both directed edges inside the EL.

In an AL, E can be found by summing the length of all V lists and divide the final answer by 2 (for undirected graph). This requires O(V+E) computation time as each vertex and each edge is only processed once. This can also be implemented in O(V) in some implementations.

Discussion: How to count E if the graph is stored in an AM?

PS: Sometimes this number is stored/maintained in a separate variable for efficiency, e.g., we can store that there are 8 undirected edges (in our AM/AL/EL data structure) for the example graph shown above.

### 8-4. 答案

[This is a hidden slide]

### 8-6. 答案

[This is a hidden slide]

### 8-8. 答案

[This is a hidden slide]

### 8-9. 讨论

Quiz: So, what is the best graph data structure?

It Depends
Edge List

### 8-10. 答案

[This is a hidden slide]

## 9. 附加功能

### 9-4. 讨论

[This is a hidden slide]

### 9-5. Implicit Graph

Last but not least, there are some graphs that are so nicely structured that we do not have to actually store them in any graph data structure that we have discussed earlier.

For example, a complete unweighted graph can be simply stored with just one integer V, i.e., we just need to remember it's size and since a complete graph has an edge between any pair of vertices, we can re-construct all those V * (V-1) / 2 edges easily.

Discussion: Can you elaborate a few more implicit graphs?

### 9-6. More Implicit Graphs

[This is a hidden slide]