一.图的基本概念

1.图的定义

图是由顶点和边组成的,分为两类:有向图和无向图。

边有方向即为有向图,无方向即为无向图。

2.图的术语

  • 端点和邻接点
    • 无向图中:一条边(i,j),则称顶点i和j为该边的两个端点,并且他们互为邻接点
    • 有向图中:则更细分为:起始端点、终止端点;出边邻接点、入边邻接点
  • 度、入度、出度
    • 无向图中:一个顶点所有的边的数目称为顶点的度
    • 有向图中:顶点指出去(作为起点)的边的数目为顶点的出度,指向该顶点(作为终点)的边的数目为顶点的入度
      • 性质:所有顶点的度之和 = 边数 * 2
  • 完全图
    • 无向图中:每两个顶点之间都存在一条边
    • 有向图中:每个顶点之间都存在方向相反的两条边
      • 无向完全图有n(n-1)/2条边,有向完全图有n(n-1)条边。用排列组合想一下就知道了
  • 稠密图和稀疏图
    • 稠密图:一个图接近完全图
    • 稀疏图:边数很少
  • 子图
    • 相当于图取出一部分,这部分即为子图
  • 路径和路径长度
    • 路径:一个点从若干条边到另一个点的序列
    • 路径长度:一个点到另一个点所经过的边的数量
      • 简单路径:没有重复经过一个顶点的路径
  • 回路/环
    • 开始点和结束点为同一个顶点
  • 连通
    • 两个顶点有路径,称这两个顶点连通
    • 无向图中:任意两点都连通的无向图称为连通图,极大连通子图称为该无向图的连通分量。(连通图的连通分量只有一个——它本身,非连通图有多个连通分量)
    • 有向图中:任意两点都连通(i可以到j,j也可以到i)的有向图称为强连通图,极大连通子图称为该有向图的强连通分量。(连通图的连通分量只有一个——它本身,非连通图有多个连通分量)。
  • 权和网
    • 边带有权值的图称为带权图或网

二.图的存储结构

图的存储结构有:邻接矩阵、邻接表、十字链表、邻接多重表、边集数组。

比较常用的且我们要掌握的是: 邻接矩阵、邻接表

1.邻接矩阵

图是由顶点和边组成的,因此我们需要分两个结构,顶点用一维数组来存,而是两个顶点之间的关系,我们可以用一个二维数组来存。

因为图大体上分为有向图和无向图,带权和不带权,因此边的二维数组我们需要分4种情况。

为什么带权图要用∞来表示不连通?因为定义成其他值可能跟权值混淆,我们需要定义成一个不可能是权值的值。我们可以用该数据类型的极限值来表示∞。

如下图:

  • 顶点—— 一维数组
  • 顶点的数据类型可以由我们自己定义,可以是int存编号(0,1,2......),也可以是char存放编号(v0,v1.......)。而实际中顶点一般还要放一些数据信息,我们还可以自己定义结构体,来存放编号+数据信息。
typedef int VertexType;

或者

typedef struct {
    int no;     //存放顶点编号
    int info;   //存放顶点信息
}VertexType;
  • 边—— 二维数组
  • 边表示的是两个顶点之间的关系,因此我们需要存顶点一维数组,以及它们的关系矩阵二维数组,此外,我们还可以存当前的顶点数以及边数来方便我们后续操作。
typedef struct {
    VertexType vexs[MAXV];  //顶点数组
    int edges[MAXV][MAXV];  //顶点关系的矩阵
    int n,e;                //定点数和边数
}MatGraph;

总代码:

#define MAXV 100       //最大顶点数
#define INF 32767      //定义∞

//typedef int VertexType;
typedef struct {
    int no;    //存放顶点编号
    int info;  //存放顶点信息
}VertexType;

typedef struct {
    VertexType vexs[MAXV];  //顶点数组
    int edges[MAXV][MAXV];  //顶点关系的矩阵
    int n,e;                //定点数和边数
}MatGraph;

邻接矩阵特点:

  • 不论边的数目是多少,邻接矩阵的存储空间都是O(n²),因此邻接矩阵适合存边多的稠密图。
  • 无向图邻接矩阵一定是对称矩阵,我们只需要存上三角或下三角。
  • 邻接矩阵主对角线元素一定是0.
  • 邻接矩阵第i行或第i列的非0非∞元素的个数是顶点i的度(无向图)或出度/入度(有向图)
  • 邻接矩阵可以很容易知道 两顶点间是否有边,以及 顶点的度。时间复杂度为O(1)。

