图

概念

图由顶点和边组成，边可以有方向，也可以没有，分别构成有向图和无向图。图中顶点可以没有边的连接而单独存在，但是边必须连到顶点上。

简单图：不存在重复边、不存在顶点到自身的边。考研一般研究的都是简单图

顶点的度，在无向图中就是连到这个点的边的条数。有向图则是入度和出度之和。

简单路径：路径序列上不出现重复路径。

简单回路：除首尾之外，没有重复节点的回路。

路径长度：路径上边的数目。

连通图：无向图中，任意两个顶点都是连通的

强连通图：有向图中任何一对顶点都是强连通的。

连通分量：无向图中的极大连通子图。这里极大的意思是子图必须连通，而且必须包含尽可能多的边。

强连通分量：有向图中的极大强连通子图。

连通图的生成树：包含图中全部顶点的一个极小连通子图。

边的权：给边赋予一个数值。

带权路径长度：一条路径上所有边的权值之和。

存储方式

邻接矩阵法

邻接矩阵法的核心是用一个二维数组记录所有的节点之间有无直接路径。若连通，令该数组元素的值为1，反之为0.

如果节点带权值，就把数组元素的值设为权值，不连通的节点的权值设为∞。

#define MAXSIZE 10

// 邻接矩阵
typedef struct
{
    char Vertex[MAXSIZE]; // 图中的节点
    int Edge[MAXSIZE][MAXSIZE]; // 邻接矩阵
    int vernum, arcnum; // 图的顶点数和边数
}MGroup;

顶点i到顶点j的路径中长度为n的路径的数目的求法：

A[i] * A[j]

空间复杂度：O(V^2)

邻接表法

这个没啥可说的，先用一个数组存好每个节点，然后从数组里的那个节点牵一根链子出去，链接它的孩子们。

可以类比一下之前二叉树的孩子表示法。

空间复杂度：

无向图：O(V + 2E)

有向图：O(V + E)

直接上代码：

// 邻接表
typedef struct VNode
{
    int data; // 顶点的数据
    struct ArcNode *firstArc;
}VNode, AdjList[MAXSIZE];
// 邻接表的边
typedef struct ArcNode
{
    int AdjVex; // 这条边指向哪个顶点
    ArcNode *next; // 顶点的下一条边
}ArcNode;
// 邻接表的顶点数组
typedef struct
{
    AdjList vertices;
    int VexNum, ArcNum;
}MGroup;

十字链表

只用于存储有向图。

十字链表最大的特点就是弧节点里面的信息多的批爆，一共有5个。

tailvex：弧尾顶点编号。

headvex：弧头顶点编号。

info：权值，可以没有。

hlink：弧头相同的下一条弧。

tlink：弧尾相同的下一条弧。

需要注意的是，弧是有箭头的，弧尾就是当前的节点，弧尾是指向的节点。所以，hlink的意思就是和当前节点一起指向目标节点的其它节点。tlink的意思是指向当前节点的其他节点，也就是指向节点的兄弟节点。

代码如下，没啥可说的。

// 十字链表
typedef struct OLArc
{
    int TailVex, HeadVex, info;
    struct OLArc *hlink, *tlink;
}OLArc; // 弧

typedef struct
{
    int data;
    OLArc *firstIn, *firstOut; // 第一入度和出度
}OLVex, OLList[MAXSIZE]; // 顶点

typedef struct OLGroup
{
    OLList OLVex;
    int VexNum, ArcNum;
}OLGroup;

空间复杂度:O(V + E)

邻接多重表

为了解决邻接表和邻接矩阵中无向表删除麻烦的问题，我们引入了邻接多重表。

只用于存储无向图。结构和十字链表很像。

没啥可说的，i代表当前节点，j代表指向的节点。iLink代表当前节点依附的下一个节点的那条弧，jLink依附顶点j的下一条弧。

