6.1 图的基本概念

图的基本概念.pdf

定义

图：图 $G$ 由顶点集 $V$ 和边集 $E$ 组成，记为 $G = (V, E)$ ，其中 $V (G)$ 表示图 $G$ 中顶点的有限非空集； $E (G)$ 表示图 $G$ 中顶点之间的关系（边）集合。若 $V = {v_{1}, v_{2}, \dots, v_{n}}$ ，则用 $∣ V ∣$ 表示图 $G$ 中顶点的个数，也称图 $G$ 的阶； $E = {(u, v) ∣ u \in V, v \in V}$ ，用 $∣ E ∣$ 表示图 G 中边的条数。
- 注意：线性表可以是空表，树可以是空树，但图不可以是空图，即 $V$ 一定是非空集，当然 $E$ 可以是空集
无向图：若 $E$ 是无向边（也称边）的有限集合时，则图 $G$ 为无向图。边是顶点的无序对，记为 $(v, w)$ 或 $(w, v)$ ，其中 $v, w$ 是顶点。可以说顶点 $w$ 和顶点 $v$ 互为邻接点，边 $(v, w)$ 依附于顶点 $w$ 和 $v$ ；或者说边 $(v, w)$ 和顶点 $v, w$ 相关联。
有向图：若 $E$ 是有向边（也称弧）的有限集合时，则图 $G$ 为有向图。弧是顶点的有序对，记为 <v,w>，其中 $v, w$ 是顶点， $v$ 称为弧尾， $w$ 称为弧头，称为从顶点 $v$ 到顶点 $w$ 的弧，也称 $v$ 邻接到 $w$ ，或 $w$ 邻接自 $v$ 。<v,w> $\neq =$ <w,v>。
简单图：不存在重复边；不存在顶点到自身的边。（只讨论简单图）
多重图：图 $G$ 某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 $G$ 为多重图。

度、入度、出度

对于无向图，顶点 $v$ 的度是指依附于该顶点的边的条数，记为 $T D (v)$
- 在具有 $n$ 个顶点、 $e$ 条边的无向图中 $i = 1 \sum n T D (v_{i}) = 2 e$
对于有向图
- 入度是以顶点 $v$ 为终点的有向边的数目，记为 $I D (v)$
- 出度是以顶点 $v$ 为起点的有向边的数目，记为 $O D (v)$
- 顶点 $v$ 的度等于其入度和出度之和，即 $T D (v) = I D (v) + O D (v)$
- 在具有 $n$ 个顶点、 $e$ 条边的有向图中 $i = 1 \sum n I D (v_{i}) = i = 1 \sum n O D (v_{i}) = e$

顶点与顶点的关系

路径：顶点 $v_{p}$ 到顶点 $v_{q}$ 之间的一条路径是指顶点序列 $v_{p}, v_{i 1}, v_{i 2}, \dots, v_{i_{m}}, v_{q}$
- 有向图的路径也是有向的
- 顶点之间有可能不存在路径
回路：第一个顶点和最后一个顶点相同的路径称为回路或环。
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度：路径上边的数目。
点到点的距离：从顶点 $u$ 出发到顶点 $v$ 的最短路径若存在，则此路径的长度称为从 $u$ 到 $v$ 的距离。若从 $u$ 到 $v$ 根本不存在路径，则记该距离为无穷（ $\infty$ ）。
连通：无向图中，若从顶点 $v$ 到顶点 $w$ 有路径存在，则称 $v$ 和 $w$ 是连通的。
强连通：有向图中，若从顶点 $v$ 到顶点 $w$ 和从顶点 $w$ 到顶点 $v$ 之间都有路径，则称这两个顶点是强连通的。
连通图：若图 $G$ 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图
- 对于 $n$ 个顶点的无向图 $G$ ，若 $G$ 是连通图，则最少有 $n - 1$ 条边；若 $G$ 是非连通图，则最多可能有 $C_{n - 1}^{2}$ 条边
强连通图：若图 $G$ 中任意两个顶点都是强连通的，则称图 G 为强连通图
- 对于 $n$ 个顶点的有向图 $G$ ，若 $G$ 是强连通图，则最少有 $n$ 条边

图的局部

子图：设有两个图 $G = (V, E)$ 和 $G^{'} = (V^{'}, E^{'})$ ，若 $V^{'}$ 是 $V$ 的子集，且 $E^{'}$ 是 $E$ 的子集，则称 $G^{'}$ 是 $G$ 的子图
生成子图：若有满足 $V (G^{'}) = V (G)$ 的子图 $G^{'}$ ，则称其为 $G$ 的生成子图
连通分量：无向图中的极大连通子图称为连通分量，其必须连通且包含尽可能多的顶点和边
强连通分量：有向图中的极大强连通子图称为有向图的强连通分量，其必须强连通且包含尽可能多的边
生成树：连通图的生成树是包含图中的一个极小连通子图，边要尽可能的少但要保持连通
生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林

权

边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值
带权图：边上带有权值的图称为带权图，也称网
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

几种特殊性态的图

无向完全图：无向图中任意两个顶点之间都存在边。若无向图的顶点数 $∣ V ∣ = n$ ，则 $∣ E ∣ \in [0, C_{n}^{2}] = [0, \frac{n ( n - 1 )}{2}]$
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧。若有向图的顶点数 $∣ V ∣ = n$ ，则 $∣ E ∣ \in [0, 2 C_{n}^{2}] = [0, n (n -1)]$ 。
稀疏图、稠密图：边数很少的图称为稀疏图，反之称为稠密图。没有绝对界限，一般来说 $∣ E ∣ < ∣ V ∣ lo g ∣ V ∣$ 时，可以将 $G$ 视为稀疏图
树、森林
- 注意树不一定是图，因为树可以是空树但图不可以是空图
有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图

6.1.2 本节习题精选

选择题：题目、答案

综合题：题目、答案

6.2 图的存储

6.2.1 邻接矩阵法

邻接矩阵法.pdf

邻接矩阵：用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点关系的二维数组称为邻接矩阵。对于一个确定的图，邻接矩阵唯一

邻接矩阵性能分析

空间复杂度： $O (∣ V ∣^{2})$ ，只和顶点数相关，和实际的边数无关。
适合用于存储稠密图。
无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区或者下三角区）。

邻接矩阵的性质：设图 G 的邻接矩阵为 $A$ （矩阵元素为 0 或 1），则 $A^{n}$ 的元素 $A^{n} [i] [j]$ 等于由顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目。如下图中邻接矩阵

A = 0100101101010110

A^{2} = 1011031111211112

， $A^{3} = A^{1} \cdot A^{2} = 0311324414231432$ ， $A^{3}$ 中 $a_{14} = 0 \cdot 1 + 1 \cdot 1 + 0 \cdot 1 + 0 \cdot 1 = 1$ 代表从 $A$ 到 $D$ 长度为3的路径只有1条，表达式中第一项 $0 \cdot 1 = 0$ 表示从A到A长度为1的路径有0条，从A到D长度为2的路径有1条，无法组合成从A到D长度为3的路径，第二项 $1 \cdot 1 = 1$ 表示从A到B长度为1的路径有1条，从B到C长度为2的路径有1条，可以组成和从A到C长度为3的路径1条。

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-},
	]
	\node [below] at(0,-1) (A) {A};
	\node [below=of A] (C) {C};
	\node [left=of A] (B) {B};
	\node [below=of B] (D) {D};
 
	\draw[arrow] (A)--(B);
	\draw[arrow] (C)--(B);
	\draw[arrow] (D)--(C);
	\draw[arrow] (D)--(B);
 
	\matrix[ampersand replacement=\&][below, rectangle, draw=none] at(5,0) {
		\& \node(species2) [rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\setlength{\extrarowheight}{1em}
		\begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}}
			A & B & C & D \\
		\end{tabular}
		};\\
		\node(species3) [shape=rectangle, draw=none] {
			\begin{tabular}{c}
			A \\
			B \\
			C \\
			D \\
			\end{tabular}
		}; \&
		\node(species4) [shape=rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|}
			\hline
			0 & 1 & 0 & 0\\ \hline
			1 & 0 & 1 & 1\\ \hline
			0 & 1 & 0 & 1\\ \hline
			0 & 1 & 1 & 0\\ \hline
		\end{tabular}
		};\\
	};
	\end{tikzpicture}
\end{document}

邻接矩阵存储无权图

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-},
	]
	\node [below] at(0,-1) (A) {A};
	\node [below=of A] (C) {C};
	\node [left=of C] (B) {B};
	\node [right=of C] (D) {D};
	\node [below left=of C, xshift=2em, yshift=-1em] (E) {E};
	\node [below right=of C, xshift=-2em, yshift=-1em] (F) {F};
 
	\draw[arrow] (A)--(B);
	\draw[arrow] (C)--(A);
	\draw[arrow] (D)--(A);
	\draw[arrow] (E)--(B);
	\draw[arrow] (E)--(C);
	\draw[arrow] (F)--(B);
	\draw[arrow] (F)--(D);
 
	\matrix[ampersand replacement=\&][below, rectangle, draw=none] at(10,0) {
		\& \node(species2) [rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\setlength{\extrarowheight}{1em}
		\begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}}
			A & B & C & D & E & F \\
		\end{tabular}
		};\\
		\node(species3) [shape=rectangle, draw=none] {
			\begin{tabular}{c}
			A \\
			B \\
			C \\
			D \\
			E \\
			F \\
			\end{tabular}
		}; \&
		\node(species4) [shape=rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|}
			\hline
			0 & 1 & 1 & 1 & 0 & 0 \\ \hline
			1 & 0 & 0 & 0 & 1 & 1 \\ \hline
			1 & 0 & 0 & 0 & 1 & 0 \\ \hline
			1 & 0 & 0 & 0 & 0 & 1 \\ \hline
			0 & 1 & 1 & 0 & 0 & 0 \\ \hline
			0 & 1 & 0 & 1 & 0 & 0 \\ \hline
		\end{tabular}
		};\\
	};
	\end{tikzpicture}
\end{document}

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-latex},
	]
	\node [below] at(0,-1) (A) {A};
	\node [below=of A] (C) {C};
	\node [left=of C] (B) {B};
	\node [right=of C] (D) {D};
	\node [below left=of C, xshift=2em, yshift=-1em] (E) {E};
	\node [below right=of C, xshift=-2em, yshift=-1em] (F) {F};
 
	\draw[arrow] (A)--(B);
	\draw[arrow] (C)--(A);
	\draw[arrow] (D)--(A);
	\draw[arrow] (E)--(B);
	\draw[arrow] (E)--(C);
	\draw[arrow] (F)--(B);
	\draw[arrow] (F)--(D);
 
	\matrix[ampersand replacement=\&][below, rectangle, draw=none] at(10,0) {
		\& \node(species2) [rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\setlength{\extrarowheight}{1em}
		\begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}}
			A & B & C & D & E & F \\
		\end{tabular}
		};\\
		\node(species3) [shape=rectangle, draw=none] {
			\begin{tabular}{c}
			A \\
			B \\
			C \\
			D \\
			E \\
			F \\
			\end{tabular}
		}; \&
		\node(species4) [shape=rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|}
			\hline
			0 & 1 & 0 & 0 & 0 & 0 \\ \hline
			0 & 0 & 0 & 0 & 0 & 0 \\ \hline
			1 & 0 & 0 & 0 & 0 & 0 \\ \hline
			1 & 0 & 0 & 0 & 0 & 0 \\ \hline
			0 & 1 & 1 & 0 & 0 & 0 \\ \hline
			0 & 1 & 0 & 1 & 0 & 0 \\ \hline
		\end{tabular}
		};\\
	};
	\end{tikzpicture}
