图的定义背景知识下面这幅图就是传说中的七桥问题（哥尼斯堡桥问题）。在哥尼斯堡，普雷格尔河环绕着奈佛夫岛（图中...

图的定义

背景知识

下面这幅图就是传说中的七桥问题（哥尼斯堡桥问题）。在哥尼斯堡，普雷格尔河环绕着奈佛夫岛（图中的A岛）。这条河将陆地分成了下面4个区域，该处还有着7座连接这些陆地的桥梁。



问题是如何从某地出发，依次沿着各个桥，必须经过每座桥且每座桥只能经过1次，最终回到原地。

不知道这个问题且好奇的童鞋现在肯定在忙活着找出来这道题的结果了。

是伟大的数学家欧拉（Leonhard Euler）在1736年首次使用图的方法解决了该问题。

欧拉将上面的模型转换成了下面这种”图“的形式。



欧拉把顶点的度定义为与该顶点相关联的边的条数，并且他证明了存在从任意点出发，经过所有边恰好一次，并最终回到出发顶点的走法的充分必要条件是：每个顶点的度均为偶数。人们称之为欧拉闭迹（Eulerian walk）。

简要定义

图（graph）G=（V，E）由顶点（vertex）的集V和边（Edge）的集E组成。顶点代表了对象，在示意图中我们使用点或圆来表示它；边代表了两个对象的连接关系，在示意图中我们使用连接两顶点的线段来表示。

有时也把边称作弧（arc），如果点对（v，w）是有序的，那么图就叫做有向的图（有向图）。如果点对(v,w)是无序的，那么图就叫做无向的图（无向图）。简单的讲，边没有指向性的图叫做无向图，边具有指向性的图叫做有向图。

顶点v和w邻接（adjacent）当且仅当（v，w）属于E。

我们可以给边赋予各式的属性，比如权值（cost）。权值可以表示从一个顶点到另一个顶点的距离，也可以表示一个顶点到另一个顶点说话费的代价（比如时间、金钱等）。一个边上带权值的图称为网络（network）。

如果无向图中从每一个顶点到其他每个顶点都存在一条路径，则称该无向图是连通的（connected）。具有这样性质的有向图称为是强连通的的（strongly connected）。如果有向图不是强连通的，但它的基础图（underlying graph）（也就是其弧上去掉方向说形成的图）是连通的，那么称该有向图是弱连通的（weakly connected）。完全图（complete graph）是其每一对顶点间都存在一条边的图。



所谓入度（indegree）是指的顶点v的边（u，v）的条数。

如下表示了一个有着7个顶点和12条边的有向图。

如果具有n个顶点，e条边的图G的顶点i的度为di，则G的边数为：

以上这个数学公式的markdown“源码”：

$ e =frac { sum_{0}^{n-1} d_i} {2} $

现在将图看作抽象数据类型，下面给出ADT图的结构：

图的存储表示方式

图主要有3种常用的存储表示方式：邻接矩阵（adjacency matrices），邻接表（adjacency lists），邻接多重表（adjacency multilists）。

邻接矩阵

邻接矩阵使用|V|∗|V|的二维数组来表示图。g[j]表示的是顶点i和顶点j的关系。

1）因为在无向图中，我们只需要知道顶点i和顶点j是否是相连的，因此我们只需要将g[j]和g[j][j]设置为1或是0表示相连或不相连即可。如下图所示。



2）而在有向图中，我们只需要知道是否有从顶点i到顶点j的边，因此如果顶点i有一条指向顶点j的边，那么g[j]就设为1，否则设为0。有向图与无向图不同，并不需要满足g[j]=g[j]。



3）在带权值的图中，g[j]表示的是顶点i到顶点j的边的权值。由于在边不存在的情况下，如果将g[j]设为0，就无法和权值为0的情况区分开来，因此选取适当的较大的常数INF（只要能和普通的权值区别开来就可以了），然后令g[j]=INF就好了。当然，在无向图中还是要保持g[j]=g[j]。在一条边上有多种不带权值的情况下，定义多个同样的|V|∗|V|数组，或者是使用结构体或类作为数组的元素，就可以和原来一样对图进行处理了。