2.邻接表

邻接矩阵存放边较少的图时,很浪费空间,如图。边矩阵种只有<v1,v0>的9是有用的,其他数据都没用

我们可以采用链式存储结构的邻接表来存放图。同样需要存顶点和边。

不带权图

  • 看上图,边表我们需要adjvex存放其中一个邻接点的下标,以及next域指向下一个边表。
//边表
typedef struct ENode{
    int adjvex;           //存放邻接点的下标
    struct ENode * next;  //指向下一个边表
}EdgeNode;
  • 每个顶点,我们需要存放顶点的信息,还需要存放指向的第一个边表的指针。
//一个顶点
typedef struct VNode{
    int data;             //存放顶点信息
    EdgeNode *firstedge;  //指向第一个边表
}VertexNode;
  • 最后,我们用一维数组来存放顶点(邻接矩阵浪费空间的是边矩阵,不是顶点数组,用数组存放顶点方便我们读取顶点信息),再存放当前顶点数和边数,构成完整的图
//完整图:全部顶点+顶点数边数
typedef struct {
  VertexNode adjlist[MAXV]; //顶点数组
  int n,e;                  //顶点数、边数
}AdjGraph;

全部代码:

#define MAXV 100       //最大顶点数
#define INF 32767      //定义∞

//边表
typedef struct ENode{
    int adjvex;           //存放邻接点的下标
    struct ENode * next;  //指向下一个边表
}EdgeNode;

//一个顶点
typedef struct VNode{
    int data;             //存放顶点信息
    EdgeNode *firstedge;  //指向第一个边表
}VertexNode;

//完整图:全部顶点+顶点数边数
typedef struct {
  VertexNode adjlist[MAXV]; //顶点数组
  int n,e;                  //顶点数、边数
}AdjGraph;

带权图

和不带权图唯一区别在于边表加了weight用于存放权值。其他都一模一样

//边表
typedef struct ENode{
    int adjvex;           //存放邻接点的下标
    int weight;           //存放权值
    struct ENode * next;  //指向下一个边表
}EdgeNode;

三.图的基本运算

主要掌握:图的创建、图的输出、图的销毁。

1.图的创建

邻接矩阵(无向带权图)的创建

思路:让用户输入需要的顶点数和边数,之后让用户依次输入顶点所带数据,保存在顶点数组中。将矩阵初始化(全0或全∞,看是否带权),然后让用户输入邻接矩阵,(x,y)以及权值w,如果不带权则不需要输入w,设为1即可。

//邻接矩阵的创建——无向带权图
void CreateMGraph(MatGraph *G){
    int i,j,w;
    //确定边数和定点数
    printf("请输入边数和顶点数:");
    scanf("%d,%d",&G->e,&G->n);
    //输入全部顶点
    printf("请输入所有顶点的数据");
    for(i=0;i<G->n;i++)
        scanf("%d",&G->vexs[i]);
    //将邻接矩阵初始化,因为是无向带权图,全部初始化为∞,
    for(i=0;i<G->n;i++)
        for(j=0;j<G->n;j++)
            G->edges[i][j] = INF;
    //输入邻接矩阵的数据
    for(int k=0;k<G->e;k++){
        printf("输入边(vi,vj)的下标i和j以及权w:");
        scanf("%d,%d,%d",&i,&j,&w);
        G->edges[i][j] = w;
        G->edges[j][i] = G->edges[i][j];    //因为无向图是对称矩阵
    }
}

邻接表(无向不带权图)的创建

思路:开始时和上面的一样, 让用户输入需要的顶点数和边数,之后让用户依次输入顶点所带数据,保存在顶点数组的data域中,同时将顶点数组的firstedge域初始化为NULL。然后建立边表:让用户输入哪两个点 i 和 j 之间存在边,然后用i指向j和j指向i创建两个边表(因为是无向图,如果是有向图,创建一个边表即可) 。

注:创建边表的过程类似于链表的头插法。

//邻接表的创建——无向不带权图
void CreateALGraph(AdjGraph *G){
    int i,j;
    //确定边数和定点数
    printf("请输入边数和顶点数:");
    scanf("%d,%d",&G->e,&G->n);
    //输入全部顶点,将firstedge域初始化为NULL
    printf("请输入所有顶点的数据");
    for(i=0;i<G->n;i++) {
        scanf("%d", &G->adjlist[i].data);
        G->adjlist[i].firstedge = NULL;
    }
    //建立无向图边表
    for(int k=0;k<G->e;k++){
        printf("输入边(vi,vj)的下标i和j:");
        scanf("%d,%d",&i,&j);
        //创建两个边表
        EdgeNode *e;
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = G->adjlist[i].firstedge;  //这两行类似于链表的头插法
        G->adjlist[i].firstedge = e;
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->adjlist[j].firstedge;  //这两行类似于链表的头插法
        G->adjlist[j].firstedge = e;
    }
}

