数据结构图论入门_无向连通图

图论基本知识

  图（Graph）可以简单表示为二元组G=<V,E>,其中V称为顶点（vertex）集合，E称为边（edge）的集合。图可分为以下几种类型

• 1.有向图：E中的每一条边都具有方向的图。
  
• 2.无向图：E中每一条边不带方向，称为无向图。
  
• 3.混合图：E中一些边不带方向，另一些边带有方向。
  
• 4.多重图：含有平行边或自环的图。（有向图、无向图和混合图都属于简单图）
  
• 5.边的表示方法

• 无向图的边叫无向边，用无序偶表示，$(v_i,v_j)$表示$i$结点与$j$结点之间的边，因为没有方向，所以$(v_i,v_j)\iff (v_j,v_i)$
• 有向图的边叫有向边，用有序偶表示，$<v_i,v_j>$表示从$i$指向$j$的边或弧，$v_i$称为始点，$v_j$称为终端点，$(v_i,v_j)\nLeftrightarrow (v_j,v_i)$,称$v_i$邻接至$v_j$,$v_j$邻接自$v_i$

• 5.顶点的度

• 无向图：无向图的度为与该顶点相关联的边的数目，各顶点的度数和等于边的数目的两倍。定义图中顶点数目为图的阶，若一个无向图中，每个顶点的度均为$n-1$,称该图为$n$阶无向完全图，其边的总数为$C_n^2=\frac{n(n-1)}{2}$。
• 有向图：有向图的度分入度和出度，入度指终端点指向该点的弧的数目，出度指以该点为始点的弧的数目。若$n$阶有向图每个顶点的入度等于出度等于$n-1$,称该图为有向完全图，其弧的数目为$n(n-1)$。

• 6.图的连通性

• 无向图：若从顶点$v_i$到顶点$v_j$有路径，则称$v_i$和$v_j$是连通的。若该图中任意两个顶点都是连通的，则称该图是连通图。
• 有向图：在有向图中，略去所有边的方向形成的无向图如果是连通图，则该有向图是弱连通图，若在方向约束下，有向图中任意两个顶点互相可达，则称该有向图为强连通图。注：图的强弱连通只针对有向图。弱连通图可以理解为该图只是在表面上看起来有些“线”将顶点都连接了起来，但是由于有方向，该图并不能实现任意两个点互相可达。
• 连通分量：无向图中，顶点之间的连通关系是一个等价关系，该等价关系将顶点集合划分的等价类成为连通分支即连通分量，这些等价类的数目称为连通分支数。可以这样理解，同一个连通分支中的所有顶点可以互相到达，任意两个连通分支中的两个顶点不能互相到达。

• 7.生成树

• 生成树：一个$n$阶连通图的生成树是一个极小连通子图（包含最少的边的连通图），生成树包含$n$个顶点，$n-1$条边，显然，一个连通图的生成树可能不唯一，其中所有边权值和最小的生成树称为最小生成树。在生成树中添加任意一条边，必然形成回路。
• 最小生成树求解算法：Prim算法、Kluskal算法

• 8.图的存储结构
  邻接矩阵
  邻接矩阵：用一个矩阵存储顶点之间是否直接有边相连，对于n阶图，设n阶方阵$a_{ij}$为该图的邻接矩阵，则
  $$a_{ij}=\{\begin{array}{r}1,v_i邻接至v_j\\ 0,v_i不邻接v_j\end{array}$$
  例如如下无向图
  

邻接矩阵为
$$A=\left[\begin{array}{ccccc}0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 1& 1\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\end{array}\right]$$

邻接矩阵代码实现

#define MAX //最大顶点数
typedef struct
{
	int n;//n为实际顶点数
	ElemTp a[MAX][MAX];//邻接矩阵
	//这里的ElemTp为可选数据类型，若只是简单图，即没有边权值
	//则a[i][j]=1表示i和j之间有边存在，为0表示无边存在
	//其他图的邻接矩阵元素可以存储i到j的边权值，等
}Graph;
1
2
3
4
5
6
7
8
9

邻接表
  使用链表对邻接矩阵进行改进，每个顶点只保存所有直接与它相连的顶点，所有这些顶点通过链表来动态保存。那么对于$n$阶无向图，需要$n$个头结点，每个结点后链接直接与其相连的顶点。例如图：

（1）首先可以看到，与0结点直接相连的有1,3，那么把1,3号结点插入到0结点的头结点后面去(1,3的顺序是任意的，后面所有表结点皆是，表结点之间的链接不表示任何关系，只关心该结点链接在哪个头结点之后)
（2）然后按此方法可以发现1后面有0,2，4；2后面有1,3，4；3后面有0,2；4后面有1,2；建立邻接表如下所示

邻接表代码实现

//头结点
typedef struct
{
	//顶点数据（可选）
	ElemTp data;
	InfoTp info;//顶点信息，可选
	int i;//顶点下标
	ArcNode *firstarc;//第一邻接的表结点
}HNode;

//表结点
typedef struct node
{
	double w;//边或弧的权重，可选
	InfoTp info;//边或弧的信息，可选
	int j;//邻接点的下标
	struct node *nextarc;//下一表结点
}ArcNode;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19