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

第八章-图

基础知识

图的定义

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

通常表示为 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)/2条边$$
  ​

结点和边数量的关系：

1. 无向图：

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

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

2. 有向图：

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

图的逻辑和存储结构

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

邻接矩阵

定义

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

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][i]=0$$

示例

1. 无向无权图：

• 图中有 4 个结点，边的集合为 {(0, 1), (1, 2), (2, 3)}。

邻接矩阵表示：
$$A=\left[\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right]$$

2. 有向带权图：

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

邻接矩阵表示：
$$A=\left[\begin{array}{ccc}0& 5& 0\\ 0& 0& 10\\ 0& 0& 0\end{array}\right]$$

邻接表

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

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);}}
}