四.图的遍历

图的遍历和树的遍历类似,我们希望从图中的某一顶点出发遍历图中所有的顶点,且每个顶点只被访问一次,这个过程叫图的遍历。

树的根结点只有一个,且每个孩子都只有一个双亲,遍历较为简单。但图的顶点和其他多个顶点相连,很可能沿着某条路径搜索后,有顶点没遍历到就回到原顶点。因此我们需要遍历多条路径且把访问过的点做标记防止重复访问。

图的遍历有两种方案:深度优先遍历、广度优先遍历。

1.深度优先遍历(DFS)

深度优先的思想是:从任一点出发,按一定的顺序,从一条路径一直走下去,直到走不通(遇到重复点或没有边连接),则退回前一点,尝试另一条路一直走下去,走不通再退回前一点.......到最后一定能遍历所有点。

比如:我们规定右手优先原则(有多条路时,优先走最右边的路),从A开始遍历下面这个图。

其过程如下:

  • 从A沿右手到B、C、D、E、F,回到A。
  • 因为A遍历过,回到F,走另一条路到G。
  • G往右走到D,D遍历过,走另一条路到H。
  • H的三个邻接点都遍历过,回到G。
  • G的邻接点都遍历过,回到F。
  • F的邻接点都遍历过,回到E。
  • E的邻接点都遍历过,回到D。
  • 从D走到 I,此时遍历完所有顶点。

上述过程可以看作:从某初始点出发,访问其还没被访问过的邻接点,然后再以该点作为初始点,访问其还没被访问过的邻接点.......可以看到,这是个递归的过程。

深度优先——邻接矩阵

  • 首先我们需要定义一个visited数组,来标记访问过的顶点
int visited[MAXV] = {0};
  • 定义一个DFS函数用于递归

void DFS(MatGraph *G,int v) {  //传入该图,以及目前所在的顶点位置
    visited[v] = 1 ;             //标记访问过的点
    printf("%d",G->vexs[v]);       //输出该点编号
    for(int i=0;i<G->n;i++)
        if(G->edges[v][i] == 1 && visited[i] != 1)  //如果该邻接点没被访问过,则递归访问它
            DFS(G,i);
}
  • 所有点都要调用DFS递归函数,因为DFS能找出一点的所有连通的点,但如果非连通图,不遍历所有点就会出现非连通的点漏掉的情况
void DFSTraberse(MatGraph G){
    for(int i=0;i<G.n;i++)      //遍历所有的点
        if(visited[i] == 0)     //对未访问过的点调用DFS,若是连通图,只会执行依次
            DFS(&G,i);
}

总代码:

//邻接矩阵存储结构
typedef int VertexType;
typedef struct {
    VertexType vexs[MAXV];  //顶点数组
    int edges[MAXV][MAXV];  //顶点关系的矩阵
    int n,e;                //定点数和边数
}MatGraph;

//邻接矩阵
int visited[MAXV] = {0};
void DFS(MatGraph *G,int v) {  //传入该图,以及目前所在的顶点位置
    visited[v] = 1 ;             //标记访问过的点
    printf("%d",G->vexs[v]);       //输出该点编号
    for(int i=0;i<G->n;i++)
        if(G->edges[v][i] == 1 && visited[i] != 1)  //如果该邻接点没被访问过,则递归访问它
            DFS(G,i);
}

void DFSTraberse(MatGraph G){
    for(int i=0;i<G.n;i++)      //遍历所有的点
        if(visited[i] == 0)     //对未访问过的点调用DFS,若是连通图,只会执行依次
            DFS(&G,i);
}

深度优先——邻接表

邻接表深度优先遍历的代码和邻接矩阵基本一样,只是在遍历时,类似于数组和链表存储结构的差别。遍历链式存储结构需要定义一个新的结点p,通过p->next来遍历所有的结点。

//邻接表
int visited[MAXV] = {0};
void DFS(AdjGraph *G,int v) {  //传入该图,以及目前所在的顶点位置
    EdgeNode *p;
    visited[v] = 1 ;             //标记访问过的点
    printf("%d",v);       //输出该点编号
    p = G->adjlist[v].firstedge;   //p保存v的第一个邻接点
    while(p!=NULL){
        if(visited[p->adjvex] == 0) //如果该邻接点没被访问过,则递归访问它
            DFS(G,p->adjvex);
        p = p->next;            //p指向下一个邻接点
    }
}