\end{document}

结点数为 $n$ 的图 $G = (V, E)$ 的邻接矩阵 $A$ 是 $n \times n$ 的，将G的顶点编号为 $v_{1}, v_{2}, \dots, v_{n}$ ，则

A [i] [j] = {1, 0, 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 是 E (G) 中的边 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 不是 E (G) 中的边

#define MaxVertexNum 100	//顶点数目的最大值
 
typedef struct{
	char Vex[MaxVertexNum];	//一位数组，顶点表
	int Edge[MaxVertexNum][MaxVertexNum];	//二维数组，邻接矩阵，边表
	//此处也可以换为bool类型或枚举类型
	int vexnum,arcnum;	//图的顶点数和边数
}MGraph;

无向图度：第 $i$ 个结点的度 = 第 $i$ 行（或第 $i$ 列）的非零元素个数
有向图度：第 $i$ 个结点的度 = 第 $i$ 行、第 $i$ 列的非零元素个数之和
出度：第 $i$ 行的非零元素个数
入度：第 $i$ 列的非零元素个数
邻接矩阵法求顶点的度、入度、出度的时间复杂度为 $O (∣ V ∣)$

邻接矩阵法存储带权图

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-},
	]
	\node [below] at(0,-1) (A) {A};
	\node [below=of A] (C) {C};
	\node [left=of C] (B) {B};
	\node [right=of C] (D) {D};
	\node [below left=of C, xshift=2em, yshift=-1em] (E) {E};
	\node [below right=of C, xshift=-2em, yshift=-1em] (F) {F};
 
	\draw[arrow] (A)--(B)node[midway, above, font=\large, draw=none]{5};
	\draw[arrow] (C)--(A)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (D)--(A)node[midway, above, font=\large, draw=none]{6};
	\draw[arrow] (E)--(B)node[midway, below, font=\large, draw=none]{3};
	\draw[arrow] (E)--(C)node[midway, above, font=\large, draw=none]{3};
	\draw[arrow] (F)--(B)node[midway, below, font=\large, draw=none]{4};
	\draw[arrow] (F)--(D)node[midway, above, font=\large, draw=none]{2};
 
	\matrix[ampersand replacement=\&][below, rectangle, draw=none] at(10,0) {
		\& \node(species2) [rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\setlength{\extrarowheight}{1em}
		\begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}}
			A & B & C & D & E & F \\
		\end{tabular}
		};\\
		\node(species3) [shape=rectangle, draw=none] {
			\begin{tabular}{c}
			A \\
			B \\
			C \\
			D \\
			E \\
			F \\
			\end{tabular}
		}; \&
		\node(species4) [shape=rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|}
			\hline
			0 & 5 & 1 & 6 & $\infty$ & $\infty$ \\ \hline
			5 & 0 & $\infty$ & $\infty$ & 3 & 4 \\ \hline
			1 & $\infty$ & 0 & $\infty$ & 3 & $\infty$ \\ \hline
			6 & $\infty$ & $\infty$ & 0 & $\infty$ & 2 \\ \hline
			$\infty$ & 3 & 3 & $\infty$ & 0 & $\infty$ \\ \hline
			$\infty$ & 4 & $\infty$ & 2 & $\infty$ & 0 \\ \hline
		\end{tabular}
		};\\
	};
	\end{tikzpicture}
\end{document}

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-latex},
	]
	\node [below] at(0,-1) (A) {A};
	\node [below=of A] (C) {C};
	\node [left=of C] (B) {B};
	\node [right=of C] (D) {D};
	\node [below left=of C, xshift=2em, yshift=-1em] (E) {E};
	\node [below right=of C, xshift=-2em, yshift=-1em] (F) {F};
 
	\draw[arrow] (A)--(B)node[midway, above, font=\large, draw=none]{5};
	\draw[arrow] (C)--(A)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (D)--(A)node[midway, above, font=\large, draw=none]{6};
	\draw[arrow] (E)--(B)node[midway, below, font=\large, draw=none]{3};
	\draw[arrow] (E)--(C)node[midway, above, font=\large, draw=none]{3};
	\draw[arrow] (F)--(B)node[midway, below, font=\large, draw=none]{4};
	\draw[arrow] (F)--(D)node[midway, above, font=\large, draw=none]{2};
 
	\matrix[ampersand replacement=\&][below, rectangle, draw=none] at(10,0) {
		\& \node(species2) [rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\setlength{\extrarowheight}{1em}
		\begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}}
			A & B & C & D & E & F \\
		\end{tabular}
		};\\
		\node(species3) [shape=rectangle, draw=none] {
			\begin{tabular}{c}
			A \\
			B \\
			C \\
			D \\
			E \\
			F \\
			\end{tabular}
		}; \&
		\node(species4) [shape=rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|}
			\hline
			0 & 5 & $\infty$ & $\infty$ & $\infty$ & $\infty$ \\ \hline
			$\infty$ & 0 & $\infty$ & $\infty$ & $\infty$ & $\infty$ \\ \hline
			1 & $\infty$ & 0 & $\infty$ & $\infty$ & $\infty$ \\ \hline
			6 & $\infty$ & $\infty$ & 0 & $\infty$ & $\infty$ \\ \hline
			$\infty$ & 3 & 3 & $\infty$ & 0 & $\infty$ \\ \hline
			$\infty$ & 4 & $\infty$ & 2 & $\infty$ & 0 \\ \hline
		\end{tabular}
		};\\
	};
	\end{tikzpicture}
\end{document}

对于带权图，若顶点之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，即

A [i] [j] = ⎩ ⎨ ⎧ w_{ij}, 0, \infty, 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 是 E (G) 中的边 i = j 时 若 (v_{i}, v_{j}) 或 < v_{i}, v_{j} > 不是 E (G) 中的边

#define MaxVertexNum 100	//顶点数目的最大值
#define INFINITY 2147483647;	//表示“无穷”
 
typedef char VertexType;	//顶点数据类型
typedef int EdgeType;	//边数据类型
 
typedef struct{
	VertexType Vex[MaxVertexNum];	//顶点表
	EdgeType Edge[MaxVertexNum][MaxVertexNum];	//边的权值
	int vexnum, arcnum;	//图的当前顶点数和弧数
}MGraph;

6.2.2 邻接表

当一个图为稀疏图时，使用邻接矩阵存储会浪费大量的存储空间

邻接表存储存储无向图、有向图

邻接表法.pdf

邻接表是指对图 $G$ 中的每个顶点 $v_{i}$ 建立一个单链表，第 $i$ 个单链表中的结点表示依附于顶点 $v_{i}$ 的边（对于有向图是以顶点 $v_{i}$ 为尾的弧）。对于一个确定的图，邻接表并不唯一

顺序存储+链式存储，可类比树的孩子表示法

