数据结构(c语言) 第八章--图 (个人笔记)

发布于：2024-12-06 ⋅ 阅读:(254) ⋅ 点赞:(0)

文章目录

第八章-图

基础知识

图的定义

由顶点的有穷非空集合和顶点之间边的集合组成

通常表示为 G( V , E )

  • G表示一个图
  • V是图G中顶点的集合
  • E是图G中边的集合

基本名词概念

  • 结点的度: 一个结点的度是连接到该结点的边的数量 ( 在有向图中为入度与出度之和 )
    • 出度：在有向图中以这个结点为起点的有向边的数目。(可形象的理解为离开这个结点的边的数目)
    • 入度：在有向图中以这个结点为终点的有向边的数目。(可形象的理解为进入/指向这个结点的边的数目)
  • 图的度: 图中所有结点的度之和。对于无向图，度总和等于边数的两倍；对于有向图，总入度等于总出度

任意一个图的总度数等于其边数的2倍

  • 生成树: 给定图的一个连通且无环的子图。若原图有 n 个结点，则生成树有 n−1 条边。

  • 连通 : 如果在同一无向图中两个结点存在一条路径相连，则称这两个结点连通

    • 连通图 : 如果无向图中任意两个结点都是连通的，则称之为连通图。

    • 强连通 : 如果有向图中任意两个结点之间存在两条路径( 即 ( i , j ) 两点中，既从i到j有一条路径，j到i也有一条路径)，则两点是强连通的。

    • 强连通图 : 当一个图中任意两点间都是强连通的，则该图称之为强连通图 .

      在强连通图中，必定有一条回路经过所有顶点。

    • 连通分量 : 图中有子图，若子图极大连通则就是 连通分量 (有向的则称为 强连通分量)

    • **强连通分量 **：非强连通图有向图中的最大子强连通图。

  • 有向图: 图中的边有方向。例如边 ( u , v) 表示从结点 u 指向结点 v。

  • 无向图: 图中的边无方向。例如边 { u , v } 表示 u 和 v相互连接，无方向。

  • 无向完全图：无向图中，任意两个顶点之间都存在边

  • 有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧

  • 空图: 没有边的图，只有结点

  • 子图: 从原图中选取部分结点和边构成的图，称为原图的子图。

  • 简单图: 不允许存在自环（一个结点与自身相连的边）或多重边（两个结点间有多条边）。

  • 有根图及其根: 有向图中，若存在一个顶点 v 可达图中其它所有顶点，则称此有向图为有根图，v称作图的根

  • 弧头、弧尾、有序对: 在有向图中，边 ( u , v ) 的起点 u 为弧尾，终点 v 为弧头，边的方向用有序对 ( u , v ) 表示。

  • 通路 : 从一个结点到另一个结点经过的边的序列，所有结点必须唯一（路径不能重复结点）。

  • 关联: 边与结点之间的关系。如果边连接到某结点，则该边被称为与此结点关联。

  • 邻接: 两个结点直接由一条边连接，则称它们是邻接的。

  • 环: 路径的起点和终点相同，且除了起点与终点外没有重复结点。也称 简单回路 或 简单环

  • 路径及其长度: 路径是一个结点序列，路径长度是路径上边的总数（无权图）或权重之和（加权图）。

  • 权: 图中边的数值表示权重，常用于描述距离、成本或时间等信息。

  • 网络: 边带权重的图称为网络。无向网络中边是无方向的，有向网络中边是有方向的。

可能考点

最少边数

若无向图G(V,E)中含有7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是： 16

鉴于要考虑“任何情况”，故考虑极端情形：将给定的边尽可能的消耗在完全图构造上。如，7个点，构造6个点的完全图需要15条边。即对7个点，若边数小于等于15，此种情形不是连通的。故至少需要16条边。

n个点，任何情况下都连通，可分成两个集合：n-1个点的完全图、一个点，二者间通过一条线连接。

即：最小边数 = n-1个点的完全图 + 1

n个结点完全图的边数 , 结点和边数量上的关系

对于有N个顶点的完全图:

  • 有向图: 有 E = n ( n − 1 ) 条边 有E=n(n−1)条边 有E=n(n−1)条边

  • 无向图: 有 E = n ( n − 1 ) / 2 条边 有 E=n(n−1) / 2 条边 有E=n(n−1)/2条边
    ​

结点和边数量的关系：

  1. 无向图：

    • 随着 n (结点) 增加，边数以平方的速度增长。

    • E (边数) 与 n 成正比关系，具体为
      E = O ( n 2 ) E=O(n^2) E=O(n2)

  2. 有向图：

    • 边数更大，尤其在 n 增大时显著增长
      因为 E = n ( n − 1 ) ，仍是 O ( n 2 ) ，但系数不同 因为 E=n(n−1)，仍是O(n^2)，但系数不同 因为E=n(n−1)，仍是O(n2)，但系数不同