void DFSTraberse(AdjGraph G){
    for(int i=0;i<G.n;i++)      //遍历所有的点
        if(visited[i] == 0)     //对未访问过的点调用DFS,若是连通图,只会执行依次
            DFS(&G,i);
}

2.广度优先遍历(BFS)

《啊哈!算法》:(四)搜索的第三节中,对广度优先的概念介绍得很详细,如下:

这里我们主要介绍广度优先算法在图上的具体实现代码。

  • 因为用到队列,我们先导入队列运算的代码
//队列相关运算
#define MaxSize  20   

typedef int ElemType;
typedef struct {
    ElemType data[MaxSize];    //存放队列中的数据元素
    int front, rear;        //队头和队尾指针
} SqQueue;

//初始化顺序队
void InitQueue(SqQueue *&q) {
    q=(SqQueue *)malloc(sizeof(SqQueue));
    q->front=q->rear=-1;
}

//判断队列是否为空
bool QueueEmpty(SqQueue *q) {
    return (q->front==q->rear);
}

//进队
bool enQueue(SqQueue *&q, ElemType e) {
    if (q->rear==MaxSize-1)	//队满上溢出
        return false;
    q->rear++;
    q->data[q->rear]=e;
    return true;
}

//出队
bool deQueue(SqQueue *&q, ElemType &e) {
    if (q->front==q->rear)	//队空
        return false;
    q->front++;
    e=q->data[q->front];
    return true;
}

广度优先——邻接矩阵

//邻接矩阵
void BFSTraverse(MatGraph G) {
    SqQueue *Q;
    InitQueue(Q);
    for (int i = 0; i < G.n; i++)
        if (visited[i] == 0) {          //该点i未访问过
            visited[i] == 1;            //标记此处
            printf("%d ", G.vexs[i]);
            enQueue(Q, i);              //将该点的下标值i入队
            while (!QueueEmpty(Q)) {    //队列不为空
                deQueue(Q, i);
                for (int j = 0; j < G.n; j++)
                    if (G.edges[i][j] == 1 && visited[i] == 0) {   //找到点i的未访问过的邻接点
                        visited[j] = 1; //标记该邻接点
                        printf("%d", G.vexs[j]);
                        enQueue(Q, j);  //将该邻接点进队
                    }
            }
        }
}

广度优先——邻接表

//邻接表
void BFSTraverse(AdjGraph G){
    EdgeNode *p;
    SqQueue *Q;
    InitQueue(Q);
    for(int i=0;i<G.n;i++)
        if (visited[i] == 0) {      //该点i未访问过
            visited[i] == 1;       //标记此处
            printf("%d ", G.adjlist[i].data);
            enQueue(Q, i);      //将该点的下标值i入队
            while (!QueueEmpty(Q)) {  //队列不为空
                deQueue(Q, i);
                p = G.adjlist[i].firstedge;
                while(p) {
                    if (visited[i] == 0) {   //找到点i的未访问过的邻接点
                        visited[p->adjvex] = 1; //标记该邻接点
                        printf("%d ", G.adjlist[i].data);
                        enQueue(Q, p->adjvex);    //将该邻接点进队
                    }
                    p = p->next;            //p指向下一个邻接点
                }
            }
        }
}

3.两种遍历方法的对比

两者时间复杂度上是一样的,仅是对顶点的访问顺序不同

DFS由于其易于编写(递归),易于理解的特点被广泛使用。

多数情况下运行BFS所需的内存会大于DFS需要的内存(DFS一次访问一条路,BFS一次访问多条路)

深度优先比较适合目标明确,以找目标为主要目的。广度优先比较适合在不断扩大遍历范围时找到相对优的解。

五.最短路径

在网图和非网图中,最短路径的含义是不同的。

  • 非网图:没有边上的权值,最短路径,就是指两顶点之间经过的边数最少的路径。
  • 网图:最短路径是指两顶点之间经过的边上权值之和最少的路径。

非网图的最短路径很好求,用广度优先搜索即可。而日常应用大多都是带权图,非网图也可以理解为所有的边的权值都为1的网图,显然我们研究网图更有实际意义。

对于非网图求最短路径,主要掌握下面两种算法:迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法

1. 迪杰斯特拉(Dijkstra)算法