\usetikzlibrary{positioning}
\newcommand{\drawEdges}[3]{
	\pgfmathsetmacro{\idx}{#1}
	\def\edges{#2}% 边
	\def\values{#3}% 边权值
	\foreach \edge [count=\i] in \edges {
		\ifnum\edge=-1
			\node[draw=none, font=\LARGE] at(\i*4, -\idx) (temp){NULL};
		\else
			\node[fill=gray!20, minimum width=1cm, minimum height=2em] at(\i*4, -\idx) (temp){\edge};
			\node[minimum width=1cm, minimum height=2em] at(\i*4+2, -\idx) (\idx-\i){};
		\fi
		\pgfmathtruncatemacro{\pre}{\i-1}
		\draw[-latex] (\idx-\pre.center) -- (temp);
	}
	\foreach \value[count=\i] in \values{
		\node[minimum width=1cm, minimum height=2em] at(\i*4+1, -\idx) {\value};
	}
}
 
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-},
	]
	\node [below] at(0,-1) (A) {A};
	\node [below=of A] (C) {C};
	\node [left=of C] (B) {B};
	\node [right=of C] (D) {D};
	\node [below left=of C, xshift=2em, yshift=-1em] (E) {E};
	\node [below right=of C, xshift=-2em, yshift=-1em] (F) {F};
 
	\draw[arrow] (A)--(B)node[midway, above, font=\large, draw=none]{5};
	\draw[arrow] (C)--(A)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (D)--(A)node[midway, above, font=\large, draw=none]{6};
	\draw[arrow] (E)--(B)node[midway, below, font=\large, draw=none]{3};
	\draw[arrow] (E)--(C)node[midway, above, font=\large, draw=none]{3};
	\draw[arrow] (F)--(B)node[midway, below, font=\large, draw=none]{4};
	\draw[arrow] (F)--(D)node[midway, above, font=\large, draw=none]{2};
	\end{tikzpicture}
	\begin{tikzpicture}[scale=1, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[draw=none, font=\large] at(0,1){data};
		\node[draw=none, font=\large] at(1,1){first};
 
		\def\myChar{A,B,C,D,E,F}
		\foreach \char [count=\i] in \myChar {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node at (0,-\idx) (node-\idx){\char};
			\node[font=\Large, draw=none, left of = node-\idx] {\idx};
			\node at (1,-\idx) [minimum width=1cm] (\idx-0){};
		}
 
		\drawEdges{0}{1,2,3,-1}{5,1,6};
		\drawEdges{1}{0,4,5,-1}{5,3,4};
		\drawEdges{2}{0,4,-1}{1,3};
		\drawEdges{3}{0,5,-1}{6,2};
		\drawEdges{4}{1,2,-1}{3,3};
		\drawEdges{5}{1,3,-1}{4,2};
	\end{tikzpicture}
\end{document}

\usetikzlibrary{positioning}
\newcommand{\drawEdges}[3]{
	\pgfmathsetmacro{\idx}{#1}
	\def\edges{#2}% 边
	\def\values{#3}% 边权值
	\foreach \edge [count=\i] in \edges {
		\ifnum\edge=-1
			\node[draw=none, font=\LARGE] at(\i*4, -\idx) (temp){NULL};
		\else
			\node[fill=gray!20, minimum width=1cm, minimum height=2em] at(\i*4, -\idx) (temp){\edge};
			\node[minimum width=1cm, minimum height=2em] at(\i*4+2, -\idx) (\idx-\i){};
		\fi
		\pgfmathtruncatemacro{\pre}{\i-1}
		\draw[-latex] (\idx-\pre.center) -- (temp);
	}
	\foreach \value[count=\i] in \values{
		\node[minimum width=1cm, minimum height=2em] at(\i*4+1, -\idx) {\value};
	}
}
 
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-latex},
	]
	\node [below] at(0,-1) (A) {A};
	\node [below=of A] (C) {C};
	\node [left=of C] (B) {B};
	\node [right=of C] (D) {D};
	\node [below left=of C, xshift=2em, yshift=-1em] (E) {E};
	\node [below right=of C, xshift=-2em, yshift=-1em] (F) {F};
 
	\draw[arrow] (A)--(B)node[midway, above, font=\large, draw=none]{5};
	\draw[arrow] (C)--(A)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (D)--(A)node[midway, above, font=\large, draw=none]{6};
	\draw[arrow] (E)--(B)node[midway, below, font=\large, draw=none]{3};
	\draw[arrow] (E)--(C)node[midway, above, font=\large, draw=none]{3};
	\draw[arrow] (F)--(B)node[midway, below, font=\large, draw=none]{4};
	\draw[arrow] (F)--(D)node[midway, above, font=\large, draw=none]{2};
	\end{tikzpicture}
	\begin{tikzpicture}[scale=1, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm]
		\node[draw=none, font=\large] at(0,1){data};
		\node[draw=none, font=\large] at(1,1){first};
 
		\def\myChar{A,B,C,D,E,F}
		\foreach \char [count=\i] in \myChar {
			\pgfmathtruncatemacro{\idx}{\i-1};%整数结果
			\node at (0,-\idx) (node-\idx){\char};
			\node[font=\Large, draw=none, left of = node-\idx] {\idx};
			\node at (1,-\idx) [minimum width=1cm] (\idx-0){};
		}
 
		\drawEdges{0}{1,-1}{5};
		\drawEdges{1}{-1}{};
		\drawEdges{2}{0,-1}{1};
		\drawEdges{3}{0,-1}{6};
		\drawEdges{4}{1,2,-1}{3,3};
		\drawEdges{5}{1,3,-1}{4,2};
	\end{tikzpicture}
\end{document}

无向图中，边结点的数量是 $2∣ E ∣$ ，整体空间复杂度为 $O (∣ V ∣ + 2∣ E ∣)$
有向图中，边结点的数量是 $∣ E ∣$ ，整体空间复杂度为 $O (∣ V ∣ + ∣ E ∣)$

求度、入度、出度

无向图求度：遍历这个顶点相关的边链表
有向图求出度：遍历这个顶点相关的边链表
有向图求入度：遍历所有顶点边链表（邻接表缺点）

在邻接表中存在两种结点：顶点表结点和边表结点

顶点表结点由顶点域 data 和指向第一条邻接边的指针 firstarc 构成
边表结点由邻接点域 adjvex 和指向下一条邻接边的指针域 nextarc 构成

#define MaxVertexNum 100	//最大顶点数
 
typedef struct ArcNode{	//边/弧
	int adjvex;	//当前结点指向哪一个顶点
	struct ArcNode *next;	//指向下一个边表结点的指针
	//InfoType info;	//边权值
}ArcNode;
 
typedef struct VNode{	//一维数组存储顶点信息
	Vertex data;	//顶点信息
	ArcNode *first;	//第一条边/弧
}VNode, AdjList[MaxVertexNum];	//AdjList表示邻接表类型
 
typedef struct{
	AdjList vertices;	//头结点数组
	int vexnum, arcnum;	//当前的顶点数和边数
}ALGraph;

对比邻接矩阵：

	邻接表	邻接矩阵
空间复杂度	无向图： $O (∣ V ∣ + 2∣ E ∣)$ ，有向图： $O (∣ V ∣ + ∣ E ∣)$	$O (∣ V ∣^{2})$
适用场景	存储稀疏图	存储稠密图
表示方式	不唯一	唯一
计算度、入度、出度	计算有向图的度、入度不方便，其余很方便	遍历对应行或列
找相邻的边	找有向图的入边不方便，其余很方便	遍历对应行或列

6.2.3 十字链表、临接多重表

十字链表、邻接多重表.pdf

十字链表

十字链表存储有向图

顶点结点：对应每一个顶点 data, firstin, firstout，分别记录
弧结点：对应每一条弧 tailvex, headvex, info, hlink, tlink，

空间复杂度： $O (∣ V ∣ + ∣ E ∣)$

寻找指定顶点的所有出边：顺着蓝色线路找
寻找指定顶点的所有入边：顺着红色线路找

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},]
 
	\node[circle, fill=gray!20] at(-3,2) (a) {A};
	\node[circle, fill=gray!20] at(-1,2) (b) {B};
	\node[circle, fill=gray!20] at(-3,0) (c) {C};
	\node[circle, fill=gray!20] at(-1,0) (d) {D};
	\draw[-latex] (a) -- (b);
	\draw[-latex] (a) -- (c);
	\draw[-latex] (c) to[out=150, in=-150] (a);
	\draw[-latex] (c) -- (d);
	\draw[-latex] (d) -- (a);
	\draw[-latex] (d) -- (b);
	\draw[-latex] (d) to[out=-120, in=-60] (c);
 
		\foreach \char [count=\i] in {A,B,C,D} {
			\node[fill=gray!20, minimum width=3em] at(0,4-\i) (\char){\char};
			\node[draw=none] at(-0.5,4-\i) {\i};
		}
		\node at(4,3) (AB){$A\to B$};\node at(6,3) (AC){$A\to C$};\node[draw=none, blue] (nullAout) [right=of AC]{NULL};
		\node at(2,1) (CA){$C\to A$};\node at(8,1) (CD){$C\to D$};\node[draw=none, blue] (nullCout) [right=of CD]{NULL};
		\node at(2,0) (DA){$D\to A$};\node at(4,0) (DB){$D\to B$};\node at(6,0) (DC){$D\to C$};\node[draw=none, blue] (nullDout) [right=of DC]{NULL};
 
		\node[draw=none, red] (nullAin) [below=of DA]{NULL};
		\node[draw=none, red] (nullBin) [below=of DB]{NULL};
		\node[draw=none, red] (nullCin) [below=of DC]{NULL};
		\node[draw=none, red] (nullDin) [above=of CD]{NULL};
 
		\tikzset{arrowout/.style={ -latex, blue}}% 出边
		\tikzset{arrowin/.style={ -latex, red}}% 入边
		\draw[arrowout] (A) -- (AB);
		\draw[arrowout] (AB) -- (AC);
		\draw[arrowout] (AC) -- (nullAout);
		\draw[arrowin] (A) -- (0,2.5) -| (CA);
		\draw[arrowin] (CA) -- (DA);
		\draw[arrowin] (DA) -- (nullAin);
 
		\draw[arrowin] (B) -| ([xshift=-0.5em]AB.south);
		\draw[arrowin] ([xshift=0.5em]AB.south) -- ([xshift=0.5em]DB.north);
		\draw[arrowin] (DB) -- (nullBin);
 
		\draw[arrowout] (C) -- (CA);
		\draw[arrowout] (CA) -- (CD);
		\draw[arrowout] (CD) -- (nullCout);
		\draw[arrowin] (C) -- (0,0.5) -| ([xshift=-0.5em]AC.south);
		\draw[arrowin] ([xshift=0.5em]AC.south) -- ([xshift=0.5em]DC.north);
		\draw[arrowin] (DC) -- (nullCin);
 
		\draw[arrowout] (D) -- (DA);
		\draw[arrowout] (DA) -- (DB);
		\draw[arrowout] (DB) -- (DC);
		\draw[arrowout] (DC) -- (nullDout);
		\draw[arrowin] (D) -- (0,-0.5) -| (CD);
		\draw[arrowin] (CD) -- (nullDin);
 
	\end{tikzpicture}
\end{document}

#define MAX_VERTEX_NUM 20	//最大顶点数量
 
typedef struct ArcBox{		//弧结点
	int tailvex, headvex;	//弧尾、弧头 的顶点编号（一维数组下标）
	struct ArcBox *hlink, *tlink;	//弧头相同、弧尾相同 的下一条弧的链域
	InfoType info;			//权值
}ArcBox;
 
typedef struct VexNode{		//顶点结点
	VertexType data;		//顶点数据域
	ArcBox *firstin, *firstout;	//该顶点的第一条入弧和第一条出弧
}VexNode;
 
typedef struct{				//有向图
	VexNode xlist[MAX_VERTEX_NUM];	//存储顶点的一维数组
	int vexnum, arcnum;	//有向图的当前顶点数和弧数
}OLGraph;

邻接多重表

邻接多重表存储无向图

邻接矩阵、邻接表存储无向图时，每条边对应两份冗余信息，删除顶点、删除边等操作时间复杂度高

邻接矩阵的空间复杂度高

每条边用一个结点表示mark, ivex, ilink, jvex, jlink, info
每个顶点也用一个结点表示data, firstedge

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},]
 
	\node[circle, fill=gray!20] at(-4,3) (a) {A};
	\node[circle, fill=gray!20] at(-2,3) (b) {B};
	\node[circle, fill=gray!20] at(-3,2) (c) {C};
	\node[circle, fill=gray!20] at(-4,1) (d) {D};
	\node[circle, fill=gray!20] at(-2,1) (e) {E};
	\draw[-] (a) -- (b);
	\draw[-] (a) -- (d);
	\draw[-] (b) -- (c);
	\draw[-] (b) -- (e);
	\draw[-] (c) -- (d);
	\draw[-] (c) -- (e);
 
		\foreach \char [count=\i] in {A,B,C,D,E} {
			\node[fill=gray!20, minimum width=3em] at(0,5-\i) (\char){\char};
			\node[draw=none] at(-0.5,5-\i) {\i};
		}
		\node at(2,4) (AB){$A - B$};\node at(4,4) (AD){$A - D$};
		\node at(2,2) (CB){$C - B$};\node at(4,2) (CD){$C - D$};\node at(6,2) (CE) {$C-E$};
		\node at(2,0) (EB){$E - B$};
 
		\node[draw=none] (nullA) [right=of AD]{NULL};
		\node[draw=none] (nullB) [below=of EB]{NULL};
		\node[draw=none] (nullC) [right=of CE]{NULL};
		\node[draw=none] (nullD) [above=of AD]{NULL};
		\node[draw=none] (nullE) [above=of CE]{NULL};
 
		\tikzset{arrowi/.style={ -latex, blue}}%
		\tikzset{arrowj/.style={ -latex, red}}%
		\draw[-latex] (A) -- (AB);
		\draw[arrowi] (AB) -- (AD);
		\draw[arrowi] (AD) -- (nullA);
 
		\draw[-latex] (B) -| ([xshift=-0.5em]AB.south);
		\draw[arrowj] ([xshift=0.5em]AB.south) -- ([xshift=0.5em]CB.north);
		\draw[arrowj] (CB) -- (EB);
		\draw[arrowj] (EB) -- (nullB);
 
		\draw[-latex] (C) -- (CB);
		\draw[arrowi] (CB) -- (CD);
		\draw[arrowi] (CD) -- (CE);
		\draw[arrowi] (CE) -- (nullC);
 
		\draw[-latex] (D) -| (CD);
		\draw[arrowj] (CD) -- (AD);
		\draw[arrowj] (AD) -- (nullD);
 
		\draw[-latex] (E) -- (EB);
		\draw[arrowi] (EB) -| (CE);
		\draw[arrowj] (CE) -- (nullE);
	\end{tikzpicture}
\end{document}

空间复杂度 $O (∣ V ∣ + ∣ E ∣)$
删除边、结点等操作很方便

对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点

#define MAX_VERTEX_NUM 20	//最大顶点数量
 
struct EBox{				//边结点
	int ivex, jvex; 		//该边依附的两个顶点的位置（一维数组下标）
	EBox *ilink, *jlink; 	//分别指向依附这两个顶点的下一条边
	InfoType info; 			//边的权值
};
struct VexBox{
	VertexType data;
	EBox *firstedge; 		//指向第一条依附该顶点的边
};
struct AMLGraph{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum,edgenum; 	//无向图的当前顶点数和边数
};

四种存储方法比较

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	$O (∣ V ∣^{2})$	无向图 $O (∣ V ∣ + 2∣ E ∣)$ 有向图 $O (∣ V ∣ + ∣ E ∣)$	$O (∣ V ∣ + ∣ E ∣)$	$O (∣ V ∣ + ∣ E ∣)$
找相邻边	遍历对应行或列	找有向图的入边必须遍历整个邻接表	很方便	很方便
删除顶点或边	删除边很方便，删除顶点需要大量移动数据	无向图中删除边或顶点都不方便	很方便	很方便
适用场景	存储稠密图	存储稀疏图	存储有向图	存储无向图
表示方式	唯一	不唯一	不唯一	不唯一

6.2.4 图的基本操作

图的基本操作.pdf

仅讨论邻接矩阵与邻接表的结构

