一、基本定义与性质

图由两个集合 V 和 E 组成，记为 G = （V，E）， V 是顶点集，E 是边集

  • 有向图： 顶点对 有序，意为一条由点 x 指向点 y 的有向边。 和 是不同的两条边
    • 在 中，x 是始点 / 弧尾，y 是终点 / 弧头
  • 无向图： 顶点对(x, y) 无序，(x, y) 和 (y, x) 指的是同一条

基本术语

n 表示顶点数，e 表示边数

  • 子图： 有一个图的顶点全部都是另一个图的顶点，边也全都是另一个图的边，这个图叫做另一个图的子图
  • 完全图
    • 无向完全图： 有 n(n - 1) / 2 条边的无向图，说人话就是每两个顶点之间都有边
    • 有向完全图： 有 n(n - 1) 条边的有向图，说人话就是从任何一个顶点都能到任何一个其他顶点
  • 稀疏图和稠密图： 边少的就是稀疏图，边多的就是稠密图
  • 网： 带权图
  • 邻接点： 无向图中，(v, v’) 表示 v 与 v’ 互为邻接点，v 和 v’ 相邻接，边 (v, v’) 依附于顶点 v 和 v’，边 (v, v’) 和顶点 v v’ 相关联
  • 度： 和顶点相关联的边的个数，记作TD(v)
    • 入度： 有向图中从该点发出的边的个数，记作ID(v)
    • 出度： 有向图中从该点进入的边的个数，记作OD(v)
    • TD(v) = ID(v) + OD(v)
    • 度是边数的两倍
  • 路径长度： 一条路径上边的个数
  • 回路 / 环： 起点终点相同
  • 简单路径： 顶点不重复的路径
  • 简单回路 / 简单环： 起点终点相同，其他不出现重复顶点的回路
  • 连通： v 可以到达 v’，则称这两点连通
  • 连通图： 图中任意两点连通
  • 连通分量： 无向图中极大连通子图
  • 强连通图： 有向图中，从任意一个点可以到任意另一个点
  • 强连通分量： 有向图中极大强连通子图
  • 连通图的生成树： 含有图中全部顶点，但是边数减1，任意添加一条边，必定构成环
  • 有向树： 一个顶点入度为0，其余顶点入度为1

二、图的存储

1. 邻接矩阵

二维数组，G[i][j] 代表 i 和 j 点的边情况

  • 无向图中，G[i][j] = 1说明有边，G[i][j] = 0说明无边
  • 有向图中，G[i][j] = w说明有边，权值是w，G[i][j] = ∞说明无边
#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;
typedef int ArcType;
typedef struct
{
	VerTexType vexs[MVNum]; // 存顶点
	ArcType arcs[MVNum][MVNum]; // 存边
	int vexnum, arcnum; // 存顶点数和边数
}AMGraph;

2. 邻接表

链式存储结构，分为表头结点表和边表

  • 表头结点表：包含数据和指针，数据表示存的是哪个顶点，指针指向这个顶点相邻的边表集
  • 边表：包含数据，邻接点，指针，数据存储权值，邻接点存储是哪个点和本表的顶点相邻，指针指向下一个和顶点相邻的结点
#define MVNum 100

typedef struct ArcNode // 边表
{
	int adjvex;
	struct ArcNode *nextarc;
	OtherInfo info;
}ArcNode;

typedef struct VNode // 表头结点表
{
	VerTexType data;
	ArcNode *firstarc;
}VNode, AdjList[MVNum];