比如我们要求下面这张图中,求v0到v8的最短路径,思路如下:

我们用v[n]数组来存v0到vn的最短距离,一开始,从v1出发,由于v0只能走到v1和v2,v[n]如下:

之后,看v1和v2能走到哪,比较最短距离更新v[n]数组。

从v1能走到v2,距离为v[1]+3=4 < v[2]=5,因此更新v[2]=4;从v1能走到v3,距离为7,更新v[3]=v[1]+7=8;v1还能走到v4,更新v[4]=v[1]+5=6

v2也能走到v1,距离为v[2]+3=8 > v[1]=1,不用更新;v2能也走到v4,距离为v[2]+1=6;v2能走到v5,更新v[5]=v[2]+7=11

此时v[n]数组为:

之后再从v3、v4、v5出发往下走,并更新数组。最后从v6、v7往下走,更新数组。得到的v[8]即为从v0到v8的最短距离:

实现代码:

  • 首先我们需要构建一个邻接矩阵,方便我们后续对图的操作(用的都是上面学过的代码)
#include <stdio.h>
#include <malloc.h>

#define MAXV 100       //最大顶点数
#define INF 32767      //定义∞

//邻接矩阵存储结构
typedef int VertexType;
typedef struct {
    VertexType vexs[MAXV];  //顶点数组
    int edges[MAXV][MAXV];  //顶点关系的矩阵
    int n,e;                //定点数和边数
}MatGraph;

//图的创建
//邻接矩阵的创建——无向带权图
void CreateMGraph(MatGraph *G){
    int i,j,w;
    //确定边数和定点数
    printf("请输入边数和顶点数:");
    scanf("%d,%d",&G->e,&G->n);
    //输入全部顶点
    printf("请输入所有顶点的数据:");
    for(i=0;i<G->n;i++)
        scanf("%d",&G->vexs[i]);
    //将邻接矩阵初始化,因为是无向带权图,全部初始化为∞,
    for(i=0;i<G->n;i++)
        for(j=0;j<G->n;j++)
            G->edges[i][j] = INF;
    //输入邻接矩阵的数据
    for(int k=0;k<G->e;k++){
        printf("输入边(vi,vj)的下标i和j以及权w:");
        scanf("%d,%d,%d",&i,&j,&w);
        G->edges[i][j] = w;
        G->edges[j][i] = G->edges[i][j];    //因为无向图是对称矩阵
    }
}

int main(){
    MatGraph  G;
    CreateMGraph(&G);
}
  • 定义两个数组,一个存最短路径权值之和,一个存最短路径的前一个元素的下标
int main(){
    MatGraph  G;
    CreateMGraph(&G);
    int v[MAXV];      //用于存储最短路径
    int path[MAXV];   //用于存储最短路径的前一个元素下标
}
  • 在定义的Dijkstra函数里,传入参数G(图),v0(起始位置),p(path[]数组),v(v[]数组)
  • 首先创建final数组用于标记顶点是否已经求过。然后对final、p、v数组进行初始化。
void Dijkstra(MatGraph G, int v0,int *p,int *v){
    int final[MAXV] ;           //用于标记已经求过的顶点
    int k;
    for(int i=0;i<G.n;i++){     //初始化
        final[i] = 0;           //final初始为0,未找到最短路径的状态
        v[i] = G.edges[v0][i];  //将与v0连通的顶点权值付给v[]
        p[i] = 0;               //路径记录初始为0
    }

    final[v0] = 1;              //v0到v0不需要路径,进行标记
} 
  • 之后,一个大的for循环遍历所有顶点,里面放两个小的for循环,一个用来找到达该顶点的最短距离,该最短距离赋值给min,该邻接顶点赋值给k;一个用来给该顶点的邻接顶点的路径值进行修正(如果v[w]>min+G.edges[k][w],则v[w]=min+G.edges[k][w]),并且在path[]数组中记录下来,p[w]=k
void Dijkstra(MatGraph G, int v0,int *p,int *v){
    int final[MAXV] ;           //用于标记已经求过的顶点
    int k;
    for(int i=0;i<G.n;i++){     //初始化
        final[i] = 0;           //final初始为0,未找到最短路径的状态
        v[i] = G.edges[v0][i];  //将与v0连通的顶点权值付给v[]
        p[i] = 0;               //路径记录初始为0
    }
    final[v0] = 1;              //v0到v0不需要路径,进行标记
    //大的for循环遍历所有顶点,套两个小的for循环
    for(int i=0;i<G.n;i++){
        int min = INF;             //用来记录离v0的距离,选取最近的
        for(int j=0;j<G.n;j++)
            if (final[j] == 0 && v[j] < min) {  //寻找离v0最近的点
                k = j;
                min = v[j];
            }
        final[k] = 1;
        for(int w=0;w<G.n;w++){    //用于修正最短路径
            if(final[w] == 0 && v[w] > min+G.edges[k][w]){
                v[w]=min+G.edges[k][w];
                p[w]=k;
            }
        }
    }
}
  • 遍历输出,完成整个最短路径求解