Adjacent(G, x, y)：判断图 $G$ 是否存在弧 <x,y> 或边 (x, y)。 $O (∣1∣)$ ， $O (1) \sim O (∣ V ∣)$
Neighbors(G, x)：列出图 $G$ 中与结点 x 邻接的边。
- 无向图： $O (∣ V ∣)$ ， $O (1) \sim O (∣ V ∣)$
- 有向图： $O (∣ V ∣)$ ，入边 $O (∣ E ∣)$ 出边 $O (1) \sim O (∣ V ∣)$
InsertVertex(G, x)：在图 $G$ 中插入顶点 x 。 $O (1)$ ， $O (1)$
DeleteVertex(G, x)：从图 $G$ 中删除顶点 x
- 无向图： $O (∣ V ∣)$ ， $O (1) \sim O (∣ E ∣)$
- 有向图： $O (∣ V ∣)$ ，入边 $O (∣ E ∣)$ 出边 $O (1) \sim O (∣ V ∣)$
AddEdge(G, x, y)：若无向边 (x, y) 或有向边 <x,y> 不存在，则向图 $G$ 中添加该边。 $O (1)$ ， $O (1)$
RemoveEdge(G, x, y)：若无向边 (x, y) 或有向边 <x,y> 存在，则从图 $G$ 中删除该边。
FirstNeighbor(G, x)（重要）：求图 $G$ 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 $- 1$ 。
- 无向图： $O (1) \sim O (∣ V ∣)$ ， $O (1)$
- 有向图： $O (1) \sim O (∣ V ∣)$ ，入边 $O (1) \sim O (∣ E ∣)$ 出边 $O (1)$
NextNeighbor(G, x, y)（重要）：假设图 $G$ 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号。若 y 是 x 的最后一个邻接点，则返回 $- 1$ 。
- 无向图： $O (1) \sim O (∣ V ∣)$ ， $O (1)$
- 有向图： $O (1) \sim O (∣ V ∣)$ ，入边 $O (1) \sim O (∣ E ∣)$ 出边 $O (1)$
Get_edge_value(G, x, y)：获取图 $G$ 中边 (x, y) 或 <x,y> 对应的权值。类似判断边是否存在
Set_edge_value(G, x, y, v)：设置图 $G$ 中边 (x, y) 或 <x,y> 对应的权值为 $v$ 。类似判断边是否存在

6.2.6 本节习题精选

选择题：题目、答案

综合题：题目、答案

6.3 图的遍历

6.3.1 广度优先遍历BFS

图的广度优先遍历演示

图的广度优先遍历.pdf

广度优先遍历（Breadth-First-Search, BFS），可以与树的广度优先遍历（层次遍历）相联系。要点如下：

找到与一个顶点相邻的所有顶点；
需要标记哪些顶点被访问过，保证每个结点只访问一次；
需要一个辅助队列（每次只能处理一个结点，用来保存这一层中暂时未被访问到的结点）

广度优先遍历用到的操作（邻接表存储）：

FirstNeighbor(G, x)：求图 $G$ 中顶点 x 的第一个邻接点，若有则返回顶点号；若 x 没有邻接点或图中不存在 x，则返回 $- 1$ 。
NextNeighbor(G, x, y)：假设图 $G$ 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 $- 1$ 。

广度优先遍历可用来解决各边权值相等的单源最短路径问题

广度优先遍历算法题

//个人理解：对所有结点进行遍历，如没有被访问过，则进行广度优先遍历（作为初始结点）
	//广度优先遍历：对初始结点进行访问并做标记，入队。
		//对队列进行处理：若队列不空，则队头结点出队，遍历其所有邻接点。若还未访问，则访问、标记、入队
 
bool visited[MAX_VERTEX_NUM];	//访问标记数组，初始均为false
 
//对图G进行广度优先遍历【处理非连通图】
void BFSTraverse(Graph G){
	for(i=0; i<G.vexnum; ++i)
		visited[i]=FALSE;			// 访问标记数组初始化(应该是全局变量？)
	InitQueue(Q);					// 初始化辅助队列
	for(i=0; i<G.vexnum; ++i)		// 从0号结点开始遍历，对每个连通分量进行一次BFS()
		if(!visited[i])	BFS(G,i);	// 如果vi从未访问过，从vi开始BFS
			// 调用次数等于连通分量数，即一共有几个连通的图
}
 
//从顶点v开始，广度优先遍历顶点v所在子图
void BFS(Graph G,int v){
	visit(v);					//访问图G的初始顶点v
	visited[v]=TRUE;			//标记v已被访问
	EnQueue(Q, v);				//顶点v入队列Q
	while(!isEmpty(Q)){
		DeQueue(Q,v);			//队列头节点出队，并将头结点的值赋给v
		for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){ //检测v的所有邻结点
			if(!visited[w]){
				visit(w);				//访问顶点w
				visited[w]=true;
				EnQueue(Q,w);		   //顶点入队
			}//if
		}//for
	}
}

复杂度分析：

空间复杂度：最坏情况，辅助队列大小为 $O (∣ V ∣)$ 。
时间复杂度：访问结点的时间+访问边的时间考前记一记
- 对于邻接矩阵存储的图，访问 $∣ V ∣$ 个顶点需要 $O (∣ V ∣)$ 的时间，查找每个顶点的邻接点都需要 $O (∣ V ∣)$ 的时间，而总共有 $∣ V ∣$ 个顶点，时间复杂度为 $O (∣ V ∣^{2})$
- 对于邻接表存储的图，访问 $∣ V ∣$ 个顶点需要 $O (∣ V ∣)$ 的时间，查找各个顶点的邻接点共需要 $O (∣ E ∣)$ 的时间，时间复杂度为 $O (∣ V ∣ + ∣ E ∣)$

广度优先生成树：广度优先生成树由广度优先遍历过程确定。

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一
同一个图的邻接表表示方式不唯一，因此广度优先遍历序列不唯一。但对于给定的邻接表，其遍历序列唯一。

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,draw=black,circle,very thick]
	\node(1) at(0,2) {1};
	\node(2) at(2,2) {2};
	\node(3) at(4,2) {3};
	\node(4) at(6,2) {4};
	\node(5) at(0,0) {5};
	\node(6) at(2,0) {6};
	\node(7) at(4,0) {7};
	\node(8) at(6,0) {8};
 
	\draw[-] (5) -- (1);
	\draw[-] (1) -- (2);
	\draw[-] (2) -- (6);
	\draw[-] (6) -- (3);
	\draw[-] (6) -- (7);
	\draw[-] (3) -- (4);
	\draw[-] (3) -- (7);
	\draw[-] (4) -- (7);
	\draw[-] (4) -- (8);
	\draw[-] (7) -- (8);
 
	\node[below right] at(8,4) (species1) [shape=rectangle, draw] {
	\fontsize{32}{20}\selectfont%
	\begin{tabular}{c|l}
		data & $*$first\\
		\hline
		 1 & -\textgreater2–\textgreater5\\%转义>
		 2 & –\textgreater1–\textgreater6\\
		 3 & –\textgreater4–\textgreater6–\textgreater7 \\
		 4 & –\textgreater3–\textgreater7–\textgreater8 \\
		 5 & –\textgreater1 \\
		 6 & –\textgreater2–\textgreater3–\textgreater7 \\
		 7 & –\textgreater3–\textgreater4–\textgreater6–\textgreater8 \\
		 8 & –\textgreater4–\textgreater7 \\
	\end{tabular}
	};
 	\end{tikzpicture}
\end{document}

\begin{document}
	\begin{tikzpicture}[scale=1, line width=1.5pt,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=2em},
	level/.style={sibling distance=10em/#1},%统一层级结点之间的横向距离
	level distance=5em]%不同层级之间的纵向距离
 
	\node(1) at(0,2) {1};
	\node(2) at(2,2) {2};
	\node(3) at(4,2) {3};
	\node(4) at(6,2) {4};
	\node(5) at(0,0) {5};
	\node(6) at(2,0) {6};
	\node(7) at(4,0) {7};
	\node(8) at(6,0) {8};
 
	\draw[-][red] (5) -- (1);
	\draw[-][red] (1) -- (2);
	\draw[-][red] (2) -- (6);
	\draw[-][red] (6) -- (3);
	\draw[-][red] (6) -- (7);
	\draw[-][red] (3) -- (4);
	\draw[-] (3) -- (7);
	\draw[-] (4) -- (7);
	\draw[-] (4) -- (8);
	\draw[-][red] (7) -- (8);
 
	\node(2) at(14,2) {2}
		child {node (1) {1}
			child {node (5) {5}}
		}
        child {node (6) {6}
			child {node (7) {7}
				child {node (4) {4}}
			}
			child {node (3) {3}
				child {node (8) {8}}
			}
		};
	\end{tikzpicture}
\end{document}

广度优先生成森林：对于非连通图的广度优先遍历，可以得到广度优先生成森林

6.3.2 深度优先遍历DFS

图的深度优先遍历演示

图的深度优先遍历.pdf

深度优先遍历（Deepth-First-Search, DFS），可以与树的先序遍历相联系

递归实现DFS算法算法题

//个人理解：对所有结点进行遍历，如没有被访问过，则进行深度优先遍历（作为初始结点）
	//深度优先遍历：对初始结点进行访问并做标记，使用递归进行遍历
		//递归过程：如果遍历当前结点邻接点，如果未被访问，则进行深度优先遍历
 
bool visited[MAX_VERTEX_NUM];	//访问标记数组
 
// 对图G进行深度优先算法【处理非连通图】
void DFSTraverse(Graph G){
	for(v=0; v<G.vexnum; v++)	//初始化标记数组
		visited[v]=FALSE;
	for(v=0; v<G.vexnum; v++){
		if(!visited[v])
			DFS(G,v);
	}
}
 
// 从顶点v出发深度优先遍历顶点v所在子图
void DFS(Graph G,int v){
	visit(v);
	visited[v]=true;
	for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v)){
		if(!visited[w])				//w是u的尚未访问的邻接顶点
			DFS(G,v);
	}
}

复杂度分析：

空间复杂度主要来自来自函数递归调用栈，最坏情况下递归深度为 $O (∣ V ∣)$ ；最好情况为 $O (1)$
时间复杂度：访问结点的时间+访问边的时间
- 对于邻接矩阵存储的图，访问 $∣ V ∣$ 个顶点需要 $O (∣ V ∣)$ 的时间，查找每个顶点的邻接点都需要 $O (∣ V ∣)$ 的时间，而总共有 $∣ V ∣$ 个顶点，时间复杂度为 $O (∣ V ∣^{2})$
- 对于邻接表存储的图，访问 $∣ V ∣$ 个顶点需要 $O (∣ V ∣)$ 的时间，查找各个顶点的邻接点共需要 $O (∣ E ∣)$ 的时间，时间复杂度为 $O (∣ V ∣ + ∣ E ∣)$

深度优先遍历可用来判断有向图中是否存在回路

