本文共 6294 字，大约阅读时间需要 20 分钟。

作为数据结构的课程笔记，以便查阅。如有出错的地方，还请多多指正！

基本概念

• 图 (Graph)： G = { V , E } G=\{V,E\} G={
  V,E}，$V(G)$ 为顶点 (Vertex) 的非空有限集，$E(G)$ 为边 $(v,w)$ / 弧 $<v,w>$ 的有限集合
  • 有向图 (Digraph)、无向图 (Undigraph)
• 有向完全图——$n$ 个顶点的有向图最大边数是 $n(n-1)$
• 无向完全图——$n$ 个顶点的无向图最大边数是 $n(n-1)/2$
• 权——与图的边或弧相关的数
• 网——带权的图
• 子图——图 $G(V,VR)$ 和图 $G^{\prime }(V^{\prime },V{R}^{\prime })$, 满足：$V^{\prime }\subseteq V$ 并且 $V{R}^{\prime }\subseteq VR$
• 邻接点
• 顶点的度
  • 无向图中，顶点的度为与每个顶点相连的边数
  • 有向图中，顶点的度分成入度与出度；入度：以该顶点为头的弧的数目；出度：以该顶点为尾的弧的数目
• 路径——路径是顶点的序列 V = { V i 0 , V i 1 , … … V i n } V=\{V_{i_0},V_{i_1},……V_{i_n}\} V={
  Vi0​​,Vi1​​,……Vin​​}
• 路径长度——沿路径边的数目或沿路径各边权值之和
• 回路——第一个顶点和最后一个顶点相同的路径
• 简单路径——序列中顶点不重复出现的路径
• 简单回路——除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路
• 连通——从顶点 $V$ 到顶点 $W$ 有一条路径，则说 $V$ 和 $W$ 是连通的
• 连通图——图中任意两个顶点都是连通的图
• 连通分量——无向图的极大连通子图
• 强连通图——有向图中，每一对 $V_i,V_j\in V$, $V_i\ne V_j$, 从 $V_i$ 到 $V_j$ 和从 $V_j$ 到 $V_i$ 都存在路径
• 强连通分量

图的存储

邻接矩阵

