Fork me on GitHub

图的基本概念

图:由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

基本概念

注意:

  • 线性表中数据元素称为元素,树中称为结点,图中称为顶点。
  • 在图结构中,不允许没有顶点。
  • 在图中,任意两个顶点间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

各种图的定义

若顶点vi到vj之间的边没有方向,则称这条边为无向边,用无序偶对(vi,vj)来表示。如果图中任意两个顶点间的边都是无向边,则称该图为无向图

若顶点vi到vj之间的边有方向,则称这条边为有向边,也称为,用有序偶对<vi,vj> 来表示,其中vi称为弧尾,vj称为弧头。如果图中任意两个顶点间的边都是有向边,则称该图为有向图

简单图:不存在顶点到其自身的边,且同一条边不重复出现。

无向完全图:任意两个顶点之间都存在边。含有n个顶点的无向完全图有n(n-1)/2条边。

有向完全图:任意两个顶点之间都存在方向互为相反的弧。含有n个顶点的有向完全图有n*(n-1)条边。

对于有n个顶点e条边的图,无向图0 <= e <= n(n-1)/2,有向图0 <= e <= n*(n-1)

有很少条边或弧的图称为稀疏图,反之称为稠密图。(相对概念)

有些图的边或弧具有与它相关的数字,这种与图的边或弧相关的数叫做。这种带权的图通常称为

假设有两个图G1 = (V1,{E1}),G2 = (V2,{E2}),如果V2属于V1,E2属于E1,则称G2为G1的子图

图的顶点与边间的关系

对于无向图G = (V,{E}),如果边(v,v′) ∈E,则称顶点v和v′互为领接点,即v与v′相邻接。边(v,v′)依附于顶点v和v′,或者说(v,v′)与顶点v和v′相关联。顶点v的是相关联的边的数目,记为TD(v)

边数即为各顶点度数和的一半。

对于有向图G = (V,{E}),如果弧<v,v′>∈E,则称顶点v邻接到顶点v′,顶点v′邻接自顶点v。弧<v,v′>和顶点v,v′相关联。以顶点v为头的弧的数目称为v的入度,记为ID(v),顶点v为尾的弧的数目称为v的出度,记为OD(v)

TD(v) = ID(v) + OD(v)

路径的长度是路径上的边或弧的数目。

第一个顶点和最后一个顶点相同的路径称为回路。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路简单环

连通图相关术语

在无向图中,如果从顶点v到顶点v′有路径,则称v和v′是连通的。如果对于图中任意两个顶点vi,vj∈E,vi和vj都是连通的,则称G是连通图。(不一定闭合)

无向图中极大连通子图称为连通分量。注意:

  • 要是子图
  • 子图要是连通的
  • 连通子图含有极大顶点数
  • 具有极大顶点数的连通子图包含依附于这些顶点的所有边

在有向图中,如果对于每一对vi、vj∈V,vi≠vj,从vi到vj和从vj到vi都存在路径,则称G为强连通图。有向图中的极大连通子图称做有向图的强连通分量

连通图的生成树:一个极小的连通子图,它含有图中全部n个顶点,但只有足以构成一棵树的n-1条边。

如果一个图有n个顶点和小于n-1条边,则是非连通图,如果它多余n-1条边,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第二条路径。有n-1条边并不一定是生成树。

如果一个有向图恰有一个顶点的入度为0,其余顶点入度均为1,则是一棵有向树

一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。

图的抽象数据类型

mark

图的存储结构

邻接矩阵

用两个数组来表示图,一个一位数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

无向图的边数组是一个对称矩阵。

mark

第i行(列)的元素之和即为vi的度。

有向图:

mark

第i行各数之和为vi的出度。

第i列各数之和为vi的入度。

网图:

mark

结构代码

1
2
3
4
5
6
7
8
9
10
typedef char VertexType;//顶点类型
typedef int EdgeType;//边上权值类型
#define MAXVEX 100//最大顶点数
#define INFINITY 65535//用65535来代表∞
typedef struct
{
VertexType vexs[MAXVEX];//顶点表
EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵,可看作边表
int numVertexes,numEdges;//当前顶点数和边数
}MGraph;