深度优先遍历序列：

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一
同一个图的邻接表表示方式不唯一，因此深度优先遍历序列不唯一。对于给定的邻接表，其遍历序列唯一

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,draw=black,circle,very thick]
	\node(1) at(0,2) {1};
	\node(2) at(2,2) {2};
	\node(3) at(4,2) {3};
	\node(4) at(6,2) {4};
	\node(5) at(0,0) {5};
	\node(6) at(2,0) {6};
	\node(7) at(4,0) {7};
	\node(8) at(6,0) {8};
 
	\draw[-] (5) -- (1);
	\draw[-] (1) -- (2);
	\draw[-] (2) -- (6);
	\draw[-] (6) -- (3);
	\draw[-] (6) -- (7);
	\draw[-] (3) -- (4);
	\draw[-] (3) -- (7);
	\draw[-] (4) -- (7);
	\draw[-] (4) -- (8);
	\draw[-] (7) -- (8);
 
	\matrix[ampersand replacement=\&][below right, rectangle, draw=none] at(8,4) {
		\& \node(species2) [rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\setlength{\extrarowheight}{1em}
		\begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}M{1em}}
			1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
		\end{tabular}
		};\\
		\node(species3) [shape=rectangle, draw=none] {
			\begin{tabular}{c}
			1 \\
			2 \\
			3 \\
			4 \\
			5 \\
			6 \\
			7 \\
			8 \\
			\end{tabular}
		}; \&
		\node(species4) [shape=rectangle, draw=none] {
		\newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}
		\begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|}
\hline
	0&\textbf{1}&0&0&\textbf{1}&0&0&0\\\hline
	\textbf{1}&0&0&0&0&\textbf{1}&0&0\\\hline
	0&0&0&\textbf{1}&0&\textbf{1}&\textbf{1}&0\\\hline
	0&0&\textbf{1}&0&0&0&\textbf{1}&\textbf{1}\\\hline
	\textbf{1}&0&0&0&0&0&0&0\\\hline
	0&\textbf{1}&\textbf{1}&0&0&0&\textbf{1}&0\\\hline
	0&0&\textbf{1}&\textbf{1}&0&\textbf{1}&0&\textbf{1}\\\hline
	0&0&0&\textbf{1}&0&0&\textbf{1}&0\\\hline
		\end{tabular}
		};\\
	};
 	\end{tikzpicture}
\end{document}

从 2 出发的深度优先遍历序列：2, 1, 5, 6, 3, 4, 7, 8
从 3 出发的深度优先遍历序列：3, 4, 7, 6, 2, 1, 5, 8
从 1 出发的深度优先遍历序列：1, 2, 6, 3, 4, 7, 8, 5

深度优先生成树：

\begin{document}
	\begin{tikzpicture}[scale=1.2, ultra thick]
	\tikzstyle{every node}=[font=\huge,draw=black,circle,very thick]
	\node(1) at(0,2) {1};
	\node(2) at(2,2) {2};
	\node(3) at(4,2) {3};
	\node(4) at(6,2) {4};
	\node(5) at(0,0) {5};
	\node(6) at(2,0) {6};
	\node(7) at(4,0) {7};
	\node(8) at(6,0) {8};
 
	\draw[-][red] (5) -- (1);
	\draw[-][red] (1) -- (2);
	\draw[-][red] (2) -- (6);
	\draw[-][red] (6) -- (3);
	\draw[-] (6) -- (7);
	\draw[-][red] (3) -- (4);
	\draw[-] (3) -- (7);
	\draw[-][red] (4) -- (7);
	\draw[-] (4) -- (8);
	\draw[-][red] (7) -- (8);
 
	\node(2) at (10,2){2}
		child {node (1) {1}
			child {node (5) {5}}
		}
		child {node (6) {6}
			child {node (3) {3}
				child {node (4) {4}
					child {node (7) {7}
						child {node (8) {8}}
					}
				}
			}
		};
	\end{tikzpicture}
\hspace{20em}
\end{document}

图的遍历与图的连通性

对无向图进行 BFS/DFS 遍历，调用 BFS/DFS函数的次数=连通分量数。对于连通图，只需调用 1 次 BFS/DFS函数。
对有向图进行 BFS/DFS 遍历，调用 BFS/DFS函数的次数要具体问题具体分析。若起始顶点到其他各顶点都有路径，则只需调用 1 次 BFS/DFS函数。对于强连通图，从任一结点出发都只需调用 1 次 BFS/DFS函数。

6.3.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

6.4 图的应用

6.4.1 最小生成树

最小生成树.pdf

生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 $n$ ，则它的生成树含有 $n - 1$ 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
最小生成树（最小代价树）：对于一个带权连通无向图 $G = (V, E)$ ，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 $R$ 为 $G$ 的所有生成树的集合，若 $T$ 为 $R$ 中边的权值之和最小的生成树，则 $T$ 称为 G 的最小生成树（Minimum-Spanning-Tree, MST）。
- 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
- 最小生成树的边数 = 顶点数 $- 1$ 。砍掉一条则不连通，增加一条边则会出现回路。
- 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。
- 只有连通图才有生成树，非连通图只有生成森林。
对比：考前记一记
- 如果需要判断MST是否唯一、是否有多种形态，应使用Kruskal算法
- Prim算法需要指定初始顶点，而Kruskal算法不需要

补充：对于带权连通图，当其任意一个环中包含的边的权值均不相同时，其最小生成树唯一

Prim算法

Prim算法演示

Prim 算法（普里姆）：从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

实现思想

循环遍历所有的结点，找到lowCast最低且还没加入到树的顶点，加入树
再次循环遍历，更新还没加入的各个顶点的lowCast值
重复上述步骤

下图中，可以由点C开始，依次选择顶点A、D、F、B、C加入生成树中

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-},
	]
	\node at(0,2.5) (A) {$A$};
	\node at(0,-0.5) (C) {$C$};
	\node at(-3,0) (B) {$B$};
	\node at(3,0) (D) {$D$};
	\node at(-2,-3) (E) {$E$};
	\node at(2,-3) (F) {$F$};
 
	\draw[arrow] (A)--(B)node[midway, left,  font=\large, draw=none]{6};
	\draw[arrow] (A)--(C)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (A)--(D)node[midway, right, font=\large, draw=none]{5};
	\draw[arrow] (B)--(C)node[midway, above, font=\large, draw=none]{5};
	\draw[arrow] (B)--(E)node[midway, left,  font=\large, draw=none]{3};
	\draw[arrow] (D)--(C)node[midway, above, font=\large, draw=none]{4};
	\draw[arrow] (D)--(F)node[midway, right, font=\large, draw=none]{2};
	\draw[arrow] (C)--(E)node[midway, left,  font=\large, draw=none]{6};
	\draw[arrow] (C)--(F)node[midway, right, font=\large, draw=none]{4};
	\draw[arrow] (E)--(F)node[midway, above, font=\large, draw=none]{6};
	\end{tikzpicture}
 
	\hspace{5em}
 
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-, dashed},
	]
	\node at(0,2.5) (A) {$A$};
	\node at(0,-0.5) (C) {$C$};
	\node at(-3,0) (B) {$B$};
	\node at(3,0) (D) {$D$};
	\node at(-2,-3) (E) {$E$};
	\node at(2,-3) (F) {$F$};
 
	\draw[arrow] (A)--(B)node[midway, left,  font=\large, draw=none]{6};
	\draw[-, red] (A)--(C)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (A)--(D)node[midway, right, font=\large, draw=none]{5};
	\draw[-, red] (B)--(C)node[midway, above, font=\large, draw=none]{5};
	\draw[-, red] (B)--(E)node[midway, left,  font=\large, draw=none]{3};
	\draw[-, red] (D)--(C)node[midway, above, font=\large, draw=none]{4};
	\draw[-, red] (D)--(F)node[midway, right, font=\large, draw=none]{2};
	\draw[arrow] (C)--(E)node[midway, left,  font=\large, draw=none]{6};
	\draw[arrow] (C)--(F)node[midway, right, font=\large, draw=none]{4};
	\draw[arrow] (E)--(F)node[midway, above, font=\large, draw=none]{6};
	\end{tikzpicture}
\end{document}

Kruskal算法

Kruskal算法演示

Kruskal 算法（克鲁斯卡尔）：每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选），直到所有结点都连通。

实现思想

将各条边按权值排序
依次检查每条边的两个顶点是否连通（是否属于同一个集合）——并查集。不连通就连起来，已连通就跳过

下图中，依次选择边AC、DF、BE、CD、BC来构建生成树

\usetikzlibrary{positioning}
\usepackage{array}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-},
	]
	\node at(0,2.5) (A) {$A$};
	\node at(0,-0.5) (C) {$C$};
	\node at(-3,0) (B) {$B$};
	\node at(3,0) (D) {$D$};
	\node at(-2,-3) (E) {$E$};
	\node at(2,-3) (F) {$F$};
 
	\draw[arrow] (A)--(B)node[midway, left,  font=\large, draw=none]{6};
	\draw[arrow] (A)--(C)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (A)--(D)node[midway, right, font=\large, draw=none]{5};
	\draw[arrow] (B)--(C)node[midway, above, font=\large, draw=none]{5};
	\draw[arrow] (B)--(E)node[midway, left,  font=\large, draw=none]{3};
	\draw[arrow] (D)--(C)node[midway, above, font=\large, draw=none]{4};
	\draw[arrow] (D)--(F)node[midway, right, font=\large, draw=none]{2};
	\draw[arrow] (C)--(E)node[midway, left,  font=\large, draw=none]{6};
	\draw[arrow] (C)--(F)node[midway, right, font=\large, draw=none]{4};
	\draw[arrow] (E)--(F)node[midway, above, font=\large, draw=none]{6};
 
	\node at(6,0) (species1) [shape=rectangle, draw] {
	\fontsize{32}{20}\selectfont%
	\begin{tabular}{c|c}
		weight & vertex\\
		\hline
		 1 & $A-C$ \\
		 2 & $D-F$\\
		 3 & $B-E$ \\
		 4 & $C-D$ \\
		 4 & $C-F$ \\
		 5 & $A-D$ \\
		 5 & $B-C$ \\
		 6 & $A-B$ \\
		 6 & $C-E$ \\
		 6 & $E-F$ \\
	\end{tabular}
	};
 
	\end{tikzpicture}
 
	\hspace{2em}
 
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-, dashed},
	]
	\node at(0,2.5) (A) {$A$};
	\node at(0,-0.5) (C) {$C$};
	\node at(-3,0) (B) {$B$};
	\node at(3,0) (D) {$D$};
	\node at(-2,-3) (E) {$E$};
	\node at(2,-3) (F) {$F$};
 
	\draw[arrow] (A)--(B)node[midway, left,  font=\large, draw=none]{6};
	\draw[-, red] (A)--(C)node[midway, right, font=\large, draw=none]{1};
	\draw[arrow] (A)--(D)node[midway, right, font=\large, draw=none]{5};
	\draw[-, red] (B)--(C)node[midway, above, font=\large, draw=none]{5};
	\draw[-, red] (B)--(E)node[midway, left,  font=\large, draw=none]{3};
	\draw[-, red] (D)--(C)node[midway, above, font=\large, draw=none]{4};
	\draw[-, red] (D)--(F)node[midway, right, font=\large, draw=none]{2};
	\draw[arrow] (C)--(E)node[midway, left,  font=\large, draw=none]{6};
	\draw[arrow] (C)--(F)node[midway, right, font=\large, draw=none]{4};
	\draw[arrow] (E)--(F)node[midway, above, font=\large, draw=none]{6};
	\end{tikzpicture}
\end{document}

	Prim 算法（普里姆）	Kruskal 算法（克鲁斯卡尔）
时间复杂度	$O (∣ V ∣^{2})$	$O (∣ E ∣ lo g_{2} ∣ E ∣)$
适用场景	边稠密图	边稀疏图

6.4.2 最短路径

单源最短路径问题——BFS算法

适用于无权图

无权图可以视为每条边的权值都为 1 的带权图。

BFS算法.pdf

使用 BFS算法求无权图的最短路径问题，需要使用三个数组：

d[ ]数组用于记录顶点 u 到其他顶点的最短路径。
path[ ]数组用于记录最短路径从哪个顶点过来。
visited[ ]数组用于记录是否被访问过。

