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

$$
E(G)={(v_1,v_2),(v_1,v_4),(v_2,v_3),(v_2,v_5),(v_3,v_4),(v_3,v_5)}
$$

图的基本术语

有向图和无向图

如果代表边的顶点对是无序的,则称$G$为无向图

image-20210109224054980
$$
E(G)={(1,2),(1,3),(1,0),(2,3),(2,4),(3,4),(3,0),(4,0)}
$$
如果代表边的顶点对是有序的,则称$G$为有向图

image-20210109224414761
$$
E(G)={<1,2>,<1,3>,<2,3>,<2,4>,<4,3>,<4,0>,<0,1>,<0,3>}
$$

端点和接点

在一个无向图中,若存在一条边$(v_i,v_j)$,则称$v_i$和$v_j$为此边的两个端点,并称它们互为邻接点

在一个有向图中,若存在一条边$<v_i,v_j>$,则称此边是顶点$v_i$的一条出边,同时也是顶点$v_j$的一条入边;称$v_i$和$v_j$分别为此边的起始端点(或起点)终止端点(或终点);称$v_i$和$v_j$互为邻接点

入度和出度

无向图中,顶点所具有的边的数目称为该顶点的

有向图中,以顶点$v_i$为终点的入边的数目,称为该顶点的入度。以顶点$v_i$为始点的出边的数目,称为该顶点的出度。一个顶点的入度与出度之和为该顶点的

若一个图中有$n$个顶点和$e$条边,每个顶点的度为$d_i(1≤i≤n)$,则有(握手定理):
$$
\mathbf
=\frac{1}{2} \sum_^ \mathbf_
$$

完全图

无向图中的每两个顶点之间都存在着一条边有向图中的每两个顶点之间都存在着方向相反的两条边,则称此图为完全图

image-20210110013756044

  • 完全无向图的边数等于$n(n-1)/2$
  • 完全有向图的边数等于$n(n-1)$

稠密图和稀疏图

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

子图

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

image-20210110014353119

路径和路径长度

在一个图$G=(V,E)$中,从顶点$v_i$到顶点$v_j$的一条路径是一个顶点序列$(v_i,v_,v_,…,v_,v_j)$,其边属于$E(G)$。

路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外,其余顶点均不相同,则称此路径为简单路径。例如$(v_0,v_2,v_1)$就是一条简单路径,其长度为$2$。

image-20210110014740952

回路

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

image-20210110014740952

image-20210110015304783

连通图和连通分量

无向图$G$中,若从顶点$v_i$到顶点$v_j$有路径,则称$v_i$和$v_j$是连通的。

若图$G$中任意的两个顶点都连通,则称$G$为连通图,否则称为非连通图

无向图$G$中的极大连通子图称为$G$的连通分量。显然,任何连通图的连通分量只有一个,即本身,而非连通图有多个连通分量

image-20210110015753959

强连通图和强连通分量

有向图$G$中,若从顶点$v_i$到顶点$v_j$有路径,则称从$v_i$到$v_j$是连通的。

若图$G$中的任意两个顶点$v_i$和$v_j$都连通,即从$v_i$到$v_j$和从$v_j$到$v_i$都存在路径,则称图$G$是强连通图

有向图$G$中的极大强连通子图称为$G$的强连通分量。显然,强连通图只有一个强连通分量,即本身,而非强连通图有多个强连通分量

image-20210110020321940

权和网

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

image-20210110020531452

图的存储结构

邻接矩阵存储方法

邻接矩阵是用来表示顶点间相邻关系的矩阵。

定义:设$G=(V,E)$是有$n \ge 0$个顶点的图,$G$的邻接矩阵$A$是具有以下性质的$n$阶方阵

image-20210110020944692

对于网,可以用$a_$表示权。若$v_i$和$v_j$不邻接(即没有$v_i$邻接到$v_j$),则可以用无限大$∞$表示权:

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;
image-20210110022157775

邻接表存储方法

邻接表存储方法是一种顺序分配链式分配相结合的存储方法。

对图中每个顶点$i$建立一个单链表,将顶点$i$的所有邻接点链起来。邻接表中有两类结点,分别为头结点边结点。每个单链表上添加一个表头结点(表示顶点信息)。并将所有表头结点构成一个数组,下标为$i$的元素表示顶点$i$的表头结点

image-20210110022856492 image-20210110023441833

网的邻接表可以在边结点中额外增加weight数据域来表示权值或额外的边信息

image-20210110023519698

邻接表存储结构的定义如下:

// 边结点的类型
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

逆邻接表

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

image-20210110024236434

邻接表的特点

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

销毁邻接表

// 销毁邻接表
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$邻接的所有顶点都被访问过为止。显然,这个遍历过程是个递归过程。

image-20210110032723486

图的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)遍历的过程是:首先访问初始点$v_i$,接着访问$v_i$的所有未被访问过的邻接点$v_,v_,…,v_$,然后再按照$v_,v_,…,v_$的次序,访问每一个顶点的所有未被访问过的邻接点,依次类推,直到图中所有和初始点$v_i$有路径相通的顶点都被访问过为止。显然,这个遍历过程不是一个递归过程。

image-20210110034305929

图的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");
}
image-20210110035423780

非连通图的遍历

对于无向图来说,若无向图是连通图,则一次遍历能够访问到图中的所有顶点;但若无向图是非连通图,则只能访问到初始点所在连通分量中的所有顶点,其他连通分量中的顶点是不可能访问到的。为此需要从其他每个连通分量中选择初始点,分别进行遍历,才能够访问到图中的所有顶点

image-20210110040239038
// 采用深度优先搜索遍历非连通无向图的算法
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);
        }
    }
}
image-20210110040732187

生成树和最小生成树

一个含$n$个顶点的连通图的生成树是该连通图的一个极小连通子图,它含有图中全部顶点,但只含$n-1$条能连通所有顶点的边,且不存在回路

  • 一个图可以有许多棵不同的生成树
  • 所有生成树具有以下共同特点:
    • 生成树的顶点个数与图的顶点个数相同
    • 生成树是图的极小连通子图
    • 一个有$n$个顶点的连通图的生成树有$n-1$条
  • 含$n$个顶点$n-1$条边的图不一定是生成树

采用DFS遍历图所得到的生成树称为深度优先生成树

采用BFS遍历图所得到的生成树称为广度优先生成树

image-20210110155947192

最小生成树

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

普里姆(Prim)算法

算法思想:

  1. 设$G=(V,E)$是具有$n$个顶点的连通网,$T=(U,TE)$为$G$的最小生成树,$U$是$T$的顶点集合,$TE$是$T$的边集合。初始状态$T$为空树,$U$和$TE$都是空集合
  2. 初始令$U=,(v\in V,为网中任一顶点), TE={}$
  3. 在所有$v \in U$,$k \in V-U$的边$(v,k) \in E$中,找一条权值最小的边$(v_i,k_i)$,将$(v_i,k_i)$并入集合$TE$,同时$k_i$并入$U$
  4. 重复上述操作直至$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;
            }
    }
}
image-20210110160835705

克鲁斯卡尔(Kruskal)算法

算法思想:

  1. 设$G=(V,E)$是网络,令最小生成树初始状态为只有$n$个顶点而无边的非连通图$T=(V, \varnothing)$,$T$中每个顶点自成一个连通分量
  2. 将$E$中的边按权递增顺序排列,选择顶点分别在两个连通分量中权最小的边加入图$T$,则原来的两个连通分量由于该边的连接而成为一个连通分量
  3. 依此类推,直至$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++;                          // 扫描下一条边
    }
}
image-20210110161524385 image-20210110161621660