• 适合于稠密图
• 无权图：
  $$\text{AdjMatrix[i][j]}=\{\begin{array}{rl}1& (v_i,v_j)或<v_i,v_j>\in E\\ 0& else\end{array}$$
• 有权图：
  $$\text{AdjMatrix[i][j]}=\{\begin{array}{rl}{w}_{ij}& (v_i,v_j)或<v_i,v_j>\in E\\ \infty & else\end{array}$$

无向图的邻接矩阵对称，可压缩存储 (对称矩阵可以只存上/下三角元素)

#define MAX_VERTEX_NUM 50#define INFINITY 10000typedef enum {   	unDirectedGraph,	directedGraph,}GraphType_e;typedef int AdjacentMatrixWeightType_t;typedef int AdjacentMatrixDataType_t;typedef struct {   	int vexNum;	int arcNum;	GraphType_e type;	AdjacentMatrixDataType_t vex[MAX_VERTEX_NUM];	AdjacentMatrixWeightType_t arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵}AdjacentMatrix_t, *pAdjacentMatrix_t;//
   
    typedef struct {   	int head;	int tail;	AdjacentMatrixWeightType_t weight;}Edge_t, *pEdge_t;
   

Status_e Create_graph(pAdjacentMatrix_t pgraph, int vex_num, GraphType_e type){   	pgraph->vexNum = vex_num;	pgraph->arcNum = 0;	pgraph->type = type;	for (int i = 0; i < pgraph->vexNum; ++i)	{   		for (int j = 0; j < pgraph->vexNum; ++j)		{   			pgraph->arc[i][j] = (i == j) ? 0 : INFINITY;		}	}	return ok;}Status_e Insert_edge(pAdjacentMatrix_t pgraph, pEdge_t edge){   	(pgraph->arcNum)++;	pgraph->arc[edge->tail][edge->head] = edge->weight;	if (pgraph->type == unDirectedGraph)	{   		pgraph->arc[edge->head][edge->tail] = edge->weight;	}	return ok;}int Locate_vex(pAdjacentMatrix_t pgraph, AdjacentMatrixDataType_t data){   	for (int i = 0; i < pgraph->vexNum; ++i)	{   		if (pgraph->vex[i] == data)		{   			return i;		}	}	return -1;}/*Input format:Nv Nedata1data2...tail head weight...*/Status_e Build_graph(pAdjacentMatrix_t pgraph, GraphType_e type){   	int vex_num;	int arc_num;	Edge_t edge;	scanf_s("%d %d", &vex_num, &arc_num);	Create_graph(pgraph, vex_num, type);	for (int i = 0; i < vex_num; ++i)	{   		scanf_s("%d", &(pgraph->vex[i]));	}	for (int i = 0; i < arc_num; ++i)	{   		AdjacentMatrixDataType_t data_tail, data_head;		scanf_s("%d %d %d", &(data_tail), &(data_head), &(edge.weight));		//scanf_s("%d %d %d", &(edge.tail), &(edge.head), &(edge.weight));		edge.tail = Locate_vex(pgraph, data_tail);		edge.head = Locate_vex(pgraph, data_head);		if (-1 == edge.tail			|| -1 == edge.head)		{   			return err;		}		Insert_edge(pgraph, &edge);	}	return ok;}

邻接表

• 适用于稀疏图
• 找邻接点容易，找逆邻接点难；求出度容易，求入度难
  

#define MAX_VERTEX_NUM 50#define INFINITY 10000typedef enum {   	unDirectedGraph,	directedGraph,}GraphType_e;typedef int AdjacentListWeightType_t;typedef int AdjacentListDataType_t;typedef struct {   	AdjacentListDataType_t data;	pArcNode_t firstEdge;}VexNode_t, *pVexNode_t;typedef struct ArcNode{    //弧结点	struct ArcNode* nextEdge;	int head;//邻接点下标	AdjacentListWeightType_t weight;}ArcNode_t, *pArcNode_t;typedef struct {   	VexNode_t vex[MAX_VERTEX_NUM];	int vexNum;	int arcNum;	GraphType_e type;}AdjacentList_t, *pAdjacentList_t;//
   
    typedef struct {   	int head;	int tail;	AdjacentListWeightType_t weight;}Edge_t, * pEdge_t;
   

Status_e Create_graph(pAdjacentList_t pgraph, int vex_num, GraphType_e type){   	pgraph->vexNum = vex_num;	pgraph->arcNum = 0;	pgraph->type = type;	for (int i = 0; i < vex_num; ++i)	{   		pgraph->vex[i].firstEdge = NULL;//要先初始化为NULL	}	return ok;}Status_e Insert_edge(pAdjacentList_t pgraph, pEdge_t edge){   	pArcNode_t parc_node = (pArcNode_t)malloc(sizeof(ArcNode_t));	parc_node->nextEdge = pgraph->vex[edge->tail].firstEdge;	pgraph->vex[edge->tail].firstEdge = parc_node;	parc_node->weight = edge->weight;	parc_node->head = edge->head;	(pgraph->arcNum)++;	if (pgraph->type == unDirectedGraph)	{   		parc_node = (pArcNode_t)malloc(sizeof(ArcNode_t));		parc_node->nextEdge = pgraph->vex[edge->head].firstEdge;		pgraph->vex[edge->head].firstEdge = parc_node;		parc_node->weight = edge->weight;		parc_node->head = edge->tail;	}	return ok;}int Locate_vex(pAdjacentList_t pgraph, AdjacentListDataType_t data){   	for (int i = 0; i < pgraph->vexNum; ++i)	{   		if (pgraph->vex[i].data == data)		{   			return i;		}	}	return -1;}/*Input format:Nv Nedata1data2...tail head weight...*/Status_e Build_graph(pAdjacentList_t pgraph, GraphType_e type){   	int vex_num, arc_num;	Edge_t edge;	scanf_s("%d %d", &vex_num, &arc_num);	Create_graph(pgraph, vex_num, type);	for (int i = 0; i < vex_num; ++i)	{   		scanf_s("%d", &(pgraph->vex[i].data));	}	for (int i = 0; i < arc_num; ++i)	{   		AdjacentListDataType_t data_tail, data_head;		scanf_s("%d %d %d", &(data_tail), &(data_head), &(edge.weight));		//scanf_s("%d %d %d", &(edge.tail), &(edge.head), &(edge.weight));		edge.tail = Locate_vex(pgraph, data_tail);		edge.head = Locate_vex(pgraph, data_head);		if (-1 == edge.tail			|| -1 == edge.head)		{   			return err;		}		Insert_edge(pgraph, &edge);	}	return ok;}

逆邻接表

• 找邻接点难，找逆邻接点容易
• 求出度难，求入度容易
  

十字链表

• 结合了邻接表和逆邻接表
• 顶点结点：
  firstIn表示指向以该顶点为弧头的第一个弧节点。而firstOut则表示指向以该顶点为弧尾的第一个弧节点
• 弧结点
  tailVex表示弧尾，headVex表示弧头。hLink指向弧头相同的下一条弧，tLink指向弧尾相同的下一条弧弧头相同的弧都在同一链表上，弧尾相同的弧也都在同一链表上
  

$T(n)$

• 在涉及全图的问题中，$O(n+e)$ 为最优；如果是稠密图，$O(n^2)$ 也为最优