\begin{document}
	\begin{tikzpicture}[scale=1, line width=1.5pt,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=2em},
	level/.style={sibling distance=10em/#1},%统一层级结点之间的横向距离
	level distance=5em]%不同层级之间的纵向距离
 
	\node(1) at(0,2) {1};
	\node(2) at(2,2) {2};
	\node(3) at(4,2) {3};
	\node(4) at(6,2) {4};
	\node(5) at(0,0) {5};
	\node(6) at(2,0) {6};
	\node(7) at(4,0) {7};
	\node(8) at(6,0) {8};
 
	\draw[-][red] (5) -- (1);
	\draw[-][red] (1) -- (2);
	\draw[-][red] (2) -- (6);
	\draw[-][red] (6) -- (3);
	\draw[-][red] (6) -- (7);
	\draw[-][red] (3) -- (4);
	\draw[-] (3) -- (7);
	\draw[-] (4) -- (7);
	\draw[-] (4) -- (8);
	\draw[-][red] (7) -- (8);
 
	\node at(12,1) (species1) [shape=rectangle, draw] {
	\fontsize{32}{20}\selectfont%
	\begin{tabular}{c|c|c|c|c|c|c|c|c}
		        & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\
		\hline
		 d[  ]    & 1 & 0 & 2 & 3 & 2 & 1 & 2 & 3 \\
		 path[  ] & 2 & -1& 6 & 3 & 1 & 2 & 6 & 7 \\
	\end{tabular}
	};
	\end{tikzpicture}
\end{document}

通过 d[ ]可知，2到8的最短路径长度为3；从 path[8] 逆向搜寻可知，2到8的最短路径2->6->7->8

//个人理解：访问结点时，深度+1并记录其前驱结点
 
#define MAX_LENGTH 2147483647			//地图中最大距离，表示正无穷
 
// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){
	for(i=0; i<G.vexnum; i++){
		visited[i]=FALSE;				//初始化访问标记数组
		d[i]=MAX_LENGTH;				//初始化路径长度
		path[i]=-1;						//初始化最短路径记录
	}
	InitQueue(Q);						//初始化辅助队列
	d[u]=0;								//起始顶点最短距离为0
	visites[u]=TRUE;
	EnQueue(Q,u);
	while(!isEmpty[Q]){					//BFS算法主过程
		DeQueue(Q,u);					//队头元素出队并赋给u
		for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u,w)){
			if(!visited[w]){
				d[w]=d[u]+1;			//修改顶点的最短路径长度
				path[w]=u;				//记录直接前驱
				visited[w]=TRUE;
				EnQueue(Q,w);			//顶点w入队
			}//if
		}
	}//while
}

单源最短路径问题——Dijkstra算法

Dijkstra算法能够很好的处理带权图的单源最短路径问题，但不适用于有负权值的带权图。

Dijkstra算法

Dijkstra算法演示

Dijkstra算法.pdf

BFS算法的局限性：BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图。
使用 Dijkstra（迪杰斯特拉）算法求最短路径问题，需要使用三个数组：
- final[ ] 数组用于标记各顶点是否已找到最短路径。
- dist[ ] 数组用于记录各顶点到源顶点的最短路径长度。
- path[ ] 数组用于记录各顶点目前最短路径上的前驱。
实现思想（类似Prim 算法 ^[注：Prim算法和Dijkstra算法的区别]）
- 循环遍历所有的结点，找到还没确定最短路径且dist最小的顶点 $V_{i}$ ，令final[i]=true
- 检查所有邻接 $V_{i}$ 的顶点，若其final值为false，则更新dist和path信息
- 重复上述步骤

时间复杂度 $O (∣ V ∣^{2})$

//个人理解：初始化后，将与初始顶点相邻的顶点距离设置为路径长度，设置path值为初始结点
	//每次循环找到还没确定最短路径且dist最小的结点，标记为已确定最短路径。
	//对其邻接结点进行检查，更新dist信息和path信息
 
// 求顶点u到其他顶点的最短路径，邻接矩阵实现
#define MAX_LENGTH = 2147483647;
 
void DIJKSTRA_MIN_Disrance(Graph G,int u){
	for(int i=0; i<G.vexnum; i++){		//初始化
		final[i]=false;			//标记全部顶点为未找到最短路径
		dist[i]=G.edge[u][i];	//标记存在直接连接路径的顶点的距离
		if(G.edge[u][i]==MAX_LENGTH || G.edge[u][i] == 0)
			path[i] = -1;		//没有直接连接路径
		else
			path[i] = u;		//存在直接连接路径
		final[u]=true;			//标记初始顶点
	}//for
 
	for(int i=1; i<G.vexnum; i++){//找到第i个节点
		int MIN=MAX_LENGTH;
		int v;
		for(int j=0; j<G.vexnum; j++){
			// 循环遍历所有结点，找到还没确定最短路径，且dist最小的顶点v
			if(final[j]==false && dist[j]<MIN){
				MIN = dist[j];
				v = j;
			}//if
		final[v]=true;
		// 检查所有邻接自v且还没确定最短路径的顶点，其路径长度是否最短
		for(int j=0; j<G.vexnum; j++){
			if(final[j]==false && dist[j]>dist[v]+G.edge[v][j]){
				//路径还可作出优化
				dist[j] = dist[v]+G.edge[v][j];
				path[j] = v;
			}//if
		}//for
	}//for
}

Dijkstra算法也可求所有顶点间的最短路径，重复 $∣ V ∣$ 次即可，总的时间复杂度也是 $O (∣ V ∣^{3})$

Example

 

\usetikzlibrary{positioning}

\usepackage{array}

\begin{document}

\begin{tikzpicture}[scale=1.5, ultra thick,

every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},

arrow/.style={-latex},

]

\node at(-2,1.5) (0) { $V_{0}$ };

\node at(0,3) (1) { $V_{1}$ };

\node at(3,3) (2) { $V_{2}$ };

\node at(3,0) (3) { $V_{3}$ };

\node at(0,0) (4) { $V_{4}$ };

\draw[arrow] (0)—(2)node[midway, above, font=\large, draw=none]{1};

\draw[arrow] (0)—(4)node[midway, above, font=\large, draw=none]{10};

\draw[arrow] (1)—(4)node[midway, left, font=\large, draw=none]{5};

\draw[arrow] (1)—(3)node[midway, below, font=\large, draw=none]{1};

\draw[arrow] (2)—(1)node[midway, above, font=\large, draw=none]{1};

\draw[arrow] (2)—(4)node[midway, above, font=\large, draw=none]{7};

\draw[arrow] (3)—(4)node[midway, above, font=\large, draw=none]{1};

\end{tikzpicture}

\end{document}

如上图所示带权有向图，从顶点 $V_{0}$ 出发执行Dijkstra算法，有如下过程：

第一轮：顶点 $V_{0}$ 到顶点 $V_{2}$ 的距离最短，为1，路径为 $V_{0} \to V_{2}$

第二轮：顶点 $V_{0}$ 到顶点 $V_{1}$ 的距离最短，为2，路径为 $V_{0} \to V_{2} \to V_{1}$

第三轮：顶点 $V_{0}$ 到顶点 $V_{3}$ 的距离最短，为3，路径为 $V_{0} \to V_{2} \to V_{1} \to V_{3}$

第四轮：顶点 $V_{0}$ 到顶点 $V_{4}$ 的距离最短，为4，路径为 $V_{0} \to V_{2} \to V_{1} \to V_{3} \to V_{4}$

各顶点间的最短路径问题——Floyd算法

Floyd算法演示

Floyd算法.pdf

Floyd算法（弗洛伊德）：求出每一对顶点之间的最短路径，使用动态规划思想，将问题的求解分为多个阶段。对于 n 个顶点的图 G，求任意一对顶点 $V_{i} \to V_{j}$ 之间的最短路径可以分为如下几个阶段：

初始：不允许在其他顶点中转，最短路径是？—— $A^{(- 1)}, p a t h^{(- 1)}$
#0：若允许在 $V_{0}$ 中转，最短路径是？—— $A^{(0)}, p a t h^{(0)}$
#1：若允许在 $V_{0}, V_{1}$ 中转，最短路径是？—— $A^{(1)}, p a t h^{(1)}$
……
#n-1：若允许在 $V_{0}, V_{1}, \dots, V_{n - 1}$ 中转，最短路径是？—— $A^{(n - 1)}, p a t h^{(n - 1)}$

Floyd算法使用到两个矩阵：

dist[ ][ ]：目前各顶点间的最短路径。
path[ ][ ]：两个顶点之间的中转点。若 path[i][j] = k，且 i 与 k 之间没有直接路径，则还需要查询 i 与 k 之间的最短路径 path[i][k]，k 与 j 之间同理。
若 $A^{(k - 1)} [i] [j] > A^{(k - 1)} [i] [k] + A^{(k - 1)} [k] [j]$ ，（中转距离小于原有距离）则 $A^{(k)} [i] [j] = A^{(k - 1)} [i] [k] + A^{(k - 1)} [k] [j]$ ， $p a t h^{(k)} [i] [j] = k$ ，否则 $A^{(k)}$ ， $p a t h^{(k)}$ 保持原值
从 $A^{(- 1)}, p a t h^{(- 1)}$ 开始，经过 $n$ 轮递推，得到 $A^{(n - 1)}, p a t h^{(n - 1)}$

Example

示例：如下图中最终得到矩阵 A 与矩阵 path。 A[0][4] = 4，说明 $V_{0}$ 到 $V_{4}$ 的最短距离为4。path[0][4] = 3，说明 $V_{0}$ 到 $V_{4}$ 的最短路径需要经过 $V_{3}$ ； path[0][3] = 2，说明 $V_{0}$ 到 $V_{3}$ 需要经过 $V_{2}$ ； path[2][3] = 1，说明 $V_{2}$ 到 $V_{3}$ 需要经过 $V_{1}$ 。path[0][2] = -1、path[2][1] = -1、path[1][3] = -1、path[3][4] = -1，因此 $V_{0}$ 到 $V_{4}$ 的最短路径为 $V_{0} \to V_{2} \to V_{1} \to V_{3} \to V_{4}$ 。

 

\usetikzlibrary{positioning}

\usepackage{array}

\begin{document}

\begin{tikzpicture}[scale=1.5, ultra thick,

every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},

arrow/.style={-latex},

]

\node at(-2,1.5) (0) { $V_{0}$ };

\node at(0,3) (1) { $V_{1}$ };

\node at(3,3) (2) { $V_{2}$ };

\node at(3,0) (3) { $V_{3}$ };

\node at(0,0) (4) { $V_{4}$ };

\draw[arrow] (0)—(2)node[midway, above, font=\large, draw=none]{1};

\draw[arrow] (0)—(4)node[midway, above, font=\large, draw=none]{10};

\draw[arrow] (1)—(4)node[midway, left, font=\large, draw=none]{5};

\draw[arrow] (1)—(3)node[midway, below, font=\large, draw=none]{1};

\draw[arrow] (2)—(1)node[midway, above, font=\large, draw=none]{1};

\draw[arrow] (2)—(4)node[midway, above, font=\large, draw=none]{7};

\draw[arrow] (3)—(4)node[midway, above, font=\large, draw=none]{1};

\node[draw=none] at(5,1.5) (A) { $A =$ };