图的逻辑和存储结构

图型结构= 点集合 + 边集合 + 操作集合

邻接矩阵
定义

是一种表示图的逻辑结构的存储方式，适用于无向图、有向图以及网络图。它使用一个二维数组来记录图中结点之间的关系，每个元素表示对应结点间是否存在边以及边的权值。

  1. 形式：

    • 假设图有 n 个结点，邻接矩阵是一个 n×n 的二维数组 A。

    • 无权图：元素 A[i][j] 的值表示从结点 i 到结点 j 是否有边。如果有边，则 A[i][j]=1；否则 A[i][j]=0。

    • 带权图：元素 A[i][j] 表示从结点 i 到结点 j 的边的权值。如果没有边，则 A[i][j] 通常为 0 或无穷大（代表不可达）.

  2. 特性：

    • 对称性

      • 在无向图中，邻接矩阵是对称的，即
        A [ i ] [ j ] = A [ j ] [ i ] A[i][j]=A[j][i] A[i][j]=A[j][i]

      • 在有向图中，矩阵不一定对称。

    • 对角线

      • 如果图中没有自环，矩阵的对角线元素
        A [ i ] [ i ] = 0 A[i][i]=0 A[i][i]=0
示例
  1. 无向无权图：
  • 图中有 4 个结点，边的集合为 {(0, 1), (1, 2), (2, 3)}。

邻接矩阵表示：
A = [ 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 ] A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} A= ​0100​1010​0101​0010​ ​

  1. 有向带权图：
  • 图中有 3 个结点，边和权值为：(0,1,5),(1,2,10)

邻接矩阵表示：
A = [ 0 5 0 0 0 10 0 0 0 ] A = \begin{bmatrix} 0 & 5 & 0 \\ 0 & 0 & 10 \\ 0 & 0 & 0 \end{bmatrix} A= ​000​500​0100​ ​

邻接表

邻接表由以下几部分组成：

  1. 顶点结点（Vertex Node，vNode）:
    • 每个顶点用一个结构体表示. 包含：
      • 顶点数据：如顶点的值、编号等。
      • 指向邻接边链表的指针（first）：存储所有与该顶点相连的边。
  2. 边结点（Edge Node，eNode）:
    • 用链表的结点表示图中的边. 包含：
      • 邻接顶点的下标或标识。
      • 指向下一个边的指针，用于构建链表。
  3. 邻接表本身（Adjacency List，AdjList）:
    • 包含一个顶点数组（v[]），每个顶点对应一个链表头。
    • 存储顶点数（vNum）和边数（eNum）。

基本算法

邻接矩阵

邻接矩阵的结构体
#define m 100//定义最大点数 
typedef struct{//定义邻接矩阵的结构类型 
	int v[m];//点集 
	int e[m][m];//边集，即邻接矩阵 
	int vNum,eNum; //点数和边数 
}graph;
创建邻接矩阵

首先输入图的结点数和边数
初始化点集,给每个点标记区分(如1,2,3,4), 一个for循环, g->v[i]=i
初始化邻接矩阵, 两个for循环, g->e[i][j] = 0
最后输入边, 一系列的(x,y) , g->e[x][y] = 1 表示这条边存在

//创建邻接矩阵
void createGraph(graph *g){
	int x=0;int y=0;
	printf("输入图的结点数: ");
	scanf("%d",&g->vNum);
	printf("\n");
	printf("输入图的边数: ");
	scanf("%d",&g->eNum);
	
	for(int i=0;i<g->vNum;i++){//初始化点集
		g->v[i]=i;
	}
	
	for(int i=0;i<g->vNum;i++){//初始化邻接矩阵
		for(int j=0;j<g->vNum;j++){
			g->e[i][j]=0;
		}
	}
	fflush(stdin);//清空缓存，避免意外错误
	printf("\n请输入边，如(2,3)便是从2发出一条边到3:\n");
	for(int i=0;i<g->eNum;i++){
		scanf("(%d,%d)",&x,&y);//输入边
		g->e[x][y]=1; //有向图, 表示这条边存在
        
		//如果是无向图,还需要加上
		//g->e[y][x]=1; 
	}
}
打印邻接矩阵

两个for循环

