← 数据结构基础

数据结构-图

图G(Graph)由两个集合:V(Vertex)E(Edge)组成,记为G = (V, E),其中V是顶点的有限集合,记为V(G),E是连接V中两个不同顶点(顶点对)的的有限集合,记为E(G)。结点之间的关系为多对多,任两个结点之间都可能有关系存在。例如: V(G) = {v1, v2, v3, v4, v5}
E(G) = {(v1, v2), (v1, v4), (v2, v3), (v2, v5), (v3, v4), (v3, v5)}

图的基本术语

有向图和无向图

如果代表边的顶点对是无序的,则称G无向图
E
(
G
) = {(1, 2), (1, 3), (1, 0), (2, 3), (2, 4), (3, 4), (3, 0), (4, 0)}
如果代表边的顶点对是
有序
的,则称
G
有向图
E
(
G
) = { < 1, 2>, < 1, 3>, < 2, 3>, < 2, 4>, < 4, 3>, < 4, 0>, < 0, 1>, < 0, 3 > }

端点和接点

在一个无向图中,若存在一条边(vi, vj),则称vivj为此边的两个端点,并称它们互为邻接点
在一个有向图中,若存在一条边 < vi, vj>,则称此边是顶点vi的一条出边,同时也是顶点vj的一条入边;称vivj分别为此边的起始端点(或起点)终止端点(或终点);称vivj互为邻接点

入度和出度

无向图中,顶点所具有的边的数目称为该顶点的
有向图中,以顶点vi为终点的入边的数目,称为该顶点的入度。以顶点vi为始点的出边的数目,称为该顶点的出度。一个顶点的入度与出度之和为该顶点的
若一个图中有n个顶点和e条边,每个顶点的度为di(1 ≤ i ≤ n),则有(握手定理): $$ \mathbf{e}=\frac{1}{2} \sum_{i=1}^{n} \mathbf{d}_{i} $$

完全图

无向图中的每两个顶点之间都存在着一条边有向图中的每两个顶点之间都存在着方向相反的两条边,则称此图为完全图
image-20210110013756044
  • 完全无向图的边数等于n(n − 1)/2
  • 完全有向图的边数等于n(n − 1)

稠密图和稀疏图

当一个图接近完全图时,则称之为稠密图。相反,当一个图含有较少的边数,即当e < n(n − 1)时,则称为稀疏图。

子图

设有两个图G = (V, E)和G’ = (V’, E’),若V’是V的子集,即V’ ⊆ V,且E’是E的子集,即E’ ⊆ E,则称G’是G的子图。例如图(b)是图(a)的子图,而图(c)不是图(a)的子图。
image-20210110014353119

路径和路径长度

在一个图G = (V, E)中,从顶点vi到顶点vj的一条路径是一个顶点序列(vi, vi1, vi2, …, vim, vj),其边属于E(G)。
路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外,其余顶点均不相同,则称此路径为简单路径。例如(v0, v2, v1)就是一条简单路径,其长度为2。
image-20210110014740952

回路

若一条路径上的开始点与结束点为同一个顶点,则此路径被称为回路(或环)。开始点与结束点相同的简单路径被称为简单回路(或简单环)。简单回路:(v0, v2, v1, v0) ,长度为3。
image-20210110014740952

连通图和连通分量

无向图G中,若从顶点vi到顶点vj有路径,则称vivj连通的。
若图G中任意的两个顶点都连通,则称G连通图,否则称为非连通图
无向图G中的极大连通子图称为G连通分量。显然,任何连通图的连通分量只有一个,即本身,而非连通图有多个连通分量
image-20210110015753959

强连通图和强连通分量

有向图G中,若从顶点vi到顶点vj有路径,则称从vivj连通的。
若图G中的任意两个顶点vivj都连通,即从vivj和从vjvi都存在路径,则称图G强连通图
有向图G中的极大强连通子图称为G强连通分量。显然,强连通图只有一个强连通分量,即本身,而非强连通图有多个强连通分量

权和网

图中每一条边都可以附有一个对应的数值,这种与边相关的数值称为。权可以表示从一个顶点到另一个顶点的距离(或花费的代价)。边上带有权的图称为带权图(或网)
image-20210110020531452

图的存储结构

邻接矩阵存储方法

