图论算法(C版)

1.1、prim算法:无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。

如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。

【Prim算法思想】任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。

【最小生成树算法实例】现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。

在分析了这张图后发现，任一对城市都是连通的。

现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。

【输出】连通所有城市的公路最小造价。

【输入样例】6 101 2 101 5 191 6 212 3 52 4 62 6 113 4 64 5 184 6 145 6 33【输出样例】50 原图最小生成树#include<cstdio>#include<string>#include<cstring>#include<climits>using namespace std;int i,j,k,n,m,mi,t,s,a[1000][1000]; void prim(){int mi,p,f,k,d[1000];bool v[1000];memset(v,false,sizeof(v));f=1;for (i=2;i<=n;i++){d[i]=INT_MAX;}d[f]=0;s=0;for(i=1;i<=n;i++){mi=INT_MAX;for (j=1;j<=n;j++)if ((v[j]==false) && (d[j]<mi)){p=j;mi=d[j];}s+=mi;v[p]=true;for(j=1;j<=n;j++){if (a[p][j]<d[j]) d[j]=a[p][j];}}}int main(){memset(a,0,sizeof(a));scanf("%d%d",&n,&m);mi=INT_MAX;for (i=1;i<=n;i++){for (j=1;j<=n;j++){a[i][j]=INT_MAX;}}for (i=1;i<=m;i++){scanf("%d%d%d",&k,&j,&t);if ((t<a[k][j])||(t<a[j][k])){a[k][j]=t;a[j][k]=a[k][j];}}prim();printf("%d",s);return 0;}1.2、克鲁斯卡尔算法假设N=(V,{E})是连通网，将N中的边按权值从小到大的顺序排列；①、将n个顶点看成n个集合；②、按权值小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边的集合中。

图论算法之（割点）我们在做dfs的时候，当访问到⼀个节点时，会出现四种情况：1.此节点未被访问过，则此次的访问关系边（发起点——>接受点）称为树边（tree edge）；(未进栈节点)2.此节点被访问过但此节点的⼦孙还没访问完，换句话说，此次的发起点的源头可以追溯到接收点，则此次访问关系边称为后向边（back edge）（栈中节点）；3.此节点被访问过且此节点的⼦孙已经访问完，⽽且发起点是搜索初始边，则称为前向边（down edge）（出栈节点）；4.此节点被访问过且此节点的⼦孙已经访问完，⽽且发起点不是搜索初始边，则称为交叉边（cross edge）（出栈节点）。

其实这种分类只是相对的，也会随着dfs的改变⽽改变，⽐如搜索⼊⼝、搜索顺序等。

（其中，在⽆向图中，交叉边不存在，想⼀想，为什么）从⼀到题说起：所谓割点，就是⼀个连通⽆向图中，删除某⼀点和与它连接的所有的边后，剩下的点不再连通，则这个点是关节点。

题⽬：给定⽆向图的点数（N），边数（M），以及M条边，输出图的所有关节点，以由到⼤输。

N<=100000，M<=300000样例：输⼊：10 172 12 62 83 23 54 24 75 35 46 37 17 27 37 58 29 610 8输出：32 6 8样例第⼀⾏为N和M，接下来M⾏为M条边。

输出第⼀⾏为割点个数，接下来由⼩到⼤输出割点的编号。

⼀看到这道题，就想，把任意⼀个点给去掉，然后遍历⼀次，看是否位连通图，如果不是，就是割点。

但是这样的复杂度是O(n(n+m))严重超时好吧，我们务必要钻研出dfs的特性，使之在线性时间，即O(n+m)时间内求出割点第⼀我们知道在遍历时⼀定会出现割点吧，这不是废话吗然后我们想根节点的成为割点的条件，必须是有＞2个⼉⼦节点才可以吧(*^▽^*)然后，就是在搜索时，怎么判断⼀个点就是割点呢定理：在⽆向图的连通图G中，当且仅当⼀个点u存在⼀个可遍历的后代节点v⽆法连回⼀个⽐u更⽼的节点时，这个点u就⼀个割点证明：考虑u的任意⼦节点v。

