2025年数据结构复习笔记：图的概念和操作

大家好，我是讯享网，很高兴认识大家。

数据结构复习笔记：图的概念和操作

一，图

1.图的定义：
图G（Graph）由俩个集合V(Vertex)和E（Edge）组成，记为G=（V， E），其中V是顶点的有限集合，E是连接V中顶点的边的有限集合。通常，也将图中的顶点集记为V（G），边集记为E（G）。
2.有向图和无向图：
如果E中的顶点对是有序的，即E中的每条边都是有方向的，则G称为有向图。如果顶点对是无序对，则称G为无向图。
在这里插入图片描述
讯享网

3.弧和边：
①弧的定义：若G = （V，E）是有向图，则它的一条有向边是由V中俩个顶点构成的有序对，也叫做弧，记为＜ｕ，ｖ＞，其中u是变得始点，又称为弧尾，v是边的终点，又称为弧头。
②边的定义：若G为无向图，则图中的边记为（u，v).因为（u，v）是无序对，所以（u，v）和（v，u）代表同一条边。
４．简单图和多重图：
E是边的集合，一般图中不会出现重复的边，重复的边简称重边。若一条边的俩个顶点相同，则此边称作自环。无重边和自环的图称为简单图，否则为多重图。
５.度：
无向图：对于无向图G，v∈V（G），E（G）中以ｖ为端点的边的个数，称为顶点的度。
有向图：对于有向图G，v的出度是以v为始点的边的个数，v的入度是以v为终点的边的个数。顶点的度等于入度加出度。
６.连通：
设G是图，若存在一条从顶点 $v_i$ 到 $v_j$ 的路径，则称 $v_i$ 和 $v_j$ 是连通的（可及的）。
若G是无向图，且V（G）中任意俩顶点都连通，则称Ｇ为连通图。
若G是有向图，且V（G）中任意俩个顶点 $v_i$ 和 $v_j$ ， $v_i$ 和 $v_j$ 以及 $v_j$ 和 $v_i$ 均连通，则称G为强连通图。
若G是有向图，且V（G）中任意俩个顶点 $v_i$ 和 $v_j$ 可及或 $v_j$ 和 $v_i$ 可及，则称G为弱连通图。
７.子图：
设G，H是图，如果V（H） $\subseteq$ V（G），E（H） $\subseteq$ E（G），则称H是G的子图，G是H的母图。
如果H是G的子图，并且V（H）＝V（G），则称H为G的支撑子图（生成子图）。
８.连通分支：
图G＝（V，E）是无向图，若G的子图 $G_k$ 是一个连通图，则称 $G_k$ 为G的连通子图。
图G=（V，E）是有向图，若G的子图 $G_k$ 是一个强连通图，则称 $G_k$ 为G的强连通子图。
（呼。。。没想到概念这么多）

二.图的存储

邻接矩阵：
对于有权图， $a_{ij}$ 为对应边< $V_i$ , $V_j$ >或（ $V_i$ , $V_j$ ）的权值， $a_{ii}$ = 0， $a_{ij}$ = $\infty$ , 当i != j 且（ $V_i$ ， $V_j$ ）不存在时。
优点：借助邻接矩阵，很容易求出图中顶点的度。无向图的邻接矩阵可压缩存储。所需空间为n（n+1）/2;有向图为 $n^2$ 。
邻接表：
①实现：1.定长数组A[n][d];
2.可变长数组vector;
3.邻接链表；
②邻接链表：

typedef struct Edge{ 
    int VerAdj; //邻接顶点序号; int cost; //权值; Edge* link = nullptr; //指向下一个边结点的指针; }; struct Vertex{ 
    int VerName; Edge* adjacent = nullptr; };

讯享网

注意：对于有向图，只存一条边即可，但对于无向图，需要存双向边。
在这里插入图片描述

三.图的遍历

深度优先搜索（Depth First Search， DFS）：
方法：从某一顶点出发v，访问它的任意邻接顶点v’,再重复上述步骤，访问未被访问过的节点。
1.递归版：

讯享网void DFS(int v) { 
    visit[v] = 1; for(p = V[v]->adjacent; p; p = p->link) { 
    if(visit[p->VerAdj] != 1) DFS(p->VerAdj); } }

2.迭代版：

void NRDFS(int v) { 
    stack <int> s; s.push(v); visit[v] = 1; //初始化为0 while(!s.empty()) { 
    int v = s.top(); s.pop(); Edge *p; for(p = V[v]->adjacent; p; p = p->link) { 
    if(visit[p->VerAdj] == 0) { 
    s.push(p->VerAdj); visit[p->VerAdj] = 1; } } } }

广度优先搜索（Breadth First Search, BFS)：
方法：访问初始点 $V_0$ ，之后依次访问 $V_1$ , $V_2$ , $V_3$ …,然后再访问与 $V_1$ , $V_2$ , $_V3$ …邻接的尚未访问的全部节点，再从这些访问过的节点出发，访问邻接的未访问的全部节点。

讯享网void BFS(int v) { 
    //initial for(int i = 1; i <= n; i++) visit[i] = 0; queue <int> Q; Q.push(v); visit[v] = 1; //sign array //BFS while(!Q.empty()) { 
    v = Q.front(); cout << v; Edge* p; for(p = V[v].adjacent; p; p = p->link) { 
    if(!visit[p->Veradj]) { 
    Q.push(p->Veradj); visit[p->Veradj] = 1; } } } }

2025年数据结构复习笔记：图的概念和操作

数据结构复习笔记：图的概念和操作

一，图

二.图的存储

三.图的遍历

相关推荐