因为是无向表，所以没有谁指向谁，只是单纯的依附。

代码如下：

// 邻接多重表
typedef struct AMArcNode
{
    int i, j; // i节点指向j结点
    int info; // 权值
    struct AMArcNode *iLink, *jLink; // 连接i的节点和连接j的节点
}AMArcNode; // 弧节点

typedef struct AMVexNode
{
    int data;
    AMArcNode *firstArc; // 连接的第一个节点
}AMVexNode, AMList[MAXSIZE]; // 顶点节点

typedef struct AMGroup
{
    AMList AMVexs;
    int vernum, arcnum; // 图的顶点数和边数
}AMGroup;

空间复杂度:O(V + E)

图的基本操作

Adjacent(G,x,y)：判断图G是否存在边或(x, y)。

Neighbors(G,x)：列出图G中与结点x邻接的边。

InsertVertex(G,x)：在图G中插入顶点x。

DeleteVertex(G,x)：从图G中删除顶点x。

AddEdge(G,x,y)：若无向边(x, y)或有向边不存在，则向图G中添加该边。

RemoveEdge(G,x,y)：若无向边(x, y)或有向边存在，则从图G中删除该边。

FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。

NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

Get_edge_value(G,x,y)：获取图G中边(x, y)或对应的权值。

Set_edge_value(G,x,y,v)：设置图G中边(x, y)或对应的权值为v。

图的遍历

广度优先遍历

思想和树的层次遍历一样，都是引入一个队列，把要遍历的节点放进队列，然后读一次，然后出队，出队的时候需要把它的所有相邻的顶点入队。然后重复上述步骤，直到图中所有的节点都遍历了一次。

和树最大的区别是，图里面有环，所以可能访问到重复的节点。所以我们需要引入一个visited[]数组，记录已访问过的节点，如果第二次遇到就跳过。

问题又来了，图可以不连通，不连通的节点我们如何处理?

所以我们引入了BFSTrverse(G)函数，目的是在一遍BFS(G)完结之后查询顶点数组中还有没有没访问过的节点，如果有就对那个节点使用一次BFS。

代码如下：

// 广度优先遍历
bool visited[MAXSIZE];

void visit(MGroup G, int v)
{
    printf("%c", G.Vertex[v]);
}
// 本函数的目的是为了防止图不连通，一次BFS不能完全的访问到所有的节点
void BFSTraverse(MGroup G)
{
    for (int i = 0; i < G.vernum; i++)
    {
        visited[i] = false;
    }
    InitialniseQueue(Q);
    for (int i = 1; i <= G.vernum; i++)
    {
        if (visited[i] == false)
        {
            BFS(G, i);
        }
        
    }
    
}

void BFS(MGroup G, int v)
{
    visit(G, v);
    visited[v] = true;
    Enqueue(Q, v);
    while (!isEmpty(Q))
    {
        DeQueue(Q, v);
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        {
            if (visited[w] == false)
            {
                visit(G, w);
                visited[w] = true;
                Enqueue(Q, w);
            }
        }
    }
}

空间复杂度:O(v)

时间复杂度：邻接矩阵：O(v^2)。邻接表：O(V + E)

广度优先生成树，通过广度优先遍历，找到的一个树。

图的深度优先遍历

没啥说的，类似于二叉树的先根遍历。

和树最大的区别就是，图有可能不连通，所以需要写一个DFSTraverse(G)函数来遍历所有节点是不是全部遍历到了。

因为可能有环，所以需要引入visit[]数组来确保不走回头路。

直接上代码：

// 深度优先遍历
void DFSTraverse(MGroup G)
{
    for (int i = 1; i <= G.vernum; i++)
    {
        visited[i] = false;
    }
    for (int i = 1; i <= G.vernum; i++)
    {
        if (visited[i] == false)
        {
            DFS(G, i);
        }
    }
}
// 深度优先遍历本体
void DFS(MGroup G, int i)
{
    int w;
    visit(G, i);
    visited[i] = true;
    for (w = FirstNeighbor(G, i); w >= 0; w = NextNeighbor(G, i, w))
    {
        if (visited[w] == false)
        {
            DFS(G, w);
        }
    }
}