邻接矩阵是用来表示顶点间相邻关系的矩阵。
定义:设G = (V, E)是有n ≥ 0个顶点的图,G的邻接矩阵A是具有以下性质的n方阵
image-20210110020944692
对于网,可以用$a_{ij}$表示权。若vivj不邻接(即没有vi邻接到vj),则可以用无限大∞表示权:
image-20210110021459199
邻接矩阵存储结构的定义如下:
#define MAXV  4             // 最大顶点个数#define InfoType int        // 顶点其他信息// 顶点类型typedef struct{    int no;                 // 顶点编号    InfoType info;          // 可选项, 顶点其他信息} VertexType;// 图的邻接矩阵类型typedef struct{    int edges[MAXV][MAXV];  // 邻接矩阵, 保存边的信息    int n, e;               // 顶点数, 边数    VertexType vexs[MAXV];  // 存放顶点信息} MatGraph;

邻接表存储方法

邻接表存储方法是一种顺序分配链式分配相结合的存储方法。
对图中每个顶点i建立一个单链表,将顶点i的所有邻接点链起来。邻接表中有两类结点,分别为头结点边结点。每个单链表上添加一个表头结点(表示顶点信息)。并将所有表头结点构成一个数组,下标为i的元素表示顶点i表头结点
网的邻接表可以在边结点中额外增加weight数据域来表示权值或额外的边信息
邻接表存储结构的定义如下:
// 边结点的类型typedef struct ANode{    int adjvex;             // 该边的邻接点编号    struct ANode *nextarc;  // 指向下一条边的指针    int weight;             // 该边的相关信息} ArcNode;// 邻接表头结点的类型typedef struct{    InfoType data;          // 顶点信息    ArcNode *firstarc;      // 指向第一条边} VNode;// 图的邻接表类型typedef struct{    VNode adjlist[MAXV];    // 邻接表的头结点数组    int n, e;               // 图中顶点数n和边数e} AdjGraph;
一个邻接表通常用指针引用:
image-20210110024019734

逆邻接表

逆邻接表就是在有向图的邻接表中,对每个顶点,链接的是指向该顶点的边

邻接表的特点

  • 邻接表的表示不唯一。这是因为在每个顶点对应的单链表中,各边结点的链接次序可以是任意的,取决于建立邻接表的算法以及边的输入次序
  • 对于有n个顶点和e条边的无向图,其邻接表有n个头结点和2e个边结点。对于有n个顶点和e条边的有向图,其邻接表有n个头结点e个边结点
  • 对于无向图,邻接表的顶点v对应的第i个链表的边结点数目正好是顶点v
    • i
      i
  • 对于有向图,邻接表的顶点v对应的第i个链表的边结点数目仅仅是v出度。其入度为邻接表中所有adjvex域值为i边结点数目
    • i
      i

图的基本运算

建立邻接表

根据邻接矩阵数组A、顶点个数n和边数e来建立图的邻接表G(采用邻接表指针方式)。
// 创建图的邻接表void createAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e){    int i, j;    ArcNode *p;    G = (AdjGraph *) malloc(sizeof(AdjGraph));    // 给邻接表中所有头结点的指针域置初值    for (i = 0; i < n; i++)    {        G->adjlist[i].firstarc = NULL;    }    // 检查邻接矩阵中每个元素    for (i = 0; i < n; i++)    {        for (j = n - 1; j >= 0; j--)        {            // 存在一条边            if (A[i][j] != 0 && A[i][j] != INF)            {                p = (ArcNode *) malloc(sizeof(ArcNode));// 创建一个结点p                p->adjvex = j;                          // 存放邻接点                p->weight = A[i][j];                    // 存放权                p->nextarc = G->adjlist[i].firstarc;    // 采用头插法插入结点p                G->adjlist[i].firstarc = p;            }        }    }    G->n = n;    G->e = e;}

销毁邻接表

// 销毁邻接表void destroyAdj(AdjGraph *&G){    int i;    ArcNode *pre, *p;    for (i = 0; i < G->n; i++)          // 扫描所有的单链表    {        pre = G->adjlist[i].firstarc;   // p指向第i个单链表的首结点        if (pre != NULL)        {            p = pre->nextarc;            while (p != NULL)           // 释放第i个单链表的所有边结点            {                free(pre);                pre = p;                p = p->nextarc;            }            free(pre);        }    }    free(G);                            //释放头结点数组}