图论算法图论算法在计算机科学种扮演者很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。

很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。

遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。

特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization ）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network ）。

与图和网络相关的最优化问题就是网络最优化或称网络优化 （netwok optimization ）问题。

哥尼斯堡七桥问题就是一个典型的例子。

在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回 到起点。

当 然可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。

欧拉为了解决这个问题，采用了建立数学模型的方法。

他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。

问题成为从任一点出发一笔画出七条线再回到起点。

欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。

深度优先搜索、广度优先搜索、无向图、有向图、最小生成树、最短路径。

求最短路迪克斯特拉（Dijkstra ）算法，其基本思想是按距0u 从近到远为顺序，依次求得0u 到G 的各顶点的最短路和距离，直至0v （或直至G 的所有顶点），算法结束。

为避免重复并保留每一步的计算信息，采用了标号算法。

下面是该算法。

(i) 令0)(0=u l ，对0u v ≠，令∞=)(v l ，}{00u S =，0=i 。

图论中的常用经典算法第一节最小生成树算法一、生成树的概念若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。

在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。

对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。

要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。

由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。

如下图：但不管如何，我们都可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。

二、求图的最小生成树算法严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。

对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。

求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。

例1、城市公交网[问题描述]有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。

现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。

[输入]n（城市数，1<=n<=100）e（边数）以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。

图论的基础概念和算法图论是数学的一个分支，研究的对象是图。

图是由一组互不相连的节点（顶点）和连接这些节点的边（边）组成的数学结构。

图论的基础概念包括顶点、边、路径、环、度数等。

本文将介绍图论的基础概念以及常用的图算法。

一、基础概念1. 图的定义和表示图由顶点集合和边集合组成。

顶点集合用V表示，边集合用E表示。

图可以用邻接矩阵或邻接表来表示。

邻接矩阵是一个二维数组，用来表示图中顶点之间的连接关系。

邻接表是一个链表数组，用来表示每个顶点相邻顶点的列表。

2. 顶点和边顶点是图的基本组成单位，用来表示图中的一个节点。

边是连接两个顶点的线段，用来表示两个顶点之间的关系。

3. 路径和环路径是由一系列相邻顶点连接而成的顶点序列。

路径的长度是指路径上经过的边的数目。

环是起点和终点相同的路径。

4. 度数顶点的度数是指与其相邻的边的数目。

入度是指指向该顶点的边的数目，出度是指由该顶点指向其他顶点的边的数目。

图中顶点的度数可以用来判断顶点的重要性。

二、常用算法1. 广度优先搜索（BFS）广度优先搜索是一种用来遍历和搜索图的算法。

从一个起始顶点开始，逐层扩展，先访问距离起始顶点最近的顶点，然后访问它们的相邻顶点，并逐渐向外扩展。

广度优先搜索可以用来计算两个顶点之间的最短路径。

2. 深度优先搜索（DFS）深度优先搜索是另一种常用的图遍历算法。

从一个起始顶点开始，沿着一条路径尽可能深入地访问图，直到不能再继续深入为止，然后回溯到上一个顶点，继续探索其他路径。

深度优先搜索可以用来计算连通分量、拓扑排序和寻找环等。

3. 最小生成树最小生成树是指图中通过连接所有顶点的子图，并且该子图的边权重之和最小。

常用的最小生成树算法包括Prim算法和Kruskal算法。

Prim算法从一个顶点开始，逐步扩展最小生成树的边，直到包含所有顶点为止。

Kruskal算法则是从边的权重最小的边开始，逐步增加边到最小生成树中，直到包含所有顶点为止。

4. 最短路径算法最短路径算法用来计算两个顶点之间的最短路径。

图论中的概念及重要算法常州一中林厚从ch1、图论中的基本概念一、图的概念简单讲，一个图是由一些点和这些点之间的连线组成的。

严格意义讲，图是一种数据结构，定义为：graph=（V，E），V是点（称为“顶点”）的非空有限集合，E是线（称为“边”）的集合，边一般用（v x，v y）表示，其中v x，v y属于V。

图（A）共有4个顶点、5条边，表示为：V={v1，v2，v3，v4}，E={（v1，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v4）}二、无向图和有向图如果边是没有方向的，称此图为“无向图”，如图（A）和图（C），用一对圆括号表示无向边，如图（A）中的边（v1，v2），显然（v x，v y）和（v y，v x）是两条等价的边，所以在上面E的集合中没有再出现边（v2，v1）。

如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图（B）中的边<v1，v2>。

把边<V x，V y>中V x称为起点，V y称为终点。

显然此时边<v x，v y>与边<v y，v x>是不同的两条边。

有向图中的边又称为弧，起点称为弧头，终点称为弧尾。

图（B）表示为：V={v1，v2，v3}，E={<v1，v2>，<v1，v3>，<v2，v3>，<v3，v2>}如果两个顶点U、V之间有一条边相连，则称U、V这两个顶点是关联的。

三、带权图一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边的权。

边上带有权的图称为带权图，也称为网（络）。

四、阶图中顶点的个数称为图的阶。

图（A）、图（B）、图（C）的阶分别为4、3、5。

五、度图中与某个顶点相关联的边的数目，称为该顶点的度。

度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。

哈密尔顿环c算法全文共四篇示例，供读者参考第一篇示例：哈密尔顿环（Hamiltonian cycle）是图论中一个重要的概念，指的是图G中一条包含所有顶点且恰好经过一次的环。

哈密尔顿环问题是一个NP难题，即目前尚未找到有效的多项式时间算法来解决该问题。

寻找哈密尔顿环的有效算法一直是图论领域的热门研究方向之一。

在图论中，哈密尔顿环的存在性和性质一直备受关注。

给定一个图G，如果存在一个哈密尔顿环，那么这个图被称为哈密尔顿图；如果不存在哈密尔顿环，但是对于图中的任意两个不同的顶点u和v，存在经过这两个顶点的哈密尔顿路径（即包含u和v并且其余顶点均不重复的路径），则称之为哈密尔顿连通图。

哈密尔顿图和哈密尔顿连通图是图论中两个非常重要的概念，它们的研究对于理解各种应用问题具有重要的意义。

现在我们来介绍一种经典的哈密尔顿环算法——C算法。

C算法是一种基于回溯思想的搜索算法，它通过递归地搜索图中的所有可能的路径来找到哈密尔顿环。

虽然C算法在最坏情况下可能需要指数级的时间复杂度来解决哈密尔顿环问题，但是在实际应用中，它仍然是一种较为有效的方法。

C算法的基本思想是从图中的任意一个顶点开始，逐步向下一个未访问的顶点移动，并判断是否满足环的条件。

在搜索过程中，如果无法找到符合条件的路径，则回退到上一个节点，继续向其他未访问过的节点探索。

通过递归的方式，C算法最终可以找到所有可能的哈密尔顿环。

在实际应用中，C算法通常需要配合一些剪枝策略来提高搜索效率。

在搜索过程中，可以根据一些启发式规则来减少搜索空间，从而快速排除不可能存在哈密尔顿环的路径。

还可以利用一些局部优化技巧，如动态规划、记忆化搜索等，来加速查找哈密尔顿环的速度。

虽然C算法在最坏情况下的时间复杂度较高，但在实际应用中，它仍然是一种可行的方法。

通过合理设计剪枝策略和优化技巧，我们可以提高C算法的搜索效率，从而更快地找到哈密尔顿环。

在解决具体问题时，我们可以根据实际情况选择不同的搜索策略和优化方法，以达到更好的效果。