一、图的定义和术语
1.图的定义
图: G=(V,E)
V: 顶点(数据元素)的有穷非空集合
E: 边的有穷集合
1) 无向图: 每条边都是无方向的
2) 有向图: 每条边都是有方向的
3) 完全图: 任意两个点都有一条边相连
4) 稀疏图: 有很少边或弧的图(e<nlogn)
5) 稠密图: 有较多边或弧的图
6) 网: 边/弧带权的图
7) 邻接: 有边/弧相连的两个顶点之间的关系(圆括号是无向图，尖括号是有向图)
存在(Vi,Vj),则称Vi和Vj互为邻接点
存在<Vi,Vj>,则称Vi邻接到Vi，Vj邻接于Vi
8) 关联(依附): 边/弧与顶点之间的关系
存在(Vi,Vj)/<Vi,Vj>,则称该边/弧关联于Vi和Vj
9) 顶点的度: 与该顶点相关联的边的数目，记为TD(v)
在有向图中，顶点的度等于该顶点的入度与出度之和
顶点v的入度是以v为终点的有向边的条数，记作ID(v)
顶点v的出度是以v为始点的有向边的条数，记作OD(v)
10) 当有向图中仅1个顶点的入度为0，其余顶点的入度均为1，此时是何形状?
答: 是树!而且是一棵有向树!
2.图的相关概念
1) 路径: 接续的边构成的顶点序列
2) 路径长度: 路径上边或弧的数目/权值之和
3) 回路(环): 第一个顶点和最后一个顶点相同的路径
4) 简单路径: 除路径起点和终点可以相同外，其余顶点均不相同的路径
5) 简单回路(简单环): 除路径起点和终点相同外，其余顶点均不相同的路径
6) 连通图(强连通图): 在无(有)向图G={V,{E}}中，若对任何两个顶点v、u都存在从v、u的路径，则称G是连通图(强连通图)
7) 权与网: 图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费
带权的图称为网
8) 子图: 设有两个图G=(V,{E})、G1=(V1,{E1}),若则称G1是G的子图
3.连通分量
1) 无向图G的极大连通子图称为G的连通分量
2) 极大连通子图:该子图是G的连通子图，将G的任何不在该子图中的顶点加入，子图不再连通
3) 有向图G的极大强连通子图称为G的连强通分量
4) 极大强连通子图:该子图是G的强连通子图，将G的任何不在该子图中的顶点加入，子图不再强连通
4) 极小连通子图:该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通
5) 生成树: 包含无向图G所有顶点的极小连通子图
6) 生成森林: 对非连通图，由各个连通分量的生成树的集合
二、图的存储结构
1.数组(邻接矩阵)表示法
建立一个顶点表(记录各个顶点信息)和一个邻接矩阵(表示各个顶点之间关系)
* 设图A=(V,E)有n个顶点，则
顶点表Vexs[n] i 0 1 2 ... n-1 Vexs[i] V1 V2 V3 ... Vn * 图的邻接矩阵是一个二维数组A.arc[n][n],定义为:
如果<i,j>属于E或者(i,j)属于E，则A.arcs[i][j]=1
否则A.arcs[i][j]=0
1) 无向图的邻接矩阵表示法:
2) 有向图的邻接矩阵表示法:
3) 网(即有权图)的邻接矩阵表示法:
2.邻接矩阵的存储表示:用两个数组分别存储顶点表和邻接矩阵
#define MVNum 100 //最大顶点数
#define MaxInt 32767 //表示极大值，即∞
typedef char VerTexType; //设顶点的数据类型为字符型
typedef int ArcType; //假设边的权值类型为整型
typedef struct
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的当前顶点数和边数
}AMGraph;3.采用邻接矩阵表示法创建无向网
1) 输入总顶点数和总边数
2) 依次输入点的信息存入顶点表中
3) 初始化邻接矩阵，使每个权值初始化为极大值
4) 构造邻接矩阵
int LocateVex(AMGraph *G, VerTexType u) //在图G中查找顶点u
{
for (int i = 0; i < G->vexnum; i++)
{
if (u == G->vexs[i])
return i; //在则返回顶点表中的下标
}
return -1; //否则返回-1
}
void CreateUDN(AMGraph *G) //采用邻接矩阵表示法创建无向网
{
printf("请输入顶点数: "); //输入顶点数
scanf("%d", &G->vexnum);
printf("请输入边数: "); //输入总边数
scanf("%d", &G->arcnum);
for (int i = 0; i < G->vexnum; i++)
{
scanf("%c", &G->vexs[i]); //依次输入点的信息
}
for (int i = 0; i < G->vexnum; i++)
{
for (int j = 0; j < G->vexnum; j++)
{
G->arcs[i][j] = MaxInt; //边的权值均置为极大值
}
}
for (int k = 0; k < G->arcnum; k++) //构造邻接矩阵
{
VerTexType v1, v2;
ArcType w;
printf("请输入一条边所依附的两个顶点: ");
scanf("%c %c", &v1, &v2); //输入一条边所依附的顶点
printf("\n请输入边的权值: ");
scanf("%d", &w); //输入边的权值
putchar('\n');
int i = LocateVex(G, v1);
int j = LocateVex(G, v2); //确定v1和v2在G中的位置
G->arcs[i][j] = w; //边的权值置为w
G->arcs[j][i] = G->arcs[i][j]; //对应对称权值也设为w
}
}4.邻接矩阵表示法的优缺点
优点:
1) 直观、简单、好理解
2) 方便检查任意一对顶点间是否存在边
3) 方便找任一顶点的所有"邻接点"(有边直接相连的顶点)
4) 方便计算任一顶点的"度"(从该点发出的边数为"出度",指向该点的边数为"入度")
//无向图: 对应行(或列)非0元素的个数
//有向图: 对应行非0元素的个数是"出度";对应列非0元素的个数是"入度"
缺点:
1) 不便于增加和删除顶点
2) 浪费空间----存稀疏图(点很多而边很少)有大量无效元素
3) 浪费时间----统计稀疏图中一共有多少条边
5.邻接表表示法(链式)
1) 无向图的邻接表表示法:
2) 有向图的邻接表表示法:
6.图的邻接表存储表示
#define MVNum 100 //最大顶点数
typedef char VerTexType;
typedef struct ArcNode //边结点
{
int avjvex; //该边所指向的顶点位置
int info; //和边相关的信息
struct ArcNode *nextarc; //指向下一条边的指针
}ArcNode;
typedef struct VNode //顶点
{
VerTexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型
typedef struct //图的结构定义
{
AdjList vertices; //vertices--vertex的复数
int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph;7.采用邻接表表示法创建无向网
算法思想:
1) 输入总顶点数和边数
2) 建立顶点表
*依次输入点的信息存入顶点表中
*使每个表头结点的指针域初始化为NULL
3) 创建邻接表
*依次输入每条边依附的两个顶点
*确定两个顶点的序号i和j，建立边结点
*将此边结点分别插入到Vi和Vj对应的两个边链表的头部
int LocateVex(ALGraph *G, VerTexType u)
{
for (int z = 0; z < G->vexnum; z++)
{
if (G->vertices[z].data == u)
return z;
}
return -1;
}
void CreateUDG(ALGraph *G) //采用邻接表表示法，创建无向图G
{
VerTexType v1, v2;
int i, j,w;
printf("请输入总顶点数: "); //输入总顶点数
scanf("%d", &G->vexnum);
printf("请输入总边数: "); //输入总边数
scanf("%d", &G->arcnum);
for (int i = 0; i < G->vexnum; i++) //输入各点，构造表头结点表
{
scanf("%c", &G->vertices[i].data); //输入顶点值
G->vertices[i].firstarc = NULL; //初始化表头结点的指针域
}
for (int k = 0; k <(2*G->arcnum); k++) //输入各边，构造邻接表
{
printf("请输入第一个顶点: "); //输入一条边依附的第一个顶点
scanf("%c", &v1);
printf("请输入第二个顶点: "); //输入一条边依附的第二个顶点
scanf("%c", &v2);
i = LocateVex(G, v1);
j = LocateVex(G, v2);
printf("请输入边的权值: ");
scanf("%d", &w);
ArcNode *p1 = (ArcNode*)malloc(sizeof(ArcNode)); //生成一个新的边结点p1
p1->avjvex = j; //邻接点序号为j
p1->info = w; //赋权值
p1->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc = p1; //将新结点*p1插入顶点Vi的边表头部
ArcNode *p2 = (ArcNode*)malloc(sizeof(ArcNode)); //生成一个新的边结点p2
p2->avjvex = i; //邻接点序号为i
p2->info = w; //赋权值
p2->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p2; //将新结点*p2插入顶点Vj的边边表头部
}
}8.邻接表表示法的优缺点
1) 方便找任一顶点的所有邻接点
2) 节约稀疏图的空间--需要N个头指针+2E个边结点(每个边结点至少两个域)
3) 方便计算无向图中任一顶点的度
4) 对有向图来说:只能计算"出度"；需要构造"逆邻接表"(存指向自己的边)来方便计算"入度"
5) 不方便检查任意一对顶点间是否存在边
9.邻接矩阵与邻接表表示法的关系
1)联系: 邻接表中每个链表对应邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数
2)区别:
(1).对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一(链接次序与顶点编号无关)
(2).邻接矩阵的空间复杂度为O(n*n),而邻接表的空间复杂度为O(n+e)
3)用途: 邻接矩阵多用于稠密图；而邻接表多用于稀疏图
10.十字链表(有向图)
1) 十字链表是有向图的另一种链式存储结构(可以看成将有向图的邻接表和逆邻接表结合起来形成的一种链表)
2) 有向图中的每一条弧对应十字链表中的一个弧结点
3) 有向图中的每个顶点在十字链表中对应有一个结点，叫作顶点结点
11.邻接多重表(无向图)
