图论：最短路径+最小生成树+中心度计算

包含图论众多热点问题：最短路径——Dijkstra SPFA Floyd等 最小生成树的两种计算方法、三种中心度、连通分量的计算 输入文件格式按照graph_movie.txt

#include “StdAfx.h“
#include “Algorithm.h“
///////////////////////////////////////////////////////////
////打开文件，存储图为AG，若打开失败则返回false
///////////////////////////////////////////////////////////
bool CreateGraph（Graph* AG char* filePath）
{
	FILE* fp;
	fp = fopen（filePath “r“）;
	if （fp == NULL）
	{
		return false;
	}
	fscanf（fp “%d%d\n“ &AG->vertex &AG->edge）;//记录顶点数n、边数e
	int a b;
	double c;
	AG->length = new double*[AG->vertex + 1];
	AG->connect = new int*[AG->vertex + 1];
	AG->adjoin = new vector[AG->vertex + 1];
	AG->inGraph = new int[AG->vertex + 1];
	for （int i = 0; i <= AG->vertex; i++）		//权矩阵初始化
	{
		AG->length[i] = new double[AG->vertex + 1];
		AG->connect[i] = new int[AG->vertex + 1];
		AG->inGraph[i] = 0;
		for （int j = 0; j <= AG->vertex; j++）
		{
			if （i == j）
				AG->length[i][j] = 0;
			else
				AG->length[i][j] = Infinite_Length;
			AG->connect[i][j] = 0;
		}
	}
	while （fscanf（fp “%d %d %lf\n“&a &b &c） != EOF）//无向图
	{
		AG->length[a][b] = c;
		AG->length[b][a] = c;
		AG->inGraph[a] = 1;
		AG->inGraph[b] = 1;
		AG->adjoin[a].push_back（b）;
		AG->adjoin[b].push_back（a）;
		AG->connect[a][b] = 1;
		AG->connect[b][a] = 1;
	}
	return true;
}
////////////////////////////////////////////////////////////
///////////是否已选取过每一个点//////////////////////////////
///////////////////////////////////////////////////////////
bool allPicked（int arr[] int n）	
{
	for （int i = 0; i <= n; i++）
	{
		if （arr[i]  == 0）
			return false;
		else
			continue;
	}
	return true;
}
///////////////////////////////////////////////////////////
///////Dijkstra算法；path用于存储最短路径////////////////////
///////////////////////////////////////////////////////////
double Dijkstra（Graph* AG int origin int path[]）	
{
	int* S = new int[AG->vertex + 1];		//标记图中的点，若已找到距离原点最短路径，则标记为1，否则为0
	double* path_length = new double[AG->vertex + 1];    //记录各点到达原点的最短距离

	for （int i = 0; i <= AG->vertex; i++）
	{
		S[i] =  0;	//S初始化为0
		path_length[i] = Infinite_Length;	//最短距离初始化为无穷大
		path[i] = origin;
	}
	S[origin] = 1;		//原点标记为1
	path_length[origin] = 0;
	for（int i = 0; i <= AG->vertex; i++）  //令path_length为各点到原点距离
	{
		path_length[i] = AG->length[origin][i];
	}
	int j = 0;
	double min_length = Infinite_Length;	//最短路径长
	int count = AG->vertex + 1;
	while（count）
	{
		count--;
		min_length = Infinite_Length;
		for （int i = 0; i <= AG->vertex; i++） //求minPi（i）
		{
			if （S[i] == 1）
				continue;
			if （path_length[i] < min_length）
			{
				j = i;
				min_length = path_length[i];
			}
		}
		S[j] = 1;	//标记找到最短路径的点
		if （allPicked（S AG->vertex））	//如果所有点都已标记
			break;
		for （int i = 0; i <= AG->vertex; i++） //对所有与j相连的节点
		{
			if （S[i] == 1）
				continue;
			if （path_length[i] > min_length + AG->length[i][j]）  //求min（Pi（i） Pi（j） + wij）
			{
				path_length[i] = min_length + AG->length[i][j];
				path[i] = j;
			}
		}
	}
	return 0;
}
////////////////////////////////////////////

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     294400  2013-01-09 10:49  图论算法大全\bin\GraphTest.exe

     文件    6073344  2013-01-09 10:49  图论算法大全\bin\GraphTest.pdb

     文件    3854326  2012-09-07 21:35  图论算法大全\bin\graph_movie.txt

     文件    3854326  2012-09-07 21:35  图论算法大全\graph_movie.txt

     文件        891  2012-12-03 23:03  图论算法大全\ShortCut.sln

    ..A..H.     43008  2013-01-16 20:40  图论算法大全\ShortCut.suo

     文件      17172  2013-01-16 20:29  图论算法大全\src\Algorithm.cpp

     文件       2377  2013-01-07 13:10  图论算法大全\src\Algorithm.h

     文件       4354  2012-12-17 00:08  图论算法大全\src\BetweenCen.cpp

     文件        653  2012-12-11 15:04  图论算法大全\src\BetweenCen.h

     文件        502  2012-12-07 23:50  图论算法大全\src\CDialog.cpp

     文件        354  2012-12-07 23:41  图论算法大全\src\CDialog.h

     文件       4323  2012-12-17 00:08  图论算法大全\src\CloseCen.cpp

     文件        770  2012-12-11 15:10  图论算法大全\src\CloseCen.h

     文件       2093  2013-01-07 20:25  图论算法大全\src\ConnectX.cpp

     文件        595  2013-01-07 20:20  图论算法大全\src\ConnectX.h

     文件       2116  2013-01-09 10:49  图论算法大全\src\ConnectY.cpp

     文件        595  2013-01-07 20:25  图论算法大全\src\ConnectY.h

     文件       2576  2013-01-07 20:10  图论算法大全\src\KruskalTree.cpp

     文件        627  2013-01-07 20:10  图论算法大全\src\KruskalTree.h

     文件       1741  2013-01-07 20:20  图论算法大全\src\PrimDialog.cpp

     文件        598  2013-01-06 18:42  图论算法大全\src\PrimDialog.h

     文件       3160  2012-12-03 23:03  图论算法大全\src\ReadMe.txt

     文件      67777  2009-08-31 02:31  图论算法大全\src\res\ShortCut.ico

     文件        672  2012-12-03 23:03  图论算法大全\src\res\ShortCut.rc2

     文件       4476  2013-01-07 13:30  图论算法大全\src\resource.h

     文件     110000  2013-01-07 20:25  图论算法大全\src\ShortCut.aps

     文件       2019  2012-12-03 23:03  图论算法大全\src\ShortCut.cpp

     文件        454  2012-12-03 23:03  图论算法大全\src\ShortCut.h

     文件      19954  2013-01-07 20:25  图论算法大全\src\ShortCut.rc

............此处省略15个文件信息