使用这种存储方式，可以很方便地判断任意两个顶点之间是否有边以及确定顶点的度，这也是这种表示法最大的优势。任意一个顶点i的度等于其邻接矩阵中顶点i所对应的行中的数字之和：

以上这个数学公式的markdown“源码”：
$ sum_{j=0}^{n-1} g[j] $

在这种表示法中扫描所有边至少需要O(n2)时间，因为必须检查矩阵中的n2−n个元素才能确定图中边的条数（邻接矩阵对角线上的n个元素都是0，因此不用检查。又因为无向图的邻接矩阵是对称的，实际只需检查邻接矩阵的一半元素）。通常把边很少的图成为稀疏图（sparse graphs）。

邻接表

如果用邻接矩阵表示稀疏图就会浪费大量内存空间，而用链接表，则是通过把顶点所能到的顶点的边保存在链表中来表示图，这样就只需要O(|V|+|E|)的内存空间。

而所谓的邻接表，就是用n个链表代替邻接矩阵中的n行。链表中的结点结构至少要包含一个顶点域和一个链域。对于任意给定的链表i，链表中的结点就是与顶点i相邻的所有顶点。邻接表存储声明的C语言声明如下：

#define MAX_VERTICES 50
typedef struct node *node-pointer;
typedef struct node
{    int vertex;

struct node *link;
};
node_pointer graph[MAX_VERTICES];
int n=0;

邻接多重表

在无向图的邻接表存储表示中，每一条边(vi，vj) 都表示为两项：一项在顶点vi 的邻接表中，而另一项在顶点 vj 的邻接表中。在多重表中，各链表中的结点可以被几个链表共享，此时图中的每一条边只对应于一个结点，而这个结点出现在该边所关联的两个顶点的每个邻接链表中。
邻接多重表结点结构的C语言声明为：

typedef struct edge *edge-pointer
typedef struct edge
{    short int marked;

int vertex1;

int vertex2;

edge_pointer path1;

edge_pointer path2;
};

图的基本操作和算法

广度优先搜索

请先忽视下图中所有的下标，让我们从头开始。随意选择一个点，此处选择v3，作为切入点。因此到v3的距离为0。从v3出发，距离为1的结点是v1和v6；继续下一步，v6已经无路可走，而与v1距离为1的是v2和v4，因此对它们标记上2；继续下去，v2和v4走一步都可以到v5，v4走一步可以到v7，因此v5和v7被标记为3。至此搜索便结束了。

这就是广度优先搜索（breadth-first search），该方法按层处理顶点。距起始点最近的那些顶点首先被求值，最远点则最后被求值，这很像对树的层序遍历（level-order traversal）。

为了实现广度优先搜索，可以使用动态链接队列。在队列中的每个顶点都包含两个域：顶点的序号和链接指针。

函数bfs所使用的队列的定义和函数原型声明为：

typedef struct queue *queue_pointer;
typedef struct queue
{    int vertex;

queue_pointer link;
};
void addq(queue_pointer *, queue_pointer *,int);
int deleteq(queue_pointer *);

图的广度优先搜索算法：

void bfs(int v)
{

node_pointer w;

queue_pointer front,rear;

front=rear=NULL;

printf("%5d",v);

visited[v]=TRUE;

addq(&front,&rear,v);    while(front)

{

v=deleteq(&front);

for(w=graph[v];w;w=w->link)

{            if(!visited[w->vertex])

{                printf("%5d",w->vertex);

addq(&front,&rear,w->vertex);

visited[w->vertex]=TRUE;

}

}

}
}

图中每个顶点都被存入队列一次，所以该算法中的while循环至多重复n次。如果采用邻接表存储表示，那么该算法所需要的时间为：

d0+d1+…+dn−1=O(e)

其中di 为顶点 vi 的度。

而如果采用邻接矩阵来实现，那么对于每个顶点的访问，while循环的时间为O(n)，所以算法的总耗时为O(n^2) 。和接下来的深度优先搜索一样，一次广度优先搜索访问到的顶点以及与这些顶点相关联的边形成的图G的一个连通分支。