void Dijkstra(MatGraph G, int v0,int *p,int *v){
    int final[MAXV] ;           //用于标记已经求过的顶点
    int k;
    for(int i=0;i<G.n;i++){     //初始化
        final[i] = 0;           //final初始为0,未找到最短路径的状态
        v[i] = G.edges[v0][i];  //将与v0连通的顶点权值付给v[]
        p[i] = 0;               //路径记录初始为0
    }
    final[v0] = 1;              //v0到v0不需要路径,进行标记
    //大的for循环遍历所有顶点,套两个小的for循环
    for(int i=0;i<G.n;i++){
        int min = INF;             //用来记录离v0的距离,选取最近的
        for(int j=0;j<G.n;j++)
            if (final[j] == 0 && v[j] < min) {  //寻找离v0最近的点
                k = j;
                min = v[j];
            }
        final[k] = 1;
        for(int w=0;w<G.n;w++){    //用于修正最短路径
            if(final[w] == 0 && v[w] > min+G.edges[k][w]){
                v[w]=min+G.edges[k][w];
                p[w]=k;
            }
        }
    }
    //遍历输出最短路径
    for(int i=0;i<G.n;i++){
        printf("v%d的最短路径为:%d,它的前一个元素为%d\n",i,v[i],p[i]);
    }
}
  • 主函数调用该Dijkstra函数,测试结果:
int main(){
    MatGraph G;
    CreateMGraph(&G);
    int v[MAXV];      //用于存储最短路径
    int path[MAXV];   //用于存储最短路径的前一个元素下标
    Dijkstra(G,0,path,v);
}

输入数据,构建邻接矩阵

输出结果:

2.弗洛伊德(Floyd)算法

如果要求任一点到另一点的最短路径,思路:首先分析所有顶点经过v0到另一顶点的最短路径(比如:v2到v3经过v0的最短路径是v2->v0->v1->v3),然后分析所有顶点经过v1到另一顶点的最短路径......直到分析完所有顶点都经过v8到另一顶点的最短路径。把每次的路径值记录下来,最小值即为所有点到另一点的最短路径。

  • 因为求的是所有点到所有点的最短路径,因此要用二维数组。
  • 主函数中,我们需要定义两个二维数组v和path,分别用来记录两点间的最短路径和前一点的下标
int main(){
    MatGraph G;
    CreateMGraph(&G);
    int v[MAXV][MAXV];      //用于存储最短路径
    int path[MAXV][MAXV];   //用于存储最短路径的前一个元素下标
}
  • 初始化path和v数组:v数组初始状态应和邻接矩阵一样,path数组初始时按0,1,2,...的顺序排列,如下图。
  • 注意:二维数组初始化要用两层for循环嵌套
void Floyd(MatGraph G, int p[MAXV][MAXV],int v[MAXV][MAXV]){
    //初始化
    for(int i=0;i<G.n;i++)
        for(int j=0;j<G.n;j++){
            v[i][j] = G.edges[i][j];
            p[i][j] = j;
        }
}
  • 核心代码:三层for循环,第一层表示本次循环必须经过的点,后两层表示遍历二维数组所有点。
void Floyd(MatGraph G, int p[MAXV][MAXV],int v[MAXV][MAXV]){
    //初始化
    for(int i=0;i<G.n;i++)
        for(int j=0;j<G.n;j++){
            v[i][j] = G.edges[i][j];
            p[i][j] = j;
        }
    //核心代码
    for(int k=0;k < G.n; k++)
        for(int i=0;i<G.n;i++)
            for(int j=0;j<G.n;j++)
                if(v[i][j] > v[i][k] + v[k][j]){
                    v[i][j] = v[i][k] + v[k][j];
                    p[i][j] = p[i][k];
                }
}
  • 遍历输出,完成函数代码。