\matrix[ampersand replacement=&][right=of A, xshift=-3em, rectangle, draw=none] {

  \& \node(species2) [rectangle, draw=none] {

  \newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}

  \setlength{\extrarowheight}{1em}

  \begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}}

  	$V_{0}$ & $V_{1}$ & $V_{2}$ & $V_{3}$ & $V_{4}$ \\

  \end{tabular}

  };\\

  \node(species3) [shape=rectangle, draw=none] {

  	\begin{tabular}{c}

  	$V_{0}$ \\

  	$V_{1}$ \\

  	$V_{2}$ \\

  	$V_{3}$ \\

  	$V_{4}$ \\

  	\end{tabular}

  }; \&

  \node(species4) [shape=rectangle, draw=none] {

  \newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}

  \begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|}

  	\hline

  	0 & 2 & 1 & 3 & 4 \\ \hline

  	$\infty$ & 0 & $\infty$ & 1 & 2 \\ \hline

  	$\infty$ & 1 & 0 & 2 & 3 \\ \hline

  	$\infty$ & $\infty$ & $\infty$ & 0 & 1 \\ \hline

  	$\infty$ & $\infty$ & $\infty$ & $\infty$ & 0 \\ \hline

  \end{tabular}

  };\\

};

\node[draw=none] at(12,1.5) (path) {path $=$ };

\matrix[ampersand replacement=&][right=of path, xshift=-3em, rectangle, draw=none] {

  \& \node(species2) [rectangle, draw=none] {

  \newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}

  \setlength{\extrarowheight}{1em}

  \begin{tabular}{M{1em}M{1em}M{1em}M{1em}M{1em}}

  	$V_{0}$ & $V_{1}$ & $V_{2}$ & $V_{3}$ & $V_{4}$ \\

  \end{tabular}

  };\\

  \node(species3) [shape=rectangle, draw=none] {

  	\begin{tabular}{c}

  	$V_{0}$ \\

  	$V_{1}$ \\

  	$V_{2}$ \\

  	$V_{3}$ \\

  	$V_{4}$ \\

  	\end{tabular}

  }; \&

  \node(species4) [shape=rectangle, draw=none] {

  \newcolumntype{M}[1]{>{\centering\arraybackslash}m{#1}}

  \begin{tabular}{|M{1em}|M{1em}|M{1em}|M{1em}|M{1em}|}

  	\hline

  	-1 & 2 & -1 & 2 & 3 \\ \hline

  	-1 & -1 & -1 & -1 & 3 \\ \hline

  	-1 & -1 & -1 & 1 & 3 \\ \hline

  	-1 & -1 & -1 & -1 & -1 \\ \hline

  	-1 & -1 & -1 & -1 & -1 \\ \hline

  \end{tabular}

  };\\

};

\end{tikzpicture}

\end{document}

时间复杂度 $O (∣ V ∣^{3})$ （ $n^{2}$ 条路径， $n$ 轮循环），空间复杂度 $O (∣ V ∣^{2})$

int dist[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];
 
void Floyd(MGraph G){
	int i,j,k;
	// 初始化部分，根据图的信息初始化矩阵A和path
	for(i=0 ;i<G.vexnum; i++){
		for(j=0; j<G.vexnum; j++){
			dist[i][j] = G.Edge[i][j];
			path[i][j] = -1;
		}
	}
	// 算法核心部分
	for(k=0; k<G.vexnum; k++){				//考虑以Vk为中转点
		for(i=0; i<G.vexnum; i++){			//遍历整个矩阵，i为行号，j为列号
			for(j=0; j<G.vexnum; j++){
				if(dist[i][j]>dist[i][k]+dist[k][j]){	//以Vk为中转点的路径是否更短
					dist[i][j] = dist[i][k]+dist[k][j];	//更新最短路径长度
					path[i][j] = k;						//更新中转点
				}//if
			}//for
		}
	}
}

Floyd算法可以用于负权值带权图，但是不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径。

最短路径算法比较

	BFS算法	Dijkstra算法	Floyd算法
无权图	✔	✔	✔
带权图	✘	✔	✔
带负权值的图	✘	✘	✔
带负权回路的图	✘	✘	✘
时间复杂度	$O (∣ V ∣^{2})$ 或 $O (∣ V ∣ + ∣ E ∣)$	$O (∣ V ∣^{2})$	$O (∣ V ∣^{3})$
通常用于	求无权图的单源最短路径	求带权图的单源最短路径	求带权图中各顶点间的最短路径

6.4.3 有向无环图描述表达式

有向无环图描述表达式.pdf

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称 DAG图(Directed Acyclic Graph)。

用有向无环图描述表达式 $((a + b) * (b * (c + d)) + (c + d) * e) * ((c + d) * e)$

\begin{document}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=16em/1, level distance=3em},%横向距离与轴向距离
	level 2/.style={sibling distance=16em/2, level distance=3em},
	level 3/.style={sibling distance=16em/4, level distance=3em},
	level 4/.style={sibling distance=16em/8, level distance=3em},
	level 5/.style={sibling distance=16em/8, level distance=3em},
	]
	\node at(0,0) {$*$}
		child {node {$+$}
			child {node {$*$}
				child {node {$+$}
					child {node {$a$}}
					child {node {$b$}}
				}
				child {node {$*$}
					child {node {$b$}}
					child {node {$+$}
						child {node {$c$}}
						child {node {$d$}}
					}
				}
			}
	        child {node {$*$}
				child {node {$+$}
					child {node {$c$}}
					child {node {$d$}}
				}
				child {node {$e$}}
			}
		}
        child {node {$*$}
			child {node {$+$}
				child {node {$c$}}
				child {node {$d$}}
			}
			child {node {$e$}}
		};
	\end{tikzpicture}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	level 1/.style={sibling distance=5em/1, level distance=3em},%横向距离与轴向距离
	level 2/.style={sibling distance=5em/2, level distance=3em},
	level 3/.style={sibling distance=5em/2, level distance=3em},
	level 4/.style={sibling distance=5em/2, level distance=3em},
	]
	\node at(8,0) (1) {$*$}
		child {node (2) {$+$}
			child {node (3) {$*$}
				child {node (5) {$+$}
					child {node (9) {$a$}}
					child {node (10) {$b$}}
				}
				child {node (6) {$*$}}
			}
		}
        child[level distance=6em] {node (4) {$*$}
			child[level distance=3em] {node (7) {$+$}
				child {node (11) {$c$}}
				child {node (12) {$d$}}
			}
			child[level distance=3em] {node (8) {$e$}}
		};
		\draw[-](2)--(4);
		\draw[-](6)--(7);
		\draw[-](6)--(10);
	\end{tikzpicture}
\end{document}

规律：合并后顶点不存在重复的操作数

有向无环图描述表达式的解题步骤：

把各个操作数不重复地排成一排；
标出各个运算符的生效顺序（先后顺序有点出入无所谓，主要为了不遗漏）；
按顺序加入运算符，注意“分层”；
从底向上逐层检查同层的运算符是否可以合并。

Example

例： $((a + b) * (b * (c + d)) + (c + d) * e) * ((c + d) * e)$

 

\begin{document}

\begin{tikzpicture}[scale=1.5, ultra thick,

every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},

arrow/.style={-latex},

]

\node at(0,0) (11) { $a$ };

\node at(2,0) (12) { $b$ };

\node at(4,0) (13) { $c$ };

\node at(6,0) (14) { $d$ };

\node at(8,0) (15) { $e$ };

\node at(1,1.5) (21) { $+$ };

\node[fill=green!20] at(4,1.5) (22) { $+$ };

\node[fill=green!20] at(5,1.5) (23) { $+$ };

\node[fill=green!20] at(6,1.5) (24) { $+$ };

\draw[arrow] (21)—(11);

\draw[arrow] (21)—(12);

\draw[arrow] (22)—(13);

\draw[arrow] (22)—(14);

\draw[arrow] (23)—(13);

\draw[arrow] (23)—(14);

\draw[arrow] (24)—(13);

\draw[arrow] (24)—(14);

\node at(2.5,3) (31) { $*$ };

\node[fill=blue!20] at(6,3) (32) { $*$ };

\node[fill=blue!20] at(7.5,3) (33) { $*$ };

\draw[arrow] (31)—(12);

\draw[arrow] (31)—(22);

\draw[arrow] (32)—(23);

\draw[arrow] (32)—(15);

\draw[arrow] (33)—(24);

\draw[arrow] (33)—(15);

\node at(2,4.5) (41) { $*$ };

\draw[arrow] (41)—(21);

\draw[arrow] (41)—(31);

\node at(4,6) (51) { $+$ };

\draw[arrow] (51)—(41);

\draw[arrow] (51)—(32);

\node at(6,7.5) (61) { $*$ };

\draw[arrow] (61)—(33);

\draw[arrow] (61)—(51);

\foreach \i in{0,1,…,4}{

  \draw[-, dashed, thick](-2,0.75+1.5*\i)--(10,0.75+1.5*\i);

}

\end{tikzpicture}

\end{document}

6.4.4 拓扑排序

拓扑排序.pdf

AOV网（Activity On Vertex NetWork，用顶点表示活动的网）：用 DAG 图（有向无环图）表示一个工程。顶点表示活动，有向边 $< V_{i}, V_{j} >$ 表示活动 $V_{i}$ 必须先于活动 $V_{j}$ 进行。

拓扑排序

BFS算法实现拓扑排序

最小入度实现拓扑排序

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：

每个顶点出现且只出现一次；
若顶点 A 在序列中排在顶点 B 的前面，则在图中不存在从顶点 B 到顶点 A 的路径。

或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后面。每个 AOV 网都有一个或多个拓扑排序序列。

拓扑排序的实现：

从 AOV 网中选择一个没有前驱（入度为0）的顶点并输出。
从网中删除该顶点和所有以它为起点的有向边，重新统计入度。
重复第1、2步直到当前的 AOV 网为空或当前网中不存在无前驱的顶点（存在回路）为止。

Example

例：“番茄炒蛋工程”的其中一个拓扑排序为：准备厨具，买菜，洗番茄，切番茄，打鸡蛋，下锅炒，吃。

代码实现拓扑排序（邻接表实现）：

indegree[ ]：当前顶点入度
print[ ]：拓扑序列
S：栈，用来保存度为0的顶点

//个人理解：初始状态下入度为0的所有结点入栈
	//栈顶结点出栈，该结点指向的所有结点入度-1，如有入度为0的结点，入栈
	//若可以遍历所有结点，则成功；否则图中存在回路
 
#define MaxVertexNum 100			//图中顶点数目最大值
 
typedef struct ArcNode{				//边表结点
	int adjvex;						//该弧所指向的顶点位置
	struct ArcNode *nextarc;		//指向下一条弧的指针
}ArcNode;
typedef struct VNode{				//顶点表结点
	VertexType data;				//顶点信息
	ArcNode *firstarc;				//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
	AdjList vertices;				//邻接表
	int vexnum,arcnum;			//图的顶点数和弧数
}Graph;						//Graph是以邻接表存储的图类型
 
// 对图G进行拓扑排序
bool TopologicalSort(Graph G){
	InitStack(S);					//初始化栈，存储入度为0的顶点
	for(int i=0; i<g.vexnum; i++){
        //检查当前入度为零的顶点，入度为0的顶点进栈
		if(indegree[i]==0)	Push(S,i);
	}
 
	int count=0;					//计数，记录当前已经输出的顶点数
	while(!IsEmpty(S)){				//栈不空，则存在入度为0的顶点
		Pop(S,i);					//栈顶元素出栈（弹出栈顶元素，并用i返回）
		print[count++]=i;			//记录拓扑序列
		for(p=G.vertices[i].firstarc; p; p=p->nextarc){
			//将所有i指向的顶点的入度减1，并将入度为0的顶点压入栈
			v= p->adjvex;
			if((--indegree[v])==0)	Push(S,v);	//入度为0，则入栈
		}
	}//while
	if(count<G.vexnum)	return false;				//排序失败，有向图中存在回路
	else	return true;				//排序成功
}