//打印邻接矩阵
void printGraph(graph *g){
	printf("图中共有%d个点,%d条边\n",g->vNum,g->eNum);
	for(int i=0;i<g->vNum;i++){
		printf("\t");
		for(int j=0;j<g->vNum;j++){
			printf("%d ",g->e[i][j]);//输出邻接矩阵
		}
		printf("\n");
	}
}
计算结点的出度和入度
  • 结点x的出度: x->i : g->e[x][i] , 一个for 循环遍历所有的结点, if 判断如果有x指向该结点的边, 则出度加1
  • 结点x的入度: i->x: g->e[i][x], 一个for循环遍历所有的结点, if判断如果有结点指向x的边, 则入度加1
//使用邻接矩阵，计算结点x的入度、出度
void CountInOutDegree(graph *g,int x){
	int InDegree=0;
	int OutDegree=0;
	for(int i=0;i<g->vNum;i++){
		if(g->e[x][i]!=0){ //计算出度
			OutDegree++;
		}
	}
	for(int i=0;i<g->vNum;i++){
		if(g->e[i][x]!=0)//计算入度
			InDegree++;
	}
	printf("结点%d的出度:%d \n",x,OutDegree);
	printf("结点%d的入度:%d \n",x,InDegree);
	
}
深度优先遍历 (使用递归)

它从一个起始节点出发，沿着一条路径尽可能深入地搜索下去，直到无法继续深入时，回溯到最近的分叉点并选择另一条路径，直到所有节点都被访问过为止。

DFSone(graph *g, int v,int visited[])

先定义一个DFSone函数, 用于对节点v进行一个深度遍历

  • 从点v进行深度遍历, 传入三个参数: 邻接矩阵(图 g) , 开始遍历的结点 ( v ), 表示结点是否被访问过的数组 ( visited[] )
  • 先是打印出值v, 并 标记 好该点已经被访问, 然后进行一个for循环
  • 如果 有边 且 未被访问过 , 就以相同的方式对该结点进行遍历, 递归调用 DFSone(g,i,visited);
DFS(graph *g, int x)

需要考虑到非联通图, 存在多个连通分量的情况下

  • 先是初始化所有结点都是未访问的状态
  • 然后是一个 if 判断当前结点是否被访问过, 如果没有就就进入到if里面对这个结点进行深度遍历DFSone(g,x,visited);
  • 再是一个for循环, 遍历所有结点 (i=0;i<g->vNum;i++) ，寻找新的连通分量
  • if 判断这个结点是否已经被访问过, 只要没被访问过, 就对这个结点进行深度遍历DFSone(g,x,visited);
//从结点v进行深度遍历
void DFSone(graph *g, int v,int visited[]){ 
	printf("%d ",v);
	visited[v]=1; //表示这个点已经被访问
    //遍历当前节点的所有邻接节点
	for(int i=0;i<g->vNum;i++){
		if(g->e[v][i]!=0 && visited[i]==0){ //边存在且未被访问
			DFSone(g,i,visited); //递归调用, 继续遍历
		}
	}
}
//在整个图里面从节点x出发深度遍历
void DFS(graph *g, int x){ 
	int visited[m]={0}; //初始所有节点未访问
	int c=0; //连通分量计数
	
	if(visited[x]==0){
		c++;
		printf("\n第%d个连通分量: ",c);
		DFSone(g,x,visited);
	}
	//非连通图的情况下, 存在多个连通分量
	for(int i=0;i<g->vNum;i++){
		if(visited[i]==0){
			c++;
			printf("\n第%d个连通分量: ",c);
			DFSone(g,i,visited);
		}
	}
}
广度优先遍历
队列

广度优先遍历需要使用到 队列 , 一个队列的基本操作: 初始化, 判空, 入队, 出队

typedef struct{ //队列的结构体
	int a[m];
	int front;
	int rear;
}Queue;
//初始化
void InitQueue(Queue *q){
	q->front=q->rear=0;
}
//判空
int IsEmpty(Queue *q){
	return q->front==q->rear;
}
//入队
void EnQueue(Queue *q,int x){
	q->a[q->rear]=x;
	q->rear++;
}
//出队
int OutQueue(Queue *q){
	int a=q->a[q->front];
	q->front++;
	return a;
}
BFsone(graph *g,int v,int visited[])

从节点v进行广度遍历, 传入三个参数, 邻接矩阵( 图 g ) , 开始遍历的节点 ( v ), 表示结点是否被访问过的数组 ( visited[] )

  • 初始化队列, 然后将当前结点入队, 并标记该结点已经被访问 (入队即表示已访问)
  • while 循环, 只要队列不为空就继续 while(!IsEmpty(&q))
  • 将队列里面出队一个元素, 打印出来
  • for循环, 遍历出队元素的所有邻接结点 for(int j=0;j<g->vNum;j++)
  • if 判断 如果有边且未被访问 , 那么就将其入队, 并标记其已经被访问