void Floyd(MatGraph G, int p[MAXV][MAXV],int v[MAXV][MAXV]){
    //初始化
    for(int i=0;i<G.n;i++)
        for(int j=0;j<G.n;j++){
            v[i][j] = G.edges[i][j];
            p[i][j] = j;
        }
    //核心代码
    for(int i=0;i < G.n; i++)
        for(int j=0;j<G.n;j++)
            for(int k=0;k<G.n;k++)
                if(v[i][j] > v[i][k] + v[k][j]){
                    v[i][j] = v[i][k] + v[k][j];
                    p[i][j] = p[i][k];
                }
    //遍历输出
    for(int i=0;i<G.n;i++) {
        for (int j = 0; j < G.n; j++)
            printf("%3d", v[i][j]);
        printf("\n");
    }
    printf("\n");
    for(int i=0;i<G.n;i++) {
        for (int j = 0; j < G.n; j++)
            printf("%3d", p[i][j]);
        printf("\n");
    }
}
  • 主函数中调用,测试结果:
int main(){
    MatGraph G;
    CreateMGraph(&G);
    int v[MAXV][MAXV];      //用于存储最短路径
    int path[MAXV][MAXV];   //用于存储最短路径的前一个元素下标
    Floyd(G,path,v);
}

输出结果:

  • 更直观地输出结果:
for(int i=0;i<G.n;i++){
        for(int j=i+1;j<G.n;j++){
            printf("v%d-v%d,权值:%d ",i,j,v[i][j]);
            int k = p[i][j];
            printf("路径为:%d",i);
            while(k!=j){
                printf("->%d",k);
                k = p[k][j];
            }
            printf("->%d\n",j);
        }
        printf("\n");
    }

输出结果:

3.两种最短路径算法比较

Dijkstra算法时间复杂度为O(n²),Floyd算法时间复杂度为O(n³)。

Dijkstra算法求的是从一个顶点到其他所有顶点的最短路径, Floyd算法求的是从所有顶点到所有顶点的最短路径。

用Dijkstra算法再加一层for循环遍历所有顶点,求到的也是所有顶点到所有顶点的最短路径,时间复杂度也变成了O(n³) 。不过Floyd算法的代码更加简洁,一般求所有顶点到所有顶点的最短路径时,用floyd算法

六.最小生成树

一个连通无向图(不包含回路),就是一棵树。

最小生成树,其实就是去掉多余的边,用权值之和最小的边使图连通。

这里我们介绍的是无向带权连通图的最短路径,需要掌握两个算法:普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

1. 普里姆(Prim)算法

思路:从任一点出发(反正最后都会遍历所有点),从最短边选择邻接点,再从这两个点选最短边的第三个邻接点,再从这三个点选最短的第四个邻接点......

如下图:从1出发,选最短边(1,2)到2。从1和2这两个点可以选的边有(1,3),(2,4),(2,3),显然最短的是(1,3)到3。此时再从1,2,3三个点出发,可以选的边有(2,4),(3,4),(3,5),选最短的(3,4)到4......

void Prim(MatGraph G){
    int min,i,j,k;
    int adjvex[MAXV];
    int lowcost[MAXV];
    lowcost[0] = 0;
    adjvex[0] = 0;
    for(i=1;i<G.n;i++){
        lowcost[i] = G.edges[0][i];
        adjvex[i] = 0;
    }
    for(i = 0;i<G.n;i++){
        min = INF;
        j = 1;k = 0;
        while(j<G.n){
            if(lowcost[j]!=0 && lowcost[j]<min){
                min = lowcost[j];
                k=j;
            }
            j++;
        }
        printf("(%d,%d)",adjvex[k],k);
        lowcost[k] = 0;
        for(j=1;j<G.n;j++){
            if(lowcost[j] != 0 && G.edges[k][j]<lowcost[j]){
                lowcost[j] = G.edges[k][j];
                adjvex[j] = k;
            }
            
        }
    }
}

2. 克鲁斯卡尔(Kruskal)算法

思路:要想让n个顶点的图连通,至少需要n-1个边。我们先把所有边的权值进行排序,从小到大开始选,如果选的两点已经连通则跳过,直到选了n-1条边且能让整个图连通。

比如:我们要找上面那个树的最小生成树。先对所有的边权值进行排序。

按从小到大,我们依次选用1 2和1 3,4 6,5 6,当要选2 3时,发现2 3已经通过1 2和1 3连通了,因此跳过2 3,同样4 5也通过4 6和5 6连通了,不能选,继续选3 4,这时已经选了n-1=8条,图已经连通,不用再选了。

整个过程的关键在于:如何判断两个顶点是否已经连通。我们可以用之前树章节学过的并查集,判断是否两点都在同一集合中即可。

