数据结构,图_数据结构无向图「建议收藏」

数据结构（五） – 图

= LUOFANG SHIJIE + 网上的小伙伴见解 + 个人见解

侵删！

“首当其冲”

在有向图中，顶点用尖括号，在无向图中，顶点用圆括号

例如<x,y>和<y,x>是不相同的，但是(x,y)和(y,x)是相同的。

在图中，一般用n来表示顶点的数目，用e来表示边的数目

无向完全图和有向完全图：

无向完全图：边的数目为n(n-1)/2

有向完全图：边的数目为n(n-1)

网：带权的图往往称为网

入度和出度：对于有向图而言的。在有向图中，所有顶点的入度和出度之和的1/2为图的边数

路径长度：是一条路径上通过边的条数

连通、连通图、连通分量：有路径——连通在图中，任一顶点都有路径——连通图

无向图中的极大连通子图——连通分量

强连通图和强连通分量：是相对于有向图而言的。

连通图的生成树：一个极小连通子图，他包含图中的所有顶点，但是只有足以构成一棵树的n-1条边。

如果一个图有n个顶点和小于n-1条边，那一定是非连通图，如果他多于n-1条边，那一定有环。

有向树和生成森林：只有一个点的入度为0，其余点的入度均为1的有向图称为有向树

生成森林：由若干棵有向树组成，且互不相交

图的存储结构

邻接矩阵表示法

若图是网，则可以这样表示：

#define MaxInt 32767
#define MVNum 100
typedef char VerTexType;	//假设顶点的类型是char型
typedef int ArcType;		//假设边的权值类型是int
typedef struct
{
	VerTexType vexs[MVNum];
	ArcTexType arcs[MVNum][MVNum];
	int arcnum,vexnum;
}AMGraph;

采用邻接矩阵法创建无向网：时间复杂度0(n²)

Status CreatUND(AMGraph &G)
{
	cin>>G.arcnum>>G.vexnum;
	for(int i=0;i<vexnum;i++)  //依次输入顶点信息
		cin>>G.vexs[i];
	for(int i=0;i<vexnum;i++)
	{
		for(int j=0;j<vexnum;j++)
		{
			G.arcs[i][j]=MaxInt;
		}
	}
	for(int k=0;k<G.arcnum;k++)
	{
		cin>>v1>>v2>>w;  //输入一条边依附的顶点和权值
  		i=LocateVex(G,v1);
  		j=LocateVex(G,v2);
  		G.arcs[i][j]=w;
  		G.arcs[i][j]=G.arcs[j][i];	//无向网
	}
	return OK;
}