深度优先搜索

深度优先搜索内容较多，已经在下文中单独列出。

连通图

使用以上的两种搜索算法也可以用来判断一个无向图是否是连通的。具体步骤如下：

1.调用bfs(0)或dfs(0)
2.检查是否存在未被访问过的顶点

具体代码如下：

void connected(void)
{    int i;

for(i=0;idv+cv,w，然后更新到dw和pw，并在w不在队列中时将它放到队列中，可以为每一个顶点设置一个位（bit）以指示它在队列中出现的情况。

无环图

如果图是无环的，则可以通过改变声明顶点为known的顺序，或者叫做顶点选取法则来改进Dijkstra算法。这种方法通过拓扑排序来选择顶点，由于选择和更新可以在拓扑排序执行的过程中执行，因此新的算法只需要一趟就可以完成。

通过下面这个动作结点图（activity-node graph）来解释什么是关键路径分析（critical path analysis）再合适不过了。一条边（v，w）表示动作v必须在动作w开始前完成，如前面说描述的那样，这就意味着图必须是无环的。



为了进行这些运算，我们把动作结点图转化成事件结点图（event-node graph），每个事件对应于一个动作和所有与它相关的动作完成。



所以现在我们需要找出事件的最早完成时间，只要找出从第一个事件到最后一关事件的最长路径的长。因为有正值回路（positive-cost cycle）的存在最长路径问题常常是没有意义的。而由于事件结点图是无环图，那就不需要担心回路的问题了，这样一来就不用有所顾忌了。

以下是最早完成时间。



以下是最晚完成时间。



借助顶点的拓扑排序计算最早完成时间，而最晚完成时间则通过倒转拓扑排序来计算。

而事件结点图中每条边的松弛时间（slack time）代表对应动作可以被延迟而不推迟整体完成的时间量，最早完成时间、最晚完成时间和松弛时间如下所示。



某些动作的松弛时间为0，这些动作是关键性的动作，它们必须按计划结束。至少存在一条完成零-松弛边组成的路径，这样的路径是关键路径（critical path）。

网络流问题

如下左图所示，有一个顶点s，称为源点（source）；还有一个顶点t，称为汇点（sink）。对于顶点c，它最大流出2，因此它的最大流入为2，如下右图所示。而t的最大流也就是5。



要想计算最大流，同样可是使用前面的思想——分阶段进行。令开始时所有边都没有流，如下中间图所示。我们可以用残余图（residual graph）来表示对于每条边还能再添加上多少流。对于每一条边，可以从容量中减去当前的流而计算出残留的流。



第一步：假设我们选择s−b−d−t路径，此时会发出2个单位的流通过这条路径的每一边，如下中间图所示。对比左图，我们做如下约定：一旦注满（使饱和）一条边，例如a到b和b到d，就将这条边从残余图（也就是中间图）去掉，如下右图所示。



第二步：接下来选择s−a−c−t路径，此时也会发出2个单位的流通过这条路径的每一边，如下中间图所示（只看s−a−c−t即可，s−b−d−t为上一步说走过的路径）。同样将残余图更新如下右图所示。



第三步：从上图的残余图中我们已经可以看出来最后一步的唯一一种走法了，也就是从s−a−d−t。做如下图所示更新。



很显然从t无法走到s，因此算法至此便终止了。因此正好5个单位的流是最大值。前面的三步我们走的如此顺利，那么问题真的如此简单么？

如果一开始我们选择了s−a−d−t，那么算法就会失败了，因为路已经被堵死了。



为了使算法得以成功运作，那么就要让流图中具有以相反方向发送流的路径，如下所示。那么对于如下右图中的残余图而言，从d返回到a的便成了3而非4，这是因为从t流到d的流量是3个单位。现在在残余图中就有a和d之间有2个方向，或者还有1个单位的流可以从a导向d，或者是3个单位的流导向相反的反向，当然，我们也可以撤销流。



紧接着如果通过d到a导入2个单位的流，算法就会从边（a，d）取走2个单位的流，更新流图如下。

长按识别图中二维码关注我们！

    关注 无人机