代码:

  • 为了方便排序,我们定义一个结构体来存储 两个邻接点和权值
typedef struct {
    int begin;
    int end;
    int weight;
}Edge;
  • 我们首先需要用该结构体定义一个数组Edges并初始化,begin是邻接矩阵的y轴(vexs[i]),end是邻接矩阵的x轴(vexs[j]),weight是邻接矩阵的值(vexs[i][j])。
void Kruskal(MatGraph G){
    Edge Edges[MAXV];    //定义边集数组
    //初始化Edges数组
    int k = 0;
    for (int i=0; i < G.n;i++)
        for (int j = 0; j < G.n; j++)
            if(G.edges[i][j] != INF) {
                Edges[k].begin = i;
                Edges[k].end = j;
                Edges[k].weight = G.edges[i][j];
                k++;
            }
}
  • 对Edges数组根据wight值进行排序(这里采用直接插入排序)
void Kruskal(MatGraph G){
    Edge Edges[MAXV];    //定义边集数组
    //初始化Edges数组
    int k = 0;
    for (int i=0; i < G.n;i++)
        for (int j = 0; j < G.n; j++)
            if(G.edges[i][j] != INF) {
                Edges[k].begin = i;
                Edges[k].end = j;
                Edges[k].weight = G.edges[i][j];
                k++;
            }
    //根据Edges的权值进行排序,直接插入排序
    int j;
    Edge new_edge;
    for (int i = 0; i < G.n; ++i)
        if (Edges[i].weight < Edges[i - 1].weight) {
            new_edge = Edges[i];
            for (j = i - 1; Edges[j].weight > new_edge.weight; j--)
                Edges[j + 1] = Edges[j];
            Edges[j + 1] = new_edge;
        }
}
  • 利用并查集。先定义并初始化一个并查集,从头依次遍历已排序的Edges数组,如果begin和end不在一个集合里,则把它们输出,同时并在一个集合
//并查集相关函数
typedef struct {		//并查集类型定义
    int parent[MAXV];		//双亲指针数组
} MFSets;

void initMFSets (MFSets& S, int n ){   //初始化
    for ( int i = 0; i < n; i++ )
        S.parent[i] = -1;	       //每个自成单元素集合
}

int find (MFSets& S, int x ) {

    while (S.parent[x] >= 0)    //函数从x开始,沿双亲链搜索到树的根
        x = S.parent[x];	//根的parent值小于0
    return x;
}

int merge(MFSets& S, int R1, int R2) {
    //把两个不相交集合R1与R2合并为一个集合。
    int x = S.parent[R1] + S.parent[R2];    //元素总个数
    if ( S.parent[R1] <= S.parent[R2] ) {   //R1的元素多
        S.parent[R1] = x;                   //R1成为合并后的根
        S.parent[R2] = R1;
        return R1;
    }
    else {		  	            //否则R2的元素多
        S.parent[R2] = x;   	            //R2成为合并后的根
        S.parent[R1] = R2;
        return R2;
    }
}
void Kruskal(MatGraph G){
    Edge Edges[G.e];    //定义边集数组
    //初始化Edges数组
    int k = 0;
    for (int i=0; i < G.n;i++)
        for (int j = 0; j < G.n; j++)
            if(G.edges[i][j] != INF) {
                Edges[k].begin = i;
                Edges[k].end = j;
                Edges[k].weight = G.edges[i][j];
                k++;
            }
    //根据Edges的权值进行排序,直接插入排序
    int j;
    Edge new_edge;
    for (int i = 0; i < G.e; ++i)
        if (Edges[i].weight < Edges[i - 1].weight) {
            new_edge = Edges[i];
            for (j = i - 1; Edges[j].weight > new_edge.weight; j--)
                Edges[j + 1] = Edges[j];
            Edges[j + 1] = new_edge;
        }
   //并查集  
    MFSets parent;              //定义一个并查集
    initMFSets(parent,G.n);     //并查集初始化
    for(int i=0;i<G.n;i++){     //从头依次遍历已排序的Edges数组
        int n = Edges[i].begin;
        int m = Edges[i].end;
        if(find(parent,n) != find(parent,m)){   //如果begin和end不在一个集合里
            merge(parent,n,m);                  //则把它们并在一个集合
            printf("(%d,%d)",n,m);              //同时把它们的顶点信息输出
        }
    }
}
  • 测试代码:输入下图的顶点与边的数据
此图片的alt属性为空;文件名为image-109.png
  • 输出结果: