prim

/*******************************
 最小代价生成树之普利姆算法思想:-----------贪心算法思想
	从图中任意取出一个顶点，把它当成一棵树，然后从与这棵树相邻接的边中选取一条最短（权值最小）
 的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到了一颗有两个顶点的树。然后从于这棵树
 相邻接的边中选取一条最短的边，并将这条边及其所连接的顶点并入当前树中，得到一棵有三个顶点的树。
 以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树。
 普利姆算法执行过程：
	从树中某个顶点V0开始，构造生成树的算法过程如下：
		1、将v0到其他顶点的所有边当做侯选边；
		2、重复以下步骤n-1次，使得其他n-1个顶点被并入生成树中。
			1）从侯选边中挑选出权值最小的边输出，并将于该边另一端相连接的顶点v并入生成树中
			2）考察所有剩余顶点vi，如果（vi,vj）的权值比lowcost[vi]小，则用（vi,vj）的权值更新lowcost[vj]
 ********************************/
 //普利姆算法的代码：
 
 struct MGraph
 {
	 int n; // 顶点总数
	 int edges[MAXSIZE][MAXSIZE];  // 边的权值
 };
 
void Prim(MGraph g,int v0,int sum)//v0是以该点为起点构造最小生成树
{
	int lowcost[MAXSIZE], vset[MAXSIZE];//vset是当前最小生成树的集合
	int i , j , k, mincost = 0;
	for (i = 0; i < g.n; ++i)
	{
		lowcost[i] = g.edges[v0][i];
		vset[i] = 0;
	}
	vset[v0] = 1;     // 将v0并入树中
	sum = 0;          // sum清零用来记录树的权值
	for (i = 0; i < g.n -1; ++i)
	{
		mincost = INF;//正无穷
		for (j = 0; j < g.n; ++j)
		{
			if (vset[j] == 0 && lowcost[j] < mincost)   // 选出当前生成树中到其余顶点最短边中的最短的一条
			{
				mincost = lowcost[j];
				k = j;
			}
		}
		vset[k] = 1;
		sum += mincost;  //此处记录了最小生成树的权值
			
		
		//以刚并入的顶点v为媒介选取新的侯选边
		for (j = 0; j < g.n; ++j)  // 执行过程中的第二步
		{
			if (vset[j] == 0 && g.edges[k][j] < lowcost[j])
			{
				lowcost[j] = g.edges[k][j];
			}
 
		}
	}
		
}
 
//解释：
/*
	普利姆算法主要部分是一个双层循环：外层循环内嵌两个并列的单层循环，单层循环内的操作都是常量级别的，
	因此普利姆算法的时间复杂度为O(n*n)。可见普利姆算法的时间复杂度只与图中的顶点数有关，与边数无关，
	所以普利姆算法适用于稠密图
*/

kruskal

/**
* 
克鲁斯卡尔算法：每次找出侯选边中权值最小的边，就将该边并入树中。重复此过程直到所有边都被检测完为止。
克鲁斯卡尔算法执行过程：
   将图中该边按照权值从小到大排序，然后从最小边开始扫描各边，病检测当前边是否为侯选边，即是否该边的
   并入会构成回路，如果不构成回路，则将该边并入当前生成树中，直到所有边都检测完为止。
   判断是否产生回路需要用到并查集。
   并查集保存了一颗或者几棵树，这些树有这样的特点：
   	1、通过树中一个节点可以找到器双亲结点，进而找到根结点（其实就是树的双亲存储结构）。
   这种特性有两个好处：
   	1、一是可以快速地将两棵个含有很多元素的集合合并为一个。两个集合就是并查集中的两棵树，只需要找到其中一棵树
   	的根，然后将其作为另一棵树中任何一个结点的孩子结点即可；
   	2、二是可以很方便地判断两个元素是否属于同一个集合。通过这两个元素所在的结点找到它们的根结点，如果它们有相同的
   	根，则说明它们属于同一个集合，否则属于不同集合。
   并查集可以用一维数组来简单的表示。
*/
struct Road
{
   int a, b; // a和b为同一条边所连接的两个顶点
   int w;    // 边的权值
   static bool  cmp(Road & a, Road & b)  //结构体比较运算子
   {
   	return a.w < b.w;
   }

};



Road road[MAXSIZE];

int  v[MAXSIZE];   // 定义并查集数组
int getRoot(int a)  //在并查集中查找根结点的算法
{
   while (a != v[a])
   {
   	a = v[a];
   }
   return a;
}

struct MGraph2
{
   int n; // 顶点总数
   int edges;  // 边的总数
};

void Kruskal(MGraph2 g,int & sum, Road road[])
{
   int i = 0; 
   int N, E, a, b;
   N = g.n;
   E = g.edges;
   sum = 0;

   for (int i = 0; i < N; ++i)
   {
   	v[i] = i;
   }
   sort(road, road + E,Road::cmp);		//对road数组的E条边按其权值从小到大进行排序
   
   for (i = 0; i < E; ++i)
   {
   	a = getRoot(road[i].a);
   	b = getRoot(road[i].b);
   	if (a != b)
   	{
   		v[a] = b;
   		sum += road[i].w;
   	}

   }

}

dijkstra

//迪杰斯特拉算法  ； 单源点最短路径
# define INF 1000000000
//dist[vi]表示当前已找到的从v0到每个终点vi的最短路径的长度
//path[vi]保存的是从v0到vi最短路径上vi的前一个顶点，初始值为：若v0到vi有边，则path[vi] = v0,否则path[vi] = -1
//set[]为标记数组，set[vi] = 0表示vi没有被纳入最终的最短路径集合中，否则表示vi已经被纳入到最短路径中
void DijKstra(MGraph g, int v, int dist[], int path[])
{
	int set[MAXSIZE];
	int min, i, j, u;
	//初始化操作
	for (int i = 0; i < g.n; ++i)
	{
		dist[i] = g.edges[v][i];
		set[i] = 0;
		if (g.edges[v][i] != INF)
		{
			path[i] = v;//和源点直接相连则说明该顶点前一个顶点为源点
		}
		else
		{
			path[i] = INF;
		}
	}
	
 
	//关键操作开始
	for (i = 0; i < g.n ; ++i)//每次选择一个离源点最近的点，一共只需选n-1次，因为源点不用算
	{
		min = INF;
		//下面这个循环每次从剩余顶点中选出一个顶点，通往这个顶点的路径在通往所有剩余顶点的路径中是长度最短的
		for (j = 0; j < g.n; ++j)
		{
			if (set[j] == 0 && dist[j] < min)
			{
				min = dist[j];
				u = j;
			}
		}
		set[u] = 1; // 将选出的顶点并入到最短路径中
		
		//下面这个循环以刚并入的顶点为中转站，对所有通往剩余顶点的路径进行检测
		for (j = 0; j < g.n; ++j)
		{
			//下面这个if语句会判断顶点u的加入是否会出现通往顶点j更短的路径，如果出现，则改变原来的路径及其长度，否则什么都不做
			if (set[j] == 0 && dist[u] + g.edges[u][j] < dist[j])
			{
				dist[j] = dist[u] + g.edges[u][j];
				path[j] = u;//能通过if的判断说明以u作为中转站能使该点到源点的距离缩短，即u作为当前点的前一个点
			}
		}
		//关键操作结束
	}
}
//迪杰斯特拉算法结束时：dist[]中存放了起点v到其余顶点的最短路径长度，path[]中存放了起点v到其余各顶点的最短路径

floyd

//弗洛伊德算法 ： 多源点最短路径算法（或者说是任意一对顶点之间的最短路径）
//弗洛伊德算法的思想：动态规划
//path[i][j]的值表示，顶点i到j路径中编号最大的中转站。
//因为第一层循环k按照0~n-1顺序逐步开放新的中转站，
//每个新中转站k若能使A[i][j]变小，
//则都会用这个新k覆盖path[i][j]的原值。
//初始化为-1表示两点间没有中转站，是直接连接着的
void Floyd(MGraph g,int path[][MAXSIZE])
{
   int i, j, k;
   int A[MAXSIZE][MAXSIZE];

   //这个双重循环对数组A[][]和Path[][]进行初始化
   for (int i = 0; i < g.n; ++i)
   {
   	for (int j = 0; j < g.n; ++j)
   	{
   		A[i][j] = g.edges[i][j];
   		path[i][j] = -1;
   	}
   }

   //下面这个三层循环是本算法的主要操作，完成了以k为中间顶点对所有顶点对（i，j）进行检测和修改
   for (k = 0; k < g.n; ++k)
   {
   	for (i = 0; i < g.n; ++i)
   	{
   		for (j = 0 ; j < g.n; ++j)
   		{
   			if (A[i][j] > A[i][k] + A[k][j])
   			{
   				A[i][j] = A[i][k] + A[k][j];
   				path[i][j] = k;
   			}
   		}
   	}
   }

}

void printpath(int start,int end)
{
   printf("%d",start);
   findpath(start,end);
}

void findpath(int start,int end)//路径
{
   if(A[start][end]<INF && path[start][end]==-1)//若两点之间有路径且没有中转站
   {											//即start==end或者两点直连
   	printf("->%d",end);//每次都输出两个直连点中的被指点
   }
   else
   {
   	int mid = path[start][end];
   	findpath(start,mid);
   	findpath(mid,end);
   }
}