创建邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void CreateMGraph (MGraph *G)
{
int i,j,k,w;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&G->numVertexes,&G->numEdges);
for (i = 0;i < G->numVertexes;i++)//建立顶点表
scanf("%d",&G->vexs[i]);
for (i = 0;i < G->numEdges;i++)
for (j = 0;j < G->numVertexes;j++)
G->arc[i][j] = INFINITY;//邻接矩阵初始化
for (k = 0;k < G->numEdges;k++)
{
printf("输入边(vi,vj)上的下标i,下标j和权数w:\n");
scanf("%d,%d,%d",&i,&j,&w);
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j];//无向图矩阵对称
}
}

时间复杂度为O(n+n²+e)

对于边数相对顶点较少的图,邻接矩阵对存储空间比较浪费。

邻接表

数组与链表相结合的存储方法。

  • 顶点用一维数组存储,每个数据元素还存储指向第一个邻接点的指针。
  • 每个顶点的所有邻接点构成一个线性表,用单链表存储。(有向图为出边表)

mark

对于有向图还可以建立一个逆邻接表,即入边表:

mark

对于带权值的网图,可以在边表结点中增加一个weight数据域:

mark

结构代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef char VertexType;
typedef int EdgeType;
typedef struct EdgeNode//边表结点
{
int adjvex;//邻接点域,存储该顶点对应的下标
EdgeType weight;//用于存储权值
struct EdgeNode *next;//链域,指向下一个邻接点
}EdgeNode;

typedef struct VertexNode//邻接表结点
{
VertexType data;
EdgeNode *firstedge;
}VertexNode,AdjList[MAXVEX];

typedef struct
{
AdjList adjList;//上机已证实可以这么用
int numVertexes,numEdges;
}GraphAdjList;

创建邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void CreateALGraph (GraphAdList *G)
{
int i,j,k;
EdgeNode *e;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&G->numVertexes,&G->numEdges);
for (i = 0;i < G->numVertexes;i++)
{
scanf("%d",&G->adjList[i].data);//输入顶点信息
G->adjList[i].firstedge = NULL;//将边表置为空表
}
for (k = 0;k < G->numEdges;k++)
{
printf("输入边(vi,vj)上的下标i,下标j和权数w:\n");
scanf("%d,%d,%d",&i,&j,&w);
e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->weight = w;
e->next = G->adjList[i].firstedge;
G->adjList[i].firstEdge = e;

e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = i;
e->weight = w;
e->next = G->adjList[j].firstedge;
G->adjList[j].firstEdge = e;
}
}

时间复杂度为O(n+e)

十字链表

将邻接表与逆邻接表结合。优化有向图的邻接表。

mark

tailvex:弧起点在顶点表的下标。

headvex:弧终点在顶点表的下标。

headlink:入边表指针域,指向终点相同的下一条边。(竖着指)

taillink:出边表指针域,指向起点相同的下一条边。(与邻接表相同)

mark

十字链表的好处是把邻接表和逆邻接表整合到了一起,既容易找到以vi为尾的弧,也容易找到以vi为头的弧,因而容易求得顶点的入度和出度。

除了结构复杂了一点外,其实创建图算法的时间复杂度和邻接表相同。

邻接多重表

优化无向图的邻接表。使之易于对边操作。

mark

ilink:指向依附顶点ivex的下一条边。

jlink:指向依附顶点jvex的下一条边。

mark

ilink和jlink指向的位置一定要与其本身依附的顶点的值相同。

邻接多重表与邻接表的区别,仅仅在于同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。如果要删除(v0,v2)这条边,只需将右图中⑥⑨的链接指向改为^即可。

边集数组

两个一维数组组成,一个存储顶点信息,一个存储边的信息,这个边数组每个元素由一条边的起点下标、终点下标和权值组成。

它更适合对边依次进行操作,而非对顶点进行操作。

mark

-------------本文结束感谢您的阅读-------------
undefined