时间复杂度

邻接表： $O (∣ V ∣ + ∣ E ∣)$ ，每条顶点和边都需要处理一次
邻接矩阵： $O (∣ V ∣^{2})$

DFS算法实现拓扑排序（综合题第6题）

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){		// 对图G进行深度遍历
	for(v=0; v<G.vexnum; v++)	//初始化标记数组
		visited[v]=FALSE;
	time=0;
	for(v=0; v<G.vexnum; v++){
		if(!visited[v])
			DFS(G,v);
	}
}
 
void DFS(Graph G,int v){		//从顶点v出发，深度优先遍历图G
	visited[v]=TRUE;
	visit(v);
	for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v)){
		if(!visited[w])				//w是u的尚未访问的邻接顶点
			DFS(G,v);
	}
	time=time+1;
	finishTime[v]=time;
}
 
//对结束时间进行从大到小的排序，即可得到拓扑序列，代码自己参考快速排序写的
void QuickSort(int finishTime[], int low, int high){
	if(low<high){
		int pivotpos = Partition(finishTime[], low, high);
		i=0;
		print[i++]=G.vertices[pivotpos];
		QuickSort（finishTime[], low, pivotpos - 1);	//划分左子表
		QuickSort（finishTime[], pivotpos + 1, high);	//划分右子表
	}
}

逆拓扑排序

逆拓扑排序的实现：

从 AOV 网中选择一个没有后继（出度为0）的顶点并输出。
从网中删除该顶点和所有以它为终点的有向边。（逆邻接表）
重复第1、2步直到当前的 AOV 网为空。

代码实现：略

DFS算法实现逆拓扑排序：在顶点退栈之前输出

//个人理解：DFS算法实现深度优先遍历，在退栈时输出结点
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G){		// 对图G进行深度遍历
	for(v=0; v<G.vexnum; v++)	//初始化标记数组
		visited[v]=FALSE;
	for(v=0; v<G.vexnum; v++){
		if(!visited[v])
			DFS(G,v);
	}
}
 
void DFS(Graph G,int v){		//从顶点v出发，深度优先遍历图G
	visited[v]=TRUE;
	for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v)){
		if(!visited[w])				//w是u的尚未访问的邻接顶点
			DFS(G,v);
		print(v);				//输出顶点
	}
}

如何判断环路是否存在？
个人想法：~~设置访问数组来标识结点是否被访问过。如果访问已经访问过的，就说明出现环路~~（不对）

6.4.5 关键路径

关键路径.pdf

AOE 网：在带权有向图中，以顶点表示事件（某一刻瞬间发生），以有向边表示活动（持续发生），以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称 AOE 网 (Activity On Edge NetWork)。

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	every node/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-latex},
	]
	\node at(0,0) (1) {$V_{1}$};
	\node at(1.5,-2) (2) {$V_{2}$};
	\node at(3,0) (3) {$V_{3}$};
	\node at(5,0) (4) {$V_{4}$};
 
	\draw[arrow, red] (1)--(2)node[midway, below left, font=\Large, draw=none]{$a_{1}=2$};
	\draw[arrow] (1)--(3)node[midway, above, font=\Large, draw=none]{$a_{2}=1$};
	\draw[arrow, red] (2)--(3)node[midway, below right, font=\Large, draw=none]{$a_{3}=3$};
	\draw[arrow, red] (3)--(4)node[midway, above, font=\Large, draw=none]{$a_{4}=2$};
	\end{tikzpicture}
\end{document}

AOE网具有以下两个性质：

只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。

术语：

在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），它表示整个工程的开始；
在 AOE 网中仅有一个出度为 0 的顶点，称为结束顶点（汇点），它表示整个工程的结束。
从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
事件 $v_{k}$ 的最早发生时间 $v e (k)$ ：决定了所有从 $v_{k}$ 开始的活动能够开工的最早时间。
事件 $v_{k}$ 的最迟发生时间 $v l (k)$ ：它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
活动 $a_{i}$ 的最早开始时间 $e (i)$ ：指该活动弧的起点所表示的事件的最早发生时间。
活动 $a_{i}$ 的最迟开始时间 $l (i)$ ：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
活动 $a_{i}$ 的时间余量： $d (i) = l (i) - e (i)$ 表示在不增加完成整个工程所需总时间的情况下，活动 $a_{i}$ 可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成， $d (i) = 0$ 即 $l (i) = e (i)$ 的活动 $a_{i}$ 是关键活动，由关键活动组成的路径就是关键路径。

求关键路径的步骤：

求所有事件的最早发生时间 $v e ()$ ：按拓扑排序序列，依次求各个顶点的 $v e (k)$ ，

$v e (源点) = 0$ ， $v e (k) = M a x {v e (j) + W e i g h t (v_{j}, v_{k})}$ ， $v_{j}$ 为 $v_{k}$ 的任意前驱
求所有事件的最迟发生时间 $v l ()$ ：按逆拓扑排序序列，依次求各个顶点的 $v l (k)$ ，

$v l (汇点) = v e (汇点)$ ， $v l (k) = M in {v l (j) - W e i g h t (v_{k}, v_{j})}$ ， $v_{j}$ 为 $v_{k}$ 的任意后继
求所有活动的最早发生时间 $e ()$ ：若边 $< v_{k}, v_{j} >$ 表示活动 $a_{i}$ ，则有 $e (i) = v e (k)$
求所有活动的最迟发生时间 $l ()$ ：若边 $< v_{k}, v_{j} >$ 表示活动 $a_{i}$ ，则有 $l (i) = v l (j) - W e i g h t (v_{k}, v_{j})$
求所有活动的时间余量 $d ()$ ： $d (i) = l (i) - e (i)$

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick,
	vertex/.style={draw=black, circle, very thick,font =\huge, minimum size=3em},
	arrow/.style={-latex},
	]
	\node[vertex] at(0,0) (1) {$V_{1}$};
	\node[vertex] at(2,2) (2) {$V_{2}$};
	\node[vertex] at(2,-2) (3) {$V_{3}$};
	\node[vertex] at(4,0) (4) {$V_{4}$};
	\node[vertex] at(5,2) (5) {$V_{5}$};
	\node[vertex] at(7,0) (6) {$V_{6}$};
 
	\node [below of = 1, font=\Large] {0,0};
	\node [below of = 2, font=\Large] {3,4};
	\node [below of = 3, font=\Large] {2,2};
	\node [below of = 4, font=\Large] {6,6};
	\node [below of = 5, font=\Large] {6,7};
	\node [below of = 6, font=\Large] {8,8};
 
	\draw[arrow] (1)--(2)node[midway, left, font=\large]{$a_{1}=3$};
	\draw[arrow, red] (1)--(3)node[midway, left, font=\large, black]{$a_{2}=2$};
	\draw[arrow] (2)--(4)node[midway, left, font=\large]{$a_{3}=2$};
	\draw[arrow] (2)--(5)node[midway, above, font=\large]{$a_{4}=3$};
	\draw[arrow, red] (3)--(4)node[midway, left, font=\large, black]{$a_{5}=4$};
	\draw[arrow] (3)--(6)node[midway, below, font=\large]{$a_{6}=3$};
	\draw[arrow, red] (4)--(6)node[midway, above, font=\large, black]{$a_{7}=2$};
	\draw[arrow] (5)--(6)node[midway, right, font=\large]{$a_{8}=1$};
	\end{tikzpicture}
\end{document}

求解过程如下：

拓扑序列为： $V_{1}, V_{3}, V_{2}, V_{5}, V_{4}, V_{6}$ ， $V (1) = 0$ ， $V (3) = 2$ ， $V (2) = 3$ ， $V (5) = 6$ ， $V (4) = 6$ ， $V (6) = 8$
逆拓扑序列为： $V_{6}, V_{5}, V_{4}, V_{2}, V_{3}, V_{1}$ ， $V (6) = 8$ ， $V (5) = 7$ ， $V (4) = 6$ ， $V (2) = 4$ ， $V (3) = 2$ ， $V (1) = 0$

	$V_{1}$	$V_{2}$	$V_{3}$	$V_{4}$	$V_{5}$	$V_{6}$
$v e (k)$	0	3	2	6	6	8
$v l (k)$	0	4	2	6	7	8

	$a_{1}$	$a_{3}$	$a_{4}$	$a_{5}$	$a_{6}$	$a_{7}$	$a_{8}$
$e (k)$	0	3	3	2	2	6	6
$l (k)$	1	4	4	2	5	6	7
$d (k)$	1	1	1	0	3	0	1

关键活动、关键路径的特性：

若关键活动耗时增加，则整个工程的工期将增长。
缩短关键活动的时间，可以缩短整个工程的工期。
当缩短到一定程度时，关键活动可能会变成非关键活动。
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

6.4.6 本节习题精选

选择题：题目、答案

综合题：题目、答案

总结

各种图算法的时间复杂度

	邻接矩阵	邻接表
Prim算法	$O (n^{2})$	——
Kruskal算法	——	$e lo g_{2} e$
Dijkstra算法	$O (n^{2})$	——
Floyd算法	$O (n^{3})$	——
DFS算法	$O (n^{2})$	$O (n + e)$
BFS算法	$O (n^{2})$	$O (n + e)$
拓扑排序	$O (n^{2})$	$O (n + e)$
逆拓扑排序	$O (n^{2})$	$O (n + e)$

我的 Obsidian 知识库

探索

第6章图

6.1 图的基本概念

6.1.2 本节习题精选

6.2 图的存储

6.2.1 邻接矩阵法

邻接矩阵存储无权图

邻接矩阵法存储带权图

6.2.2 邻接表

6.2.3 十字链表、临接多重表

十字链表

邻接多重表

四种存储方法比较

6.2.4 图的基本操作

6.2.6 本节习题精选

6.3 图的遍历

6.3.1 广度优先遍历BFS

6.3.2 深度优先遍历DFS

图的遍历与图的连通性

6.3.4 本节习题精选

6.4 图的应用

6.4.1 最小生成树

Prim算法

Kruskal算法

6.4.2 最短路径

单源最短路径问题——BFS算法

单源最短路径问题——Dijkstra算法

各顶点间的最短路径问题——Floyd算法

最短路径算法比较

6.4.3 有向无环图描述表达式

6.4.4 拓扑排序

拓扑排序

逆拓扑排序

6.4.5 关键路径

6.4.6 本节习题精选

总结

关系图谱

目录

反向链接

我的 Obsidian 知识库

探索

第6章 图

6.1 图的基本概念

6.1.2 本节习题精选

6.2 图的存储

6.2.1 邻接矩阵法

邻接矩阵存储无权图

邻接矩阵法存储带权图

6.2.2 邻接表

6.2.3 十字链表、临接多重表

十字链表

邻接多重表

四种存储方法比较

6.2.4 图的基本操作

6.2.6 本节习题精选

6.3 图的遍历

6.3.1 广度优先遍历BFS

6.3.2 深度优先遍历DFS

图的遍历与图的连通性

6.3.4 本节习题精选

6.4 图的应用

6.4.1 最小生成树

Prim算法

Kruskal算法

6.4.2 最短路径

单源最短路径问题——BFS算法

单源最短路径问题——Dijkstra算法

各顶点间的最短路径问题——Floyd算法

最短路径算法比较

6.4.3 有向无环图描述表达式

6.4.4 拓扑排序

拓扑排序

逆拓扑排序

6.4.5 关键路径

6.4.6 本节习题精选

总结

关系图谱

目录

反向链接

第6章图