数据结构·图

图的基本概念

图的定义

• 定义
  • 图不能一个顶点也没有！
• 术语
  • 有向图
    • 注意弧头是终点，弧尾是起点
  • 无向图
  • 简单图、多重图
  • 完全图
    • 无向完全图
    • 有向完全图
  • 子图、生成子图
  • 连通、连通图和连通分量
    • 连通的
    • 连通图、非连通图
    • 连通分量（极大连通子图）
  • 强连通图、强连通分量
    • 强连通的
    • 强连通图
    • 强连通分量（极大强连通子图）
  • 生成树、生成森林
    • 生成树（连通图的极小连通子图）
    • 生成森林（非连通图各分量的生成树构成的森林）
  • 顶点的度、入度和出度
  • 边的权和网
    • 权值
    • 网（带权图）
  • 稠密图、稀疏图
  • 路径、路径长度和回路
  • 简单路径、简单回路
  • 距离
  • 有向树

图的存储及基本操作

邻接矩阵法

• 空间复杂度为$O(|V|^2)$

邻接表法

• 空间复杂度
  • 无向图$O(|V|+2|E|)$
  • 有向图$O(|V|+|E|)$

十字链表

• 顶点（顺序存储）
  • [data, firstin, firstout]
• 弧结点（链式存储）
  • [tailvex, headvex, hlink, tlink, (info)]
• 十字链表法存储有向图的一个示例

邻接多重表

• 顶点（顺序存储）
  • [data, firstedge]
• 弧结点（链式存储）
  • [ivex, ilink, jvex, jlink, (info)]

图的基本操作

十字链表法存储有向图的一个示例

#include <stdio.h>

struct edge;

struct vertex{
	char data;
	struct edge *firstin, *firstout;
};

struct edge {
	int tailvex, headvex;
	struct edge *hlink,*tlink;
	/* char *info; */
};

/* struct graph { */
/* 	struct vertex vex[4]; */
/* 	struct */
/* }; */

int main(){
	struct vertex my_graph[4];

	struct edge edge1, edge2, edge3, edge4, edge5, edge6, edge7;
	edge1.tailvex=2;
	edge1.headvex=0;
	edge1.hlink=&edge2;
	edge1.tlink=&edge5;
	edge2.tailvex=3;
	edge2.headvex=0;
	edge2.hlink=NULL;
	edge2.tlink=&edge3;
	edge3.tailvex=3;
	edge3.headvex=1;
	edge3.hlink=NULL;
	edge3.tlink=&edge4;
	edge4.tailvex=3;
	edge4.headvex=2;
	edge4.hlink=NULL;
	edge4.tlink=NULL;
	edge5.tailvex=2;
	edge5.headvex=3;
	edge5.hlink=NULL;
	edge5.tlink=NULL;
	edge6.tailvex=0;
	edge6.headvex=2;
	edge6.hlink=&edge4;
	edge6.tlink=NULL;
	edge7.tailvex=0;
	edge7.headvex=1;
	edge7.hlink=&edge3;
	edge7.tlink=&edge6;

	my_graph[0].data='A';
	my_graph[0].firstin=&edge1;
	my_graph[0].firstout=&edge7;
	my_graph[1].data='B';
	my_graph[1].firstin=&edge7;
	my_graph[1].firstout=NULL;
	my_graph[2].data='C';
	my_graph[2].firstin=&edge6;
	my_graph[2].firstout=&edge1;
	my_graph[3].data='A';
	my_graph[3].firstin=&edge5;
	my_graph[3].firstout=&edge2;

	/* printf("edge3->tlink: %p", edge3.tlink); */
	/* printf("edge3->hlink: %p", edge3.hlink); */

	for (int i=0;i<4;i++){
		printf("[");
		int edges[4];
		for (int j=0;j<4;j++)
			edges[j]=0;
		struct edge *next=my_graph[i].firstout;
		/* int j=0; */
		while (next/*&&j<2*/) {
			/* printf("j: %d, next->tailvex: %d, next->headvex: %d\n", j, next->tailvex,next->headvex); */
			edges[next->headvex]=1;
			next=next->tlink;
			/* j++; */
		}
		for (int j=0;j<4;j++){
			printf("%d", edges[j]);
			if (j<3)
				printf(", ");
		}
		printf("]\n");
	}

	return 0;
}

图的遍历

BFS

• 算法思想
• 性能分析
  • 空间复杂度$O(|V|)$
  • 时间复杂度
    • 邻接表$O(|V|+|E|)$
    • 邻接矩阵$O(|V|^2)$
• BFS解决非带权图最短路径问题
• BFS生成树

DFS

• 算法思想
• 性能分析
  • 空间复杂度$O(|V|)$
  • 时间复杂度
    • 邻接表$O(|V|+|E|)$
    • 邻接矩阵$O(|V|^2)$
• DFS生成树和生成森林

图的遍历与图的连通性

图的应用

最小生成树

• 最小生成树的定义及性质
• Prim算法
  • 算法思想（点出发）
  • 性能
    • 时间复杂度$O(|V|^2)$
• Kruskal算法
  • 算法思想（边出发）
  • 性能
    • 时间复杂度$O(|E|\log_2|E|)$

最短路径

• 问题描述
• Dijkstra算法
  • 算法思想
  • 性能
    • 时间复杂度总为$O(|V|^2)$
  • 不允许带负权值
• Floyd算法
  • 算法思想
  • 性能
    • 时间复杂度为$O(|V|^3)$
  • 不允许负权值回路

有向无环图描述表达式

• 有向无环图的定义（DAG图）
• *咸鱼算法

拓扑排序

• AOV网
• 拓扑排序
  • 算法思想
  • 时间复杂度
    • 邻接表$O(|V|+|E|)$
    • 邻接矩阵$O(|V|^2)$
  • 逆拓扑排序

关键路径

• AOE网
• 关键路径
• 关键活动
• 算法