BFS(graph *g,int x)

需要考虑非连通, 存在多个连通分量的情况

  • 初始化所有节点都是未访问的状态
  • if判断, 如果没有被访问, 那么就对这个节点进行广度优先遍历, 调用 BFsone(g,x,visited);
  • for循环遍历所有的结点, 里面if 判断如果该结点未被访问, 那么就对这个结点进行广度优先遍历, 调用BFsone(g,i,visited);
void BFsone(graph *g,int v,int visited[]){
	Queue q;
	InitQueue(&q);
	EnQueue(&q,v);
	visited[v]=1;

	while(!IsEmpty(&q)){
		int i=OutQueue(&q);
		printf("%d ",i);
		for(int j=0;j<g->vNum;j++){//遍历所有的邻接结点
			//判断是否有边且未被访问
			if(g->e[i][j]!=0 && visited[j]==0){
				EnQueue(&q,j);
				visited[j]=1;
			}
		}
		
	}
}
void BFS(graph *g,int x){
	int visited[m]={0};
	int c=0;
	if(visited[x]==0){
		c++;
		printf("\n第%d个连通图:\n",c);
		BFsone(g,x,visited);
	}
	for(int i=0;i<g->vNum;i++){
		if(visited[i]==0){
			c++;
			printf("\n第%d个连通图:\n",c);
			BFsone(g,i,visited);
		}
	}
}

邻接表

邻接表结构体

邻接表由三部分组成:

  • 边结点的结构体
  • 顶点结点的结构体
  • 邻接表本身的结构体
//1.1边结点的结构体
typedef struct e{
	int v;
	struct e*next;
}eNode;
//1.2顶点结点的结构体
typedef struct k{
	int vdata;//顶点数据
	eNode* first;//指向邻接边链表的指针,存储所有与该顶点相连的边
}vNode;

//1.3邻接表本身结构体
typedef struct {
	vNode v[max];//顶点数组
	int vNum; //顶点数
	int eNum; //边数v
}AdjList;
创建邻接表
inserTail 函数

用于将新的边结点( eNode ) 插入到顶点的邻接表末尾

当链表为空时：

  • 直接将边节点赋值给链表的头指针 v->first，然后立即返回。

当链表不为空时：

  • 遍历链表直到找到最后一个节点（tail->next == NULL）。
  • 将新节点插入到链表末尾。

将边插入到顶点 x 的边链表中

createAdjGraph 函数

初始化图的信息：

  • 读取顶点数 vNum 和边数 eNum。
  • 初始化顶点数组 g->v：
    • 将每个顶点的 first 指针设置为 NULL（表示初始没有边）。
    • 设置顶点编号 v[i].vdata = i。
  • 作用： 确保顶点数组的每一项都可以正确存储对应的邻接链表。

读取边的信息:

  • 按 (x, y) 的格式输入边，表示从顶点 x 指向顶点 y 的有向边。
  • 为每条边动态分配内存，创建一个 eNode
    • 设置该边的目标点 p->v = y。(因为是 x->y , 所以 y 是边结点 ,顶点结点是 x)
    • 将 p->next 初始化为 NULL（链表的新尾节点）。
  • 调用 inserTail函数将新边节点插入到对应顶点 x 的邻接链表中。

inserTail(&(g->v[x]),p);

邻接表创建的流程总结
  1. 输入顶点数和边数，初始化顶点数组。
  2. 每次读取一条边 (x, y)：
    • 创建新边节点并设置目标顶点为 y。
    • 将新边插入到顶点 x 的邻接链表末尾。
  3. 邻接表最终由顶点数组和每个顶点的邻接链表组成。
//链表末尾插入元素
void inserTail(vNode *v,eNode *e){
	if(v->first==NULL){
		v->first=e;//链表为空, 直接插入e元素
		return;
	}
	eNode *tail;
	tail=v->first;
	//让tail为最后一个结点
	while(tail->next!=NULL){
		tail=tail->next;
	}
	tail->next=e;//将新元素尾插入链表
}

//创建邻接表
void createAdjGraph(AdjList *g){
	int x=0;
	int y=0;
	printf("输入结点数: ");
	scanf("%d",&g->vNum);
	printf("输入边数: ");
	scanf("%d",&g->eNum);
	
	//初始化
	for(int i=0;i<g->vNum;i++){
		g->v[i].first=NULL;//初始链表为空
		g->v[i].vdata=i;
	}
	fflush(stdin);//清空缓存
	printf("输入边, 如(2,3)表示从2发出一条边到3:\n");
	for(int i=0;i<g->eNum;i++){
		scanf("(%d,%d)",&x,&y);
		eNode *p=(eNode *)malloc(sizeof(eNode));
		p->v=y; //边的目标结点
		p->next=NULL;
		inserTail(&(g->v[x]),p);
	}
}
逆邻接表