typedef struct
{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

3. 十字链表

个人觉得可以理解为有向图的邻接矩阵按邻接表的方式存储
看图自己理解吧~感觉考到的概率不大

4. 邻接矩阵和邻接表存储的比较

（1） 邻接矩阵

  • 优点：方便
  • 缺点：图稍微大一点就存不下

（2） 邻接表

  • 优点：可以存下大图
  • 缺点：麻烦，相对来说没有邻接矩阵直观（其实是本菜狗太弱了）

三、图的遍历

1. 深度优先搜索 DFS

（1） 思路

不撞南墙不回头，只要有没有走过的点就接着走，一条路走到底，直到不能走了就退回来，找到下一条能走的路
举个栗子

深搜的结果是：v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7

（2） 算法实现

邻接矩阵存储图

时间复杂度： O(V^2^)

void DFS_AM(AMGraph G, int v)
{
	cout << v; // 遍历过v点
	visited[v] = true; // 标记v已被遍历
	for (int v = 0; w < G.vexnum; w ++ ) // 遍历图中所有点
		if ((G.arcs[v][w] != 0) && (!visited[w])) DFS_AM(G, w); // 该点没有被遍历过 且 该点和v之间有边 就递归遍历该点
}

邻接表存储图

时间复杂度： O(V + E)

void DFS_AL(ALGraph G, int v)
{
	cout << v; // 遍历过v点
	visited[v] = true; // 标记v已被遍历过
	p = G.vertices[v].firstarc; // 和v第一个相邻的点记作p
	while (p != NULL) // 只要p存在就进入循环
	{
		w = p->adjvex; // w是p的值
		if (!visited[w]) DFS_AL(G, w); // 只要w点没被遍历过 就递归遍历该点
		p = p->nextarc; // p指向下一个边结点
	}
}

2. 广度优先搜索 BFS

（1） 思路

知道起点之后，第一次遍历起点，第二次遍历所有与起点距离为1的点，第三次遍历所有与起点距离为2的点，以此类推~
举个栗子

还是这个图
广搜的结果是：v1 -> v2 -> v3 -> v4 -> v5 -> v6 -> v7 -> v8

（2） 算法实现

邻接矩阵存储图

时间复杂度： O(V^2^)

void BFS_AM(Graph_AM G, int v)
{
	cout << v;
	visited[v] = true;
	int queue[MAXSIZE]; // 创建队列 这里因为考试可能不能写c++ 就用数组模拟队列啦
	int head = 0, rear = 0; // 清空队列
	queue[rear ++ ] = v; // 把点v存进队列
	while (head != rear)
	{
		int u = queue[head ++ ]; // 队头元素出队并保存
		for (i = 0; i < G->VexNum; i ++ ) // 遍历所有点
		{
			if ((G.arcs[u][i] != 0) && (!visited[i])) // 该点没有被遍历过 且 该点和v之间有边 就遍历该点
			{
				cout << i;
				visited[i] = true;
				queue[rear ++ ] = i;
			}
		}
	}
}

邻接表存储图

时间复杂度： O(V + E)

void BFS_AL(Graph_AL G, int v)
{
	cout << v; // 遍历过该点
	visited[v] = true; // 标记
	ArcNode queue[MAXSIZE]; // 建立队列
	int head = 0, rear = 0; // 队列初始化
	queue[rear ++ ] = G.vertices[v].firstarc; // 把目前遍历的这个点的第一个相邻点入队
	while (head != rear) // 队列不空就循环
	{
		ArcNode u = queue[head ++ ]; // 取出队头并删去
		while (u)
		{
			if (!visited[u->adjvex]) // 只要没遍历过就立刻遍历
             {
				cout << u->adjvex;
				visited[u->adjvex] = true;
				queue[rear ++ ] = G.vertices[u->adjvex].FirstEdge; // 把与目前遍历的点相邻的第一个点存进去
			}
			u = u->Next; // 遍历下一个
		}
	}
}

四、图的应用

1. 最小生成树

在一个连通网的所有生成树里权值之和最小的就是最小生成树。

（1） 普里姆 （Prim）算法

A. 思路

从起点开始，每次循环中遍历所有点，选择还没有加入最小生成树且与生成树集合距离最短的点加入生成树，直到所有点都加入生成树中

B. 算法实现

挖坑~

（2） 克鲁斯卡尔（Kruskal）算法

A. 思路

把所有边的权值按照从小到大排序，每次选择当前最小的，如果这条边连接的两个顶点有至少一个没有遍历过，就把这条边加入生成树，直到所有顶点都在生成树里

B. 算法实现

继续挖坑~

2. 关键路径

（1） AOE网

AOE网——带权有向无环图

  • 边：活动
  • 顶点：事件
  • 权值：活动持续的时间

基本概念

  • 源点： 入度为0的点
  • 汇点： 出度为0的点
  • 带权路径长度： 一条路径上各边权值之和
  • 关键路径： 从源点到汇点带权路径长度最大的路径
  • 关键活动： 关键路径上的活动
  • 事件 v~i~ 最早发生时间 ve(i)
    从源点到 v~i~ 的最长路径长度
    ve(0) = 0
    ve(i) = max{ve(k) + w~k,i~}
  • 事件 v~i~ 最迟发生时间 vl(i)
    不延误任何后继事件的最迟发生时间
    vl(i) = min{vl(k) - w~i,k~}
  • 活动 a~i~ = 最早开始时间 e(i)
    等于事件 v~j~ 的最早发生时间
    e(i) = ve(i)
  • 活动 a~i~ = 最晚开始时间 l(i)
    等于事件 v~k~ 的最迟发生时间减活动持续时间
    l(i) = vl(k) - w~i,k~
  • ==当一个活动的最早发生时间等于最晚发生时间，那么说明这个活动是关键活动==

    （3） 关键路径

    A. 思路

    没有思路，找到最长的一条路径，然后凭直觉做吧

    B. 算法实现

    再挖一个