图

定义

二元组的定义

一张图G是一个二元组$(V, E)$，其中$V$称为顶点集(Vertices set)，$E$称为边集(Edges set)。$E$的元素是一个二元组数对，用(x, y)表示，其中$x, y \epsilon V$

术语

1. 阶(Order): 图G中顶集V的大小称作图G的阶。

2. 子图(Sub-Graph): 如果$V(G') \subseteq V(G)$，则图$G'$称作图$G$的子图。

3. 生成子图(Spanning Sub-Graph): 指满足条件$V(G')=V(G)$的$G$的子图G'。

4. 度(Degree): 一个顶点的度是指与该顶点相关联的总边数，顶点v的度记作d(v)。度和边有如下关系：$\sum_{v\in V}d(v)=2\left|E\right|$。

5. 出度(Out-degree)和入度(In-degree): 对有向图而言，顶点的度还可分为出度和入度。一个顶点的出度为$d_0$，是指有$d_0$条边以该顶点为起点，或说与该点关联的出边共有$d_0$条。入度的概念也类似。

6. 邻接矩阵(Adjacency matrix)

7. 自环(Loop): 若一条边的两个顶点相同，则此边称作自环。

8. 路径(Path): 从顶点u到顶点v的一条路径是指一个序列$v_0,e_1,v_1,e_2,v_2,...v_k,e_k$，$e_i$的起点终点为$v_{i-1}$及$v_i$；k称作路径的长度；$v_0=u$称为路径的起点；$v_k=v$称为路径的终点。如果u=v，称该路径是闭的，反之则称为开的；如果$v_1,...,v_k$两两不等，则称之为简单路径（Simple path，注意，u=v是允许的）。

9. 行迹(Trace): 如果路径$P(u,v)$中边各不相同，则该路径称为u到v的一条行迹。

10. 轨道(Track): 即简单路径。

11. 闭的行迹称作回路(Circuit)，闭的轨道称作圈(Cycle)。（现存文献中的命名法并无统一标准。比如在另一种定义中，walk对应上述的path，path对应上述的track，trail对应上述的trace。）

12. 距离(Distance): 从顶点u出发到顶点v的最短路径若存在，则此路径的长度称作从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（$\infty$）。

13. 距离矩阵(Distance matrix)

14. 桥(Bridge): 若去掉一条边，便会使得整个图不连通，该边称为桥。

分类

有向图和无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。

简单图

一个图如果

1. 没有两条边，它们所关联的两个点都相同（在有向图中，没有两条边的起点终点都分别相同）；

2. 每条边所关联的是两个不同的顶点

则称为简单图（Simple graph）。简单的有向图和无向图都可以使用以上的“二元组的定义”，但形如$(x,x)$的序对不能属于E。而无向图的边集必须是对称的，即如果$(x,y)\in E$，那么$(y,x)\in E$。

多重图

若允许两结点间的边数多于一条，又允许顶点通过同一条边和自己关联，则为多重图的概念。它只能用“三元组的定义”。

重要类型

1. 补图

2. 树状图

3. 平面图

4. 连通图

   1. 强连通图

   2. 强连通分量

5. 有向无环图

   1. AOV网

   2. AOE网

6. 完全图：每一对不同顶点间都有边相连的的图，记作$K_n$。

7. 二分图：顶集$V=X\cup Y(X\cap Y=\phi$，且每一条边都有一个顶点在$X$中，而另一个顶点在$Y$中。

   1. 完全二分图：二分图$G$中若任意两个$X$和$Y$中的顶点都有边相连。若$\left|X\right|=m,\left|Y\right|=n$，则图$G$记作$K_{m,n}$。

8. 正则图：如果图中所有顶点的度皆相等，则此图称为正则图

9. 欧拉图:存在经过所有边一次（可以多次经过点）的路径的图

10. 哈密顿图:存在经过所有点一次的路径的图

11. 加权图（weighted graph）：一个加权图在图中的每条边上给出一个值（权重）

存储

遍历

1. 深度优先遍历

2. 广度优先遍历

深度优先遍历

树的先序遍历的推广，它的基本思想是：从图$G$的某个顶点$v_0$出发，访问$v_0$，然后选择一个与$v_0$相邻且没被访问过的顶点$v_i$访问，再从$v_i$出发选择一个与$v_i$相邻且未被访问的顶点$v_j$进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点$w$，从$w$出发按同样的方法向前遍历，直到图中所有顶点都被访问。

Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组
Status (*VisitFunc)(int v); // VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)) {
    VisitFunc = Visit;
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE; // 访问标志数组初始化
    for (v = 0; v < G.vexnum; ++v)
        if (!visited[v])
            DFS(G, v);  // 对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v) { // 从第v个顶点出发递归地深度优先遍历图G
    visited[v] = TRUE;
    VisitFunc(v);   // 访问第v个顶点
    for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w))
        // FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
        // 若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
        // 若w是v的最后一个邻接点，则返回空（0）。
        if (!visited[w])
            DFS(G, w);  // 对v的尚未访问的邻接顶点w调用DFS
}

广度优先遍历

是树的层次遍历的推广，它的基本思想是：首先访问初始点$v_i$，并将其标记为已访问过，接着访问$v_i$的所有未被访问过的邻接点$vi1,vi2,…, vi t$，并均标记已访问过，然后再按照$vi1,vi2,…, vi t$的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

Boolean visited[ MAX_VERTEX_NUM ]; // 访问标志数组
Status (* VisitFunc)(int v); // VisitFunc是访问函数，对图的每个顶点调用该函数

void BFSTraverse(Graph G, Status(* Visit)(int v)) {
    VisitFunc = Visit;
    for (v = 0; v < G.vexnum; ++v)
        visited[v] = FALSE;
    initQueue(Q); // 置空辅助队列Q
    for (v = 0; v < G.vexnum; ++v) {
        if (!visited[v]) {
            visited[v] = TRUE;
            VisitFunc(v);
            EnQueue(Q, v); // v入队列
            while (!QueueEmpty(Q)) {
                DeQueue(Q, u); // 队头元素出队并置为u
                for (w = FirstAdjVex(G, u);
                        w >= 0; w = NextAdjVex(G, u, w))
                    if (!Visited[w]) { // w为u的尚未访问的邻接顶点
                        Visited[w] = TRUE;
                        VisitFunc(w);
                        EnQueue(Q, w);
                    }
            }
        }
    }
}

算法

单源最短路径问题

拓扑排序

最小生成树

题型

1. 克隆图

2. 课程表

3. 网络延迟问题

4. 除法求值

5. 最小高度树

6. 重新安排行程

7. 冗余连接

参考

1. 图（数学）

2. 图高频面试题