与邻接表其他部分都相同, 就是最后那部分的代码, x和y的位置变了一下
( x , y ) 因为是作为入边表, 也就是 y是作为顶点结点, x作为边结点 , 成了 y->x 的形式
将边插入到顶点 y 的边链表中

//创建逆邻接表
void createReverseAdjGraph(AdjList *g){
	int x=0;
	int y=0;
	printf("输入结点数: ");
	scanf("%d",&g->vNum);
	printf("输入边数: ");
	scanf("%d",&g->eNum);
	
	//初始化
	for(int i=0;i<g->vNum;i++){
		g->v[i].first=NULL;//初始链表为空
		g->v[i].vdata=i;
	}
	fflush(stdin);//清空缓存
	printf("输入边, 如(2,3)表示从2发出一条边到3:\n");
	for(int i=0;i<g->eNum;i++){
		scanf("(%d,%d)",&x,&y);
		eNode *p=(eNode *)malloc(sizeof(eNode));
		p->v=x; //边的目标结点
		p->next=NULL;
		inserTail(&(g->v[y]),p);
	}
}
计算出度和入度

定义一个边结点 eNode *p=g->v[x].first , 为顶点 x 的第一条边

  • 计算结点x的出度: while循环, 只要p不为空, 出度加1, p指向下一个边结点, p=p->nexe
  • 计算入度: for循环, 遍历每一个结点, 变量 p 为顶点的边
    • while循环, 只要p不为空, if判断如果有指向结点x的边 ( p->v==x ) , 则入度+1, 没有的话就p指向下一条边, 直到p为空
//使用邻接表，计算结点x的入度、出度
void AdjCountInOutDegree(AdjList *g ,int x){
	int InDegree=0;
	int OutDegree=0;
	eNode *p;
	p=g->v[x].first;
	while(p!=NULL){ //计算出度
		OutDegree++;
		p=p->next;
	}
	for(int i=0;i<g->vNum;i++){ //计算入度
		p=g->v[i].first;
		while(p!=NULL){
			if(p->v==x){
				InDegree++;
			}
			p=p->next;
		}
		
	}
	printf("\n结点%d的出度:%d\n",x,OutDegree);
	printf("结点%d的入度:%d\n",x,InDegree);
}
深度优先遍历

跟邻接矩阵的差不多, 仅仅因为结构体的不同带来的变化

//对结点v进行深度遍历
void AdjDFsOne(AdjList *g, int v,int visited[]){
	eNode *p;
	printf("%d ",v);
	visited[v]=1;
	for(p=g->v[v].first;p!=NULL;p=p->next){ //遍历边结点
		if(visited[p->v]==0){
			AdjDFsOne(g,p->v,visited);
		}
	}
}
//对整个图的邻接表 从结点x出发深度遍历
void AdjDFs(AdjList *g, int x){
	int visited[m]={0};
	int c=0;
	if(visited[x]==0){
		c++;
		printf("\n第%d个连通分量: ",c);
		AdjDFsOne(g,x,visited);
	}
	for(int i=0;i<g->vNum;i++){
		if(visited[i]==0){
			c++;
			printf("\n第%d个连通分量: ",c);
			AdjDFsOne(g,i,visited);
		}
	}
}
广度优先遍历

跟邻接矩阵的差不多, 仅仅因为结构体的不同带来的变化

//从结点v开始的广度遍历
void AjdBFsOne(AdjList *g, int v, int visited[]){
	Queue q;
	InitQueue(&q);
	EnQueue(&q,v);
	visited[v]=1;
	eNode *p;
	while(!IsEmpty(&q)){
		int i=OutQueue(&q);
		printf("%d ",i);
		for(p=g->v[i].first;p!=NULL;p=p->next){ //遍历边结点
			if(visited[p->v]==0){
				EnQueue(&q,p->v);
				visited[p->v]=1;
			}
		}
	}
}

void AdjBFs(AdjList *g,int x){
	int visited[m]={0};
	int c=0;
	if(visited[x]==0){
		c++;
		printf("\n第%d个连通分量: ",c);
		AjdBFsOne(g,x,visited);
	}
	for(int i=0;i<g->vNum;i++){
		if(visited[i]==0){
			c++;
			printf("\n第%d个连通分量: ",c);
			AjdBFsOne(g,i,visited);
		}
	}
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布