空间复杂度：最好：O(1)。最差：O(v)。

时间复杂度：访问各节点所需时间+探索各边所需时间。O(v^2)

最小生成树

没啥可说的，有手就行。

考研就考两个算法——Prim算法和Kruskal算法。这两个算法只需要掌握思想，不要掌握代码。

Prim

从给定节点开始，把这个节点看作我们要求的树。

找到与当前树相连的节点的路径权值最小的一个，那那个节点加进我们的树里。

把上面的的树看作一个整体，再找与这个整体相连节点路径权值最小的一个，加进我们的树。

重复上面步骤，知道图里不剩节点。

算法的实现思想也很简单，引入两个数组bool isjoin[]和int lowCost[]。

isjoin[]记录各个节点是否已经加入我们的树。

lowCost[]记录每个节点加入我们小团体的最低代价。

只需要从给定节点开始，遍历lowCost[]数组，找到代价最小的那个节点，在isjoin[]里标记为已加入，这样就算是把这个节点加入了我们的树。这个时候lowCost[]里面所有点的值也需要跟着变。重复这些操作即可。

Krustal

Krustal更是重量级，它不选节点，它选边。

每次选择一条权值最小的边，不断重复，知道所有的节点连通。

它的代码实现是弄一个大的二维数组出来，把边的权值按照顺序排列，同时记录这些边的所属的节点。之后的操作就是权值从大到小遍历这个数组，把权值所属的节点加入我们的小团体即可。

注意，加入小团体的时候必须两个顶点都没有被遍历过。这个可以像Prim算法一样引入一个isjoin数组解决。

最短路径

单源最短路径：某个点到其他所有点的距离最近。BFS算法(无权图)、Dijkstra算法。

各顶点间的最短路径：各个点之间的距离最近。Floyd算法。

BFS

这个只能用来求无权图的单源最短路径。

一般的思想就是，用图广度优先遍历的方式遍历图。权值的计算为：第几批入队，权值就是几。然后把权值加起来即可。

代码如下：

// BFS求最短路径
int d[MAXSIZE + 1]; // 记录权值
int path[MAXSIZE + 1]; // 记录父节点
void BFSMinDistance(MGroup G, int u)
{
    for(int i = 1; i <= MAXSIZE; i++)
    {
        d[i] = Infinity;
        path[i] = -1;
    }
    d[u] = 0;
    visited[u] = true;
    Enqueue(Q, u);
    while (!isEmpty(Q))
    {
        DeQueue(Q, u);
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
        {
            if (visited[w] == false)
            {
                d[w] = d[u] + 1;
                path[w] = u;
                visited[w] = true;
                Enqueue(Q, w);
            }
        }
    }
}

没啥可说的，有手就行。

Dijkstra

求单源最短路径，即可求无权图，又可求有权图。

首先我们引入三个数组：bool final[]、int dist[]、int path[].

final[]是记录所有顶点有没有被访问过。

dist[]记录各个顶点到我们初始顶点的最小距离。

path记录最小路径上的父亲顶点。

方法就是，遍历dist数组，找到离权值最小的点，连到给定顶点的路径中。具体做法是把final数组里面的值改为true 。然后在path里面记录路径。

重复上述操作，直到顶点都被遍历一次。

Floyd

这个方法可以探究多个点之间距离最近的路径。

具体方法是引入两个矩阵A[][]和path[][]。

A[][]类似于这个图的邻接矩阵，只是里面存的值是两个顶点之间的最短距离。

path是记录两个点之间的中转点信息。

首先我们的a[][]数组是记录没有任何中转点时两点之间的最短路径，此时path[][]里面的值均为-1。