输出邻接表

// 打印邻接表void printAdj(AdjGraph *G){    int i;    ArcNode *p;    for (i = 0; i < G->n; i++)    {        p = G->adjlist[i].firstarc;        printf("%3d: ", i);        while (p != NULL)        {            printf("%3d[%d]→", p->adjvex, p->weight);            p = p->nextarc;        }        printf("∧\n");    }}
image-20210110031926936

图的遍历

图的遍历(Traversing Graph)是指从图中某一个顶点出发,访问图中的其余顶点,且使每个顶点仅被访问一次(如果给定的图是连通的无向图或者是强连通的有向图,则遍历过程一次就能完成)。
图的遍历有两种方法:
  • 深度优先搜索(DFS,Deep-First Search)
  • 广度优先搜索(BFS,Breadth-First Search)

深度优先搜索

深度优先搜索(DFS)遍历的过程是:从图中某个初始顶点v出发,首先访问初始顶点v,然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点,再从w出发进行深度优先搜索,直到图中与当前顶点v邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。
图的DFS序列不唯一,尽管从不同顶点或同一顶点出发,但遍历的路径不一样,则得到的DFS序列都可能不同
深度优先搜索遍历的特征是能走则走
邻接表为存储结构的深度优先搜索遍历的算法流程:
// 深度优先搜索void DFS(AdjGraph *G, int v){    ArcNode *p;    visited[v] = 1;             // 置已访问标记    printf("%d  ", v);          // 输出被访问顶点的编号    p = G->adjlist[v].firstarc; // p指向顶点v的第一条边的边头结点    while (p != NULL)    {        // 若p->adjvex顶点未访问, 递归访问它        if (visited[p->adjvex] == 0) DFS(G, p->adjvex);        // p指向顶点v的下一条边的边头结点        p = p->nextarc;    }}
image-20210110033123264

广度优先搜索

广度优先搜索(BFS)遍历的过程是:首先访问初始点vi,接着访问vi的所有未被访问过的邻接点vi1, vi2, …, vit,然后再按照vi1, vi2, …, vit的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。显然,这个遍历过程不是一个递归过程。
图的BFS序列不唯一,尽管从不同顶点或同一顶点出发,但遍历的路径不一样,则得到的BFS序列都可能不同
广度优先搜索遍历的特征是找完路再走
邻接表为存储结构的广度优先搜索遍历的算法流程:
// 广度优先搜索void BFS(AdjGraph *G, int v){    ArcNode *p;    int w;    int queue[MAXV], front = 0, rear = 0;   // 定义循环队列    printf("%2d", v);                       // 输出被访问顶点的编号    visited[v] = 1;                         // 置已访问标记    rear = (rear + 1) % MAXV;    queue[rear] = v;                        // v进队    while (front != rear)                   // 若队列不空时循环    {        front = (front + 1) % MAXV;        w = queue[front];                   // 出队并赋给        p = G->adjlist[w].firstarc;         // 找w的第一个的邻接点        while (p != NULL)        {            if (visited[p->adjvex] == 0)            {                printf("%2d", p->adjvex);   // 访问之                visited[p->adjvex] = 1;                rear = (rear + 1) % MAXV;   // 该顶点进队                queue[rear] = p->adjvex;            }            p = p->nextarc;                 // 找下一个邻接顶点        }    }    printf("\n");}

非连通图的遍历

对于无向图来说,若无向图是连通图,则一次遍历能够访问到图中的所有顶点;但若无向图是非连通图,则只能访问到初始点所在连通分量中的所有顶点,其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍历,才能够访问到图中的所有顶点
// 采用深度优先搜索遍历非连通无向图的算法void DFS1(AdjGraph *g){    int i;    // 遍历所有未访问过的顶点    for (i = 0; i < g->n; i++)    {        if (visited[i] == 0)        {            DFS(g, i);        }    }}// 采用广度优先搜索遍历非连通无向图的算法void BFS1(AdjGraph *g){    int i;    // 遍历所有未访问过的顶点    for (i = 0; i < g->n; i++)    {        if (visited[i] == 0)        {            BFS(g, i);        }    }}

生成树和最小生成树

一个含n个顶点的连通图的生成树是该连通图的一个极小连通子图,它含有图中全部顶点,但只含n − 1条能连通所有顶点的边,且不存在回路
  • 一个图可以有许多棵不同的生成树
  • 所有生成树具有以下共同特点:
    • 生成树的顶点个数与图的顶点个数相同
    • 生成树是图的极小连通子图
    • 一个有n个顶点的连通图的生成树有n − 1条
  • n个顶点n − 1条边的图不一定是生成树
采用DFS遍历图所得到的生成树称为深度优先生成树
采用BFS遍历图所得到的生成树称为广度优先生成树

最小生成树

希望找到一棵生成树,它的每条边上的权值之和最小

普里姆(Prim)算法

算法思想:
  1. G = (V, E)是具有n个顶点的连通网,T = (U, TE)为G的最小生成树,UT的顶点集合,TET的边集合。初始状态T为空树,UTE都是空集合
  1. 初始令U = v, (v ∈ V, ), TE = {}
  1. 在所有v ∈ Uk ∈ V − U的边(v, k) ∈ E中,找一条权值最小的边(v, k),将(v, k)并入集合TE,同时k并入U
    1. i
      i
      i
      i
      i
  1. 重复上述操作直至U = V为止,这时TE中有n − 1条边,T = (U, TE)为G的一棵最小生成树
#define INF 32767                   // INF表示无限大// Prim算法void Prim(int cost[][MAXV], int n, int v){    int lowcost[MAXV], min;    int closest[MAXV], i, j, k;    for (i = 0; i < n; i++)         // 给lowcost[]和closest[]置初值    {        lowcost[i] = cost[v][i];        closest[i] = v;    }    for (i = 1; i < n; i++)         // 找出n-1个顶点    {        min = INF;        for (j = 0; j < n; j++)     // 在(V-U)中找出离U最近的顶点k            if (lowcost[j] != 0 && lowcost[j] < min)            {                min = lowcost[j];                k = j;            }        printf("边(%d,%d)权为:%d\n", closest[k], k, min);        lowcost[k] = 0;             // 标记k已经加入U        for (j = 0; j < n; j++)     // 修改数组lowcost和closest            if (cost[k][j] != 0 && cost[k][j] < lowcost[j])            {                lowcost[j] = cost[k][j];                closest[j] = k;            }    }}

克鲁斯卡尔(Kruskal)算法

算法思想:
  1. G = (V, E)是网络,令最小生成树初始状态为只有n个顶点而无边的非连通图T = (V, ⌀),T中每个顶点自成一个连通分量
  1. E中的边按权递增顺序排列,选择顶点分别在两个连通分量中权最小的边加入图T,则原来的两个连通分量由于该边的连接而成为一个连通分量
  1. 依此类推,直至T中所有顶点都在同一连通分量上为止,该连通分量就是G的一棵最小生成树
typedef struct{    int u;     // 边的起始顶点    int v;     // 边的终止顶点    int w;     // 边的权值} Edge;// Kruskal算法void Kruskal(Edge E[], int n, int e){    int i, j, m1, m2, sn1, sn2, k;    int vset[MAXV];    for (i = 0; i < n; i++) vset[i] = i;    // 初始化辅助数组    k = 1;   // k表示当前构造最小生成树的第几条边,初值为1    j = 0;   // E中边的下标,初值为0    // 生成的边数小于n时循环    while (k < n)    {        m1 = E[j].u;        m2 = E[j].v;            // 取一条边的头尾顶点        sn1 = vset[m1];        sn2 = vset[m2];        // 分别得到两个顶点所属的集合编号        if (sn1 != sn2)      // 属不同的集合->最小生成树的一条边        {            printf("(%d,%d):%d\n", m1, m2, E[j].w);            k++;                      // 生成边数增1            for (i = 0; i < n; i++)   // 两个集合统一编号                if (vset[i] == sn2)   // 集合编号为sn2的改为sn1                    vset[i] = sn1;        }        j++;                          // 扫描下一条边    }}

Nobelium is built with ♥ and ⚛ Next.js. Proudly deployed on ▲Vercel.

© Ashinch 2021 桂ICP备18011166号-1