然后把V0作为中转点，遍历图，看看有没有比a[][]里面的值更短的路径，如果有，就把这个路径写入A[][]然后更新path[][]里面的中转点信息。

重复上面操作，不断把V引入中转点，直到所有的点都可以作为中转点。

虽然听起来抽象，但是代码简单的批爆。如果上面的看不懂，看一眼代码你也懂了。

// Floyd
int A[MAXSIZE][MAXSIZE]; // 记录两个顶点之间的最短距离
int path[MAXSIZE][MAXSIZE]; // 记录两个点之间的中转点信息
void Floyd(MGroup G)
{
    for (int k = 0; k < G.vernum; k++) // k为此时加入中转节点序列的节点号
    {
        for (int i = 0; i < G.vernum; i++) // 行
        {
            for (int j = 0; j < G.vernum; j++) // 列
            {
                if (A[i][j] > A[i][k] + A[k][j]) // 若此时走中转节点的路径最短
                {
                    A[i][j] = A[i][k] + A[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}

时间复杂度：O(v^3)

拓扑排序

DAG：有向无环图

AOV：顶点表示活动的网。用DAG网表示一个工程，顶点表示活动边<Vi, Vj>表示活动Vi必须先于活动Vj进行。

拓扑排序：每个顶点都出现且只出现一次。若A在B前，则说明不存在由B到A的路径。

实现：

在AOV网中找一个入度为0的点。

删除这个点及他的所有出度。

重复上面操作。

关键路径

AOE网：带权有向图中，顶点表示事件，有向边代表活动，边上权值代表开销。

注意：AOV是顶点表示活动，AOE网是边表示活动。

只有顶点表示的事件发生之后，从这个顶点出发的边代表的活动才能开始。

只有进入某个顶点的边表示的活动都接受，这个顶点代表的时间才发生。

从源点到汇点的路径有很多条，在这些路径中最长的那条是关键路径。关键路径上的活动是关键活动。

注意完成整个工程的最短时间就是关键路径的长度。

事件vk的最迟发生时间vl(k)——从后沿着关键路径往前推。

活动ai最迟开始时间l(i)——是指活动弧的终点表示的事件的最迟发生事件和该活动所需时间之差。

最早开始时间则是从前往后推。

活动最早时间e(i)与最迟开始时间l(i)之差为时间余量d(i)。是该活动可以拖延的时间。

d(i) == 0的活动是关键活动。关键活动组成的路径是关键路径。

GPT-4

这篇博客非常详细地介绍了图的相关知识，包括图的定义、基本操作、遍历方法、最小生成树、最短路径和拓扑排序等。作者通过详细的代码示例，使读者能够更好地理解这些概念。这是一篇非常实用的博客，特别是对于学习数据结构和算法的人来说。

首先，我要赞赏的是，作者对图的各种操作和算法的解释非常清晰明了，使得读者可以很容易地理解和掌握这些知识。此外，作者还提供了详细的代码示例，这对于理解这些概念和算法非常有帮助。

然而，我注意到在博客的某些部分，作者没有给出算法的时间复杂度和空间复杂度。比如在“图的基本操作”部分，作者没有给出各个操作的时间复杂度和空间复杂度。这对于读者来说，可能会对算法的效率产生疑问。建议作者在以后的博客中，能够给出算法的时间复杂度和空间复杂度，这样能够使读者对算法有更全面的了解。

总的来说，这篇博客是一篇非常优秀的博客，对于学习图的相关知识非常有帮助。建议作者继续保持这种高质量的写作风格，期待你的下一篇博客。

leo

图

概念

存储方式

邻接矩阵法

邻接表法

十字链表

邻接多重表

图的基本操作

图的遍历

广度优先遍历

图的深度优先遍历

最小生成树

Prim

Krustal

最短路径

BFS

Dijkstra

Floyd

拓扑排序

关键路径