图基本概念
图的定义
图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)示意图G中顶点的无限非空集；E(G)示意图G中顶点之间的关系(边)的汇合。
留神：线性表能够是空表，树能够是空树，图不能够是空图，图能够没有边，然而至多要有一个顶点。
有向图
若E是有向边（简称弧）的无限汇合时，则G为有向图。弧是顶点的有序对，记为<v,w>，其中 v，w 是顶点，v 是弧尾，w 是弧头。称为从顶点v到顶点w的弧。
如上图所示G可示意为：
G=(V,E)
V={1,2,3}
E={<1,2>, <2,1>, <2,3>}
无向图
若E是无向边（简称边）的无限汇合时，则G为无向图。边是顶点的无序对，记为 (v,w) 或(w,v) ，且有 (v,w) =(w,v) 。其中 v，w 是顶点。
如上图所示，无向图G可示意为：
G=(V, E)V={1,2,3,4}
E={(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}
简略图
简略图满足以下两条内容：
1）不存在反复边
2）不存在顶点到本身的边
所以下面的有向图和无向图都是简略图。与简略图绝对的是多重图，即：两个结点间接边数多于一条，又容许顶点通过同一条边与本人关联。然而咱们在数据结构中仅探讨简略图，所以多重图不独自解说啦。
4.齐全图
无向图中任意两点之间都存在边，称为无向齐全图；如无向图中的示例就是齐全图。
有向图中任意两点之间都存在方向向反的两条弧，称为有向齐全图；如示例中的图就不是齐全图，但如果没有顶点3和指向顶点3 的边，就是一个齐全图。即下图是一个齐全图。
子图
若有两个图G=(V,E),G1=(V1,E2)，若V1是V的子集且E2是E的子集，称G1是G的子图。
如下面的有向齐全图是有向图的一个子图。
连通、连通图、连通重量
在无向图中，两顶点有门路存在，就称为连通的。若图中任意两顶点都连通，同此图为连通图。无向图中的极大连通子图称为连通重量。
以上面两个图为例，上面的图是下面的图的连通重量，并且上面的图是连通图。下面图中I与J也是连通的。
强连通图、强连通重量
在有向图中，两顶点两个方向都有门路，两顶点称为强连通。若任一顶点都是强连通的，称为强连通。有向图中极大强连通子图为有向图的强连通重量。
生成树和生成森林
连通图的生成树是蕴含图中全副顶点的一个极小连通子图，若图中有n个顶点，则生成树有n-1条边。所以对于生成树而言，若砍去一条边，就会变成非连通图。
在非连通图中，连通重量的生成树形成了非连通图的生成森林。
无向图的一个生成树
顶点的度、入度和出度
顶点的度为以该顶点为一个端点的边的数目。
对于无向图，顶点的边数为度，度数之和是顶点边数的两倍。
对于有向图，入度是以顶点为起点，出度相同。有向图的全副顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和。
留神：入度与出度是针对有向图来说的。
边的权和网
图中每条边上标有某种含意的数值，该数值称为该边的权值。这种图称为带树图，也称作网。
门路、门路长度和回路
两顶点之间的门路指顶点之间通过的顶点序列，通过门路上边的数目称为门路长度。若有n个顶点，且边数大于n-1，此图肯定有环。
简略门路、简略回路
顶点不反复呈现的门路称为简略门路。
除第一个顶点和最初一个顶点外，其余顶点不反复呈现的回路称为简略回路。
间隔
若两顶点存在门路，其中最短门路长度为间隔。
有向树
有一个顶点的入度为0，其余顶点的入度均为1的有向图称作有向树。如下图：
图的存储构造
邻接表
// queue.h#pragma once#include <iostream>const int queueSize = 100;template<class T>class queue{public: T data[queueSize]; int front, rear;};// graph.h#pragma once#include<iostream>#include"queue.h"// 定义边表结点struct ArcNode{ int adjvex;// 邻接点域 ArcNode* next;};// 定义顶点表结点struct VertexNode{ int vertex; ArcNode* firstedge;}; // 基于邻接表存储构造的图的类实现const int MaxSize = 10;int visited[MaxSize] = { 0 };// 顶点是否被拜访的标记//typedef VertexNode AdjList[MaxSize]; //邻接表 template<class T>class ALGraph{public: ALGraph(T a[], int n, int e);// 构造函数建设具备N个定点e条边的图 ~ALGraph() {}// 析构函数 void DFSTraaverse(int v);// 深度优先遍历图 void BFSTraverse(int v);// 广度优先遍历图private: VertexNode adjlist[MaxSize];// 寄存顶点的数组 int vertexNum, arcNum;// 图中顶点数和边数}; template<class T>ALGraph<T>::ALGraph(T a[], int n, int e){ vertexNum = n; arcNum = e; for (int i = 0; i <vertexNum; i++) { adjlist[i].vertex = a[i]; adjlist[i].firstedge = NULL; } for (int k = 0; k < arcNum; k++) { int i, j; std::cin >> i >> j; ArcNode* s = new ArcNode; s->adjvex = j; s->next = adjlist[i].firstedge; adjlist[i].firstedge = s; }} template<class T>inline void ALGraph<T>::DFSTraaverse(int v){ std::cout << adjlist[v].vertex; visited[v] = 1; ArcNode* p = adjlist[v].firstedge; while (p != NULL) { int j = p->adjvex; if (visited[j] == 0) DFSTraaverse(j); p = p->next; }} template<class T>inline void ALGraph<T>::BFSTraverse(int v){ int visited[MaxSize] = { 0 };// 顶点是否被拜访的标记 queue<T> Q; Q.front = Q.rear = -1; // 初始化队列 std::cout << adjlist[v].vertex; visited[v] = 1; Q.data[++Q.rear] = v;// 被拜访顶点入队 while (Q.front != Q.rear) { v = Q.data[++Q.front]; // 对头元素出队 ArcNode* p = adjlist[v].firstedge; while (p != NULL) { int j = p->adjvex; if (visited[j] == 0) { std::cout << adjlist[j].vertex; visited[j] = 1; Q.data[++Q.rear] = j; } p = p->next; } }}// main.cpp#include"graph.h"using namespace std;int main(){ int arry[] = { 1,2,3,4,5 }; ALGraph<int> graph(arry, 5, 7); graph.BFSTraverse(3); cout << endl; graph.DFSTraaverse(3); system("pause"); return 0;}邻接矩阵
#include <stdio.h>#include <stdlib.h>#define maxv 10#define max 10typedef char elem;typedef int elemtype;#include "queue.h"#include "mgraph.h"void main(){ mgraph g; printf("1.初始化函数测试:\n"); initial(g); printf("2.创立函数测试:\n"); create(g); printf("3.输入函数测试:\n"); printg(g); printf("4.输入顶点度函数测试:\n"); degree(g); printf("5.深度优先遍历函数测试:\n"); dfstraverse(g); printf("6.广度优先遍历函数测试:\n"); bfs(g);}//有向图的邻接矩阵,顶点数据为字符型typedef struct MGraph{ elem vexes[maxv];//顶点表 int edges[maxv][maxv];//邻接矩阵 int n,e;//顶点数n和边数e}mgraph;bool visited[maxv];//拜访标记数组void initial(mgraph &g)//初始化函数{ int i,j; g.e=0; g.n=0; for(j=0;j<maxv;j++) g.vexes[j]=0;//建设顶点表 for(i=0;i<maxv;i++) { for(j=0;j<maxv;j++) { g.edges[i][j]=0;//初始化邻接矩阵 } }}int locate(mgraph g,elem u)//查找顶点对应的数组下标值{ for(int i=0;i<g.n;i++) { if(g.vexes[i]==u) return i; } return -1;}void create(mgraph &g)//创立图的邻接矩阵存储{ int i,j,k; elem u,v; printf("请输出有向图的顶点数:"); scanf("%d",&g.n); printf("请输出有向图的弧数:"); scanf("%d",&g.e); fflush(stdin);//清空缓存中的数据 printf("请输出字符型顶点数据,如ABCD:"); for(j=0;j<g.n;j++) scanf("%c",&g.vexes[j]);//建设顶点表 fflush(stdin); printf("请输出弧的信息,格局:弧尾,弧头\n"); for(k=0;k<g.e;k++) { scanf("%c,%c",&u,&v); i=locate(g,u); j=locate(g,v); g.edges[i][j]=1; fflush(stdin); }}void printg(mgraph g)//输入有向图的邻接矩阵{ int i,j; printf("输出图的邻接矩阵存储信息:\n"); printf("顶点数据:\n"); for(i=0;i<g.n;i++) printf("%d:%c\n",i,g.vexes[i]); printf("邻接矩阵数据:\n"); for(i=0;i<g.n;i++) { for(j=0;j<g.n;j++) { printf("%3d",g.edges[i][j]); } printf("\n"); }}void degree(mgraph g)//输入顶点的度{ int i,j,in,out; for(i=0;i<g.n;i++) { in=0; out=0; for(j=0;j<g.n;j++) { if(g.edges[i][j]!=0) out++; if(g.edges[j][i]!=0) in++; } printf("顶点%c的出度为%d---入度为%d---度为%d\n",g.vexes[i],out,in,in+out); }}int firstadjvex(mgraph g,int v)//顶点v的第一个邻接顶点{ for(int i=0;i<g.n;i++) { if(g.edges[v][i]==1) return i; } return -1;}int nextadjvex(mgraph g,int v,int w)//顶点v的绝对于w的下一个邻接顶点{ for(int i=w+1;i<g.n;i++) { if(g.edges[v][i]==1) return i; } return -1;}void dfs(mgraph g,int v)//遍历一个连通重量{ int w; visited[v]=true; printf("%c ",g.vexes[v]); for(w=firstadjvex(g,v);w>=0;w=nextadjvex(g,v,w)) { if(!visited[w]) dfs(g,w); }}void dfstraverse(mgraph g)//深度优先遍历{ int v; for(v=0;v<g.n;v++) visited[v]=false;//标记拜访数组初始化 for(v=0;v<g.n;v++) { if(!visited[v]) dfs(g,v); }}void bfs(mgraph g)//广度优先遍历{ int u=0,v=0,w=0; queue q; for(v=0;v<g.n;v++) visited[v]=false; initqueue(q); for(v=0;v<g.n;v++) { if(!visited[v]) { visited[v]=true; printf("%c ",g.vexes[v]); enqueue(q,v); while(!queueempty(q)) { dequeue(q,u); for(w=firstadjvex(g,u);w>=0;w=nextadjvex(g,u,w)) { if(!visited[w]) { visited[w]=true; printf("%c ",g.vexes[w]); enqueue(q,w); } } } } } destroyqueue(q);}typedef struct{ elemtype *base;//动态分配存储空间 int front;//头指针,若队列不空指向队列头元素 int rear;//尾指针,若队列不空指向队列尾元素的下一个地位}queue;void initqueue(queue &q)//初始化队列{ q.base=new elemtype[max];//调配存储空间 if(!q.base) { printf("队列调配失败\n"); exit(-2); } else q.front=q.rear=0;}int queueempty(queue q)//判断队列是否为空{ if(q.front==q.rear) return 1; else return 0;}void enqueue(queue &q,elemtype e)//入队列操作{ if((q.rear+1)%max==q.front) { printf("队满,无奈插入新元素!\n"); exit(-2); } else { q.base[q.rear]=e; q.rear=(q.rear+1)%max; }}void dequeue(queue &q,elemtype e)//出队列操作{ if(q.front==q.rear)//判断队列是否为空 { printf("空队列,无奈删除头元素!\n"); exit(-2); } else { e=q.base[q.front]; q.front=(q.front+1)%max; }}void destroyqueue(queue &q)//销毁队列{ free(q.base); q.base=NULL; q.front=0; q.rear=0; printf("\n");}十字链表
/************************************************************************************ 十字链表构造：次要针对的是有向图进行的存储优化对于有向图来说，邻接表是有缺点的。关怀了出度问题，想理解入度就必须要遍历整个图能力晓得，反之，逆邻接表解决了入度却不了角出度的状况。有没有可能把邻接表与逆邻接表联合起来呢？答案是必定的，就是把它们整合在一起。所以呈现了十字链表构造。顶点构造：[data | firstin | firstout ]其中firstin示意入边表头指针，指向该顶点的入边表中的第一个结点firstout示意出边表头指针，指向该顶点的出边表中的第一个结点。弧构造：[tailvex | headvex | headlink | taillink]其中tailevex是指弧终点在顶点表中的下标，headvex相似。headlink是指入边表指针域，指向起点雷同的下一条边，taillink相似。如果是网，可再减少一个权值域。**********************************************************************************/#include <iostream>#include <string>#include <queue>using namespace std; #define MAXVEXSIZE 10#define SUCCESS 1#define UNSUCCESS 0typedef int Status;int visited[MAXVEXSIZE]; //批示顶点是否被拜访 typedef string VertexType; //顶点类型typedef struct ArcType { int tailvex; //弧头下标 int headvex; //弧尾下标 int weight; //权值 ArcType* headlink; //指向下一个同一弧头的弧 ArcType* taillink; //指向下一个同一弧尾的弧}ArcType;typedef struct { VertexType data; ArcType* firstin; //指向第一条入弧 ArcType* firstout; //指向第一条出弧 }VertexNode;typedef VertexNode CrossList[MAXVEXSIZE]; typedef struct { CrossList crossList; //十字链表 int iVexNum; int iArcNum; }CrossGraph; //由顶点值得到顶点索引int GetIndexByVertexVal( const CrossGraph& G, VertexType val ){ for ( int i = 0; i < G.iVexNum; ++i ) { if ( val == G.crossList[i].data ) return i; } return -1;} //创立有向图Status CreateCrossGraph( CrossGraph& G ){ cout << "输出顶点个数以及边数："; cin >> G.iVexNum >> G.iArcNum; cout << "请输出" << G.iVexNum << "个顶点:"; for ( int i = 0; i < G.iVexNum; ++i ) { cin >> G.crossList[i].data; G.crossList[i].firstin = NULL; G.crossList[i].firstout = NULL; } cout << "请输出由两点形成的边(" << G.iArcNum << "条):"; for ( int i = 0; i < G.iArcNum; ++i ) { VertexType first; VertexType second; cin >> first >> second; int m = GetIndexByVertexVal( G, first ); int n = GetIndexByVertexVal( G, second ); if ( m == -1 || n == -1 ) return UNSUCCESS; ArcType* pArc = new ArcType; memset( pArc, 0, sizeof(ArcType) ); pArc->headvex = m; pArc->tailvex = n; pArc->weight = 0; //权值临时不必 pArc->taillink = G.crossList[m].firstout;//表头插入法 G.crossList[m].firstout = pArc; pArc->headlink = G.crossList[n].firstin;//表头插入法 G.crossList[n].firstin = pArc; } return SUCCESS;} //求顶点的度，在十字链表中还是挺不便的，因为其是邻接表与逆邻接表的结合体int GetVertexDegree( const CrossGraph& G, VertexType val ){ int m = GetIndexByVertexVal( G, val ); //失去顶点的在顶点表中的索引 if ( -1 == m ) return -1; int TD = 0; //先求出度 ArcType* pArcOut = G.crossList[m].firstout; while ( pArcOut ) { ++TD; pArcOut = pArcOut->taillink; } //再累退出度 ArcType* pArcIn = G.crossList[m].firstin; while( pArcIn ) { ++TD; pArcIn = pArcIn->headlink; } return TD;} //深度优先遍历void DFS( const CrossGraph& G, int i ){ cout << G.crossList[i].data << " "; visited[i] = true; ArcType* pArc = G.crossList[i].firstout; while( pArc ) { int iVex = pArc->tailvex; if ( !visited[iVex] ) { DFS( G, iVex ); } pArc = pArc->taillink; }}void DFSTraverse( const CrossGraph& G ){ for ( int i = 0; i < G.iVexNum; ++i ) { visited[i] = false; } for ( int i = 0; i < G.iVexNum; ++i ) { if ( !visited[i] ) { DFS( G, i ); } }} //广度优先遍历void BFSTraverse( const CrossGraph& G ){ for ( int i = 0; i < G.iVexNum; ++i ) { visited[i] = false; } queue<int> Q; for ( int i = 0; i < G.iVexNum; ++i ) { if ( !visited[i] ) { cout << G.crossList[i].data << " "; visited[i] = true; Q.push( i ); while ( !Q.empty() ) { int iVex = Q.front(); Q.pop(); ArcType* pArc = G.crossList[iVex].firstout; while ( pArc ) { int j = pArc->tailvex; if ( !visited[j] ) { cout << G.crossList[j].data << " "; visited[j] = true; Q.push(j); } pArc = pArc->taillink; } } } }} //销毁图void DestroyGraph( CrossGraph& G ){ for ( int i = 0; i < G.iVexNum; ++i ) { ArcType* pArc = G.crossList[i].firstout; while( pArc ) { ArcType* q = pArc; pArc = pArc->taillink; delete q; } G.crossList[i].firstout = NULL; G.crossList[i].firstin = NULL; } G.iVexNum = 0; G.iArcNum = 0;} int main(){ //创立有向图 CrossGraph G; CreateCrossGraph( G ); //深度优先遍历图 cout << "深度优先遍历:" << endl; DFSTraverse( G ); cout << endl << endl; //广度优先遍历图 cout << "广度优先遍历:" << endl; BFSTraverse( G ); cout << endl << endl; //结点的度 cout << "输出求度的结点:"; VertexType v; cin >> v; cout << "度为：" << GetVertexDegree( G, v ) << endl; //销毁有向图 DestroyGraph( G ); return 0;}邻接多重表
/*********************************************************************************************** 邻接多重表构造：次要针对的是无向图进行的存储优化如果咱们在无向图的利用中，关注的重点是顶点，那么邻接表是不错的抉择，但如果咱们更关注边的操作，比方对已拜访过的边做标记，删除某一条边等操作，那就意味着，须要找到这条边的两个边表结点进行操作，这其实还是比拟麻烦的。因而，咱们也按照十字链表的形式，对表结点进行一下革新： [ ivex | ilink | jvex | jlink]其中ivex和jvex是与某条边附丽的两个顶点在顶点表中下标。ilink指向附丽点ivex的下一条边,jlink指向附丽点jvex的下一条边，这就是邻接多重表构造。*************************************************************************************************/#include <iostream>#include <string>#include <queue>using namespace std; #define MAXVEXSIZE 10#define SUCCESS 1#define UNSUCCESS 0typedef int Status;int visited[MAXVEXSIZE]; //批示顶点是否被拜访 typedef string VertexType; //顶点类型typedef struct ArcType { int ivex; //该弧附丽的两点的地位 int jvex; // int weight; //权值 ArcType* ilink; //别离指向附丽该弧的下一条弧 ArcType* jlink; }ArcType;typedef struct { VertexType data; ArcType* firstArc; //指向第一条弧 }VertexNode;typedef VertexNode MulAdjList[MAXVEXSIZE]; typedef struct { MulAdjList mulAdjList; //多重邻接表 int iVexNum; int iArcNum; }MulAdjGraph; //由顶点值得到顶点索引int GetIndexByVertexVal( const MulAdjGraph& G, VertexType val ){ for ( int i = 0; i < G.iVexNum; ++i ) { if ( val == G.mulAdjList[i].data ) return i; } return -1;} //创立无向图Status CreateCrossGraph( MulAdjGraph& G ){ cout << "输出顶点个数以及边数："; cin >> G.iVexNum >> G.iArcNum; cout << "请输出" << G.iVexNum << "个顶点:"; for ( int i = 0; i < G.iVexNum; ++i ) { cin >> G.mulAdjList[i].data; G.mulAdjList[i].firstArc = NULL; } cout << "请输出由两点形成的边(" << G.iArcNum << "条):"; for ( int i = 0; i < G.iArcNum; ++i ) { VertexType first; VertexType second; cin >> first >> second; int m = GetIndexByVertexVal( G, first ); int n = GetIndexByVertexVal( G, second ); if ( m == -1 || n == -1 ) return UNSUCCESS; ArcType* pArc = new ArcType; memset( pArc, 0, sizeof(ArcType) ); pArc->ivex = m; pArc->jvex = n; pArc->weight = 0; //权值临时不必 pArc->ilink = G.mulAdjList[m].firstArc;//表头插入法 G.mulAdjList[m].firstArc = pArc; pArc->jlink = G.mulAdjList[n].firstArc;//表头插入法 G.mulAdjList[n].firstArc = pArc; } return SUCCESS;} //求顶点的度int GetVertexDegree( const MulAdjGraph& G, VertexType val ){ int m = GetIndexByVertexVal( G, val ); //失去顶点的在顶点表中的索引 if ( -1 == m ) return -1; int TD = 0; ArcType* pArc = G.mulAdjList[m].firstArc; while ( pArc ) { ++TD; if ( m == pArc->ivex ) pArc = pArc->ilink; else pArc = pArc->jlink; } return TD;} //深度优先遍历void DFS( const MulAdjGraph& G, int i ){ cout << G.mulAdjList[i].data << " "; visited[i] = true; ArcType* pArc = G.mulAdjList[i].firstArc; while( pArc ) { int iVex = pArc->jvex; if ( !visited[iVex] ) { DFS( G, iVex ); } pArc = pArc->ilink; }}void DFSTraverse( const MulAdjGraph& G ){ for ( int i = 0; i < G.iVexNum; ++i ) { visited[i] = false; } for ( int i = 0; i < G.iVexNum; ++i ) { if ( !visited[i] ) { DFS( G, i ); } }} //广度优先遍历void BFSTraverse( const MulAdjGraph& G ){ for ( int i = 0; i < G.iVexNum; ++i ) { visited[i] = false; } queue<int> Q; for ( int i = 0; i < G.iVexNum; ++i ) { if ( !visited[i] ) { cout << G.mulAdjList[i].data << " "; visited[i] = true; Q.push( i ); while ( !Q.empty() ) { int iVex = Q.front(); Q.pop(); ArcType* pArc = G.mulAdjList[iVex].firstArc; while ( pArc ) { int j = pArc->jvex; if ( !visited[j] ) { cout << G.mulAdjList[j].data << " "; visited[j] = true; Q.push( j ); } pArc = pArc->ilink; } } } }} //销毁图void DestroyGraph( MulAdjGraph& G ){ for ( int i = 0; i < G.iVexNum; ++i ) { ArcType* pArc = G.mulAdjList[i].firstArc; while( pArc ) { ArcType* q = pArc; pArc = pArc->ilink; int m = q->ivex; //在m号顶点下找以后边的前一条边 ArcType* pmArc = G.mulAdjList[m].firstArc; ArcType* pmPreArc = NULL; while ( pmArc != q ) { pmPreArc = pmArc; if ( m == pmArc->ivex ) { pmArc = pmArc->ilink; } else { pmArc = pmArc->jlink; } } if ( !pmPreArc ) { G.mulAdjList[m].firstArc = q->ilink; } else { if ( m == pmPreArc->ivex ) { pmPreArc->ilink = q->ilink; } else { pmPreArc->jlink = q->ilink; } } int n = q->jvex; //在n号顶点下找以后边的前一条边 ArcType* pnArc = G.mulAdjList[n].firstArc; ArcType* pnPreArc = NULL; while ( pnArc != q ) { pnPreArc = pnArc; if ( n == pnArc->ivex ) { pnArc = pnArc->ilink; } else { pnArc = pnArc->jlink; } } if ( !pnPreArc ) { G.mulAdjList[n].firstArc = q->jlink; } else { if ( n == pnPreArc->ivex ) { pnPreArc->ilink = q->jlink; } else { pnPreArc->jlink = q->jlink; } } delete q; } } G.iVexNum = 0; G.iArcNum = 0;} int main(){ //创立有向图 MulAdjGraph G; CreateCrossGraph( G ); //深度优先遍历图 cout << "深度优先遍历:" << endl; DFSTraverse( G ); cout << endl << endl; //广度优先遍历图 cout << "广度优先遍历:" << endl; BFSTraverse( G ); cout << endl << endl; //结点的度 cout << "输出求度的结点:"; VertexType v; cin >> v; cout << "度为：" << GetVertexDegree( G, v ) << endl; cout << "再输出求度的结点:"; cin >> v; cout << "度为：" << GetVertexDegree( G, v ) << endl; cout << "再输出求度的结点:"; cin >> v; cout << "度为：" << GetVertexDegree( G, v ) << endl; //销毁有向图 DestroyGraph( G ); return 0;}边集数组
概念
边集数组是由两个一维数组形成。一个是存储顶点的信息；另一个是存储边的信息。这个边数组每个数据元素由一条边的终点下标（begin）、起点下标（end）和权（weight）组成。
typedef struct VertexNode4 /*顶点表结点*/{ VerterType data;/*数据域*/}vexs4[MAX];性质
边集数组关注的是边的汇合，在边集数组中要查找一个顶点的度须要扫描整个边数组，效率并不高。
因而它更适宜对边顺次进行解决的操作，而不适宜对顶点相干的操作。
C实现
//以下是图的边集数组表示法typedef struct VertexNode4 /*顶点表结点*/{ VerterType data;/*数据域*/}vexs4[MAX];/*边数组构造*/typedef struct edges4{ int begin;/*存储终点的下标*/ int end;/*存储起点的下标*/ int weight;/*权值*/}Edges4[MAX];/*图的边集数组存储构造*/typedef struct graph4{ Edges4 edg4; /*边表结点构造*/ vexs4 Node4; /*顶点表结点构造*/ int numVertexes; /*图中以后的顶点数*/ int numEdges; /*图中以后的边数*/}graph4;extern void CreateGraph4(graph4* g);void CreateGraph4(graph4* g){ int i=0, j=0, k=0, w=0; printf("请输出顶点数和边数：\n"); scanf_s("%d,%d", &g->numVertexes, &g->numEdges,4); //输出顶点数和边数 getchar(); //能够获取回车符 printf("请输出顶点信息：\n"); //获取顶点数组信息 for (i = 0; i < g->numVertexes; i++) { scanf_s("%c", &g->Node4[i].data,5); //输出顶点信息 } getchar(); //能够获取回车符 //获取边数组 for (k = 0; k < g->numEdges; k++) { printf("输出边<vi,vj>上的下标i,下标j和w的值：\n"); scanf_s("%d,%d,%d", &i, &j, &w,4); getchar(); g->edg4[k].begin = i; //输出边的终点 g->edg4[k].end = j; //输出边的起点 g->edg4[k].weight = w; //两条边的权值 }}int main(void){ graph4 gra; CreateGraph4(&gra); system("pause"); return 0;}图的遍历
深度优先（DFS）
应用栈进行回退。
//深度优先遍历int visitedDFS[MAXV] = { 0 }; //全局数组，记录是否遍历void DFS(ListGraph* LG, int v) { EdgeNode* p; visitedDFS[v] = 1; //记录已拜访，置 1 printf("%2d", v); //输入顶点编号 p = LG->adjList[v].firstEdge; //p 指向顶点 v 的第一个邻接点 while (p != NULL) { if (visitedDFS[p->adjVer] == 0 && p->weight != INF) { //如果 p->adjVer 没被拜访，递归拜访它 DFS(LG, p->adjVer); } p = p->nextEdge; //p 指向顶点 v 的下一个邻接点 }}广度优先（BFS）
应用辅助队列
//广度优先遍历//以邻接表储构造，在使用广度优先遍历时须要引入一个队列SeQuence，用来存储和输入遍历数据，visiteBFS[]记录拜访状态（v 是初始点）。void BFS(ListGraph* LG, int v) { int ver; //定义出队顶点 EdgeNode* p; SqQueue* sq; //定义指针 initQueue(sq); //初始化队列 int visitedBFS[MAXV] = { 0 }; //初始化拜访标记数组 enQueue(sq, v); //初始点进队 printf("%2d", v); visitedBFS[v] = 1; //打印并标记要出队顶点 while (!emptyQueue(sq)) { //队为空完结循环 ver = deQueue(sq, v); //出队，并失去出队信息 p = LG->adjList[ver].firstEdge; //指向出队的第一个邻接点 while (p != NULL) { //查找 ver 的所有邻接点 if (visitedBFS[p->adjVer] == 0 && p->weight != INF) { //如果没被拜访 printf("%2d", p->adjVer); //打印该顶点信息 visitedBFS[p->adjVer] = 1; //置已拜访状态 enQueue(sq, p->adjVer); //该顶点进队 } p = p->nextEdge; //找下一个邻接点 } } printf("\n");}整体设计
#include<stdio.h>#include<malloc.h>#define MAXV 7 //最大顶点个数#define INF 32767 //定义 ∞ //∞ == INF ,int 型的最大范畴（2位）= 2^(2*8-1)，TC通知咱们int占用2个字节，而VC和LGCC通知咱们int占用4个字节//图：Graph//顶点：Vertex//邻接：Adjacency//矩阵：Matrix//表：List//边：Edge //深度优先遍历：Depth First Search （DFS） //广度优先比例：Breadth First Search （BFS） typedef struct eNode { int adjVer; //该边的邻接点编号 int weight; //该边的的信息，如权值 struct eNode* nextEdge; //指向下一条边的指针 }EdgeNode; //别名，边结点的类型 typedef struct vNode { EdgeNode* firstEdge; //指向第一个边结点 }VNode; //别名，邻接表的头结点类型 typedef struct list { int n; //顶点个数 int e; //边数 VNode adjList[MAXV]; //邻接表的头结点数组 }ListGraph; //别名，残缺的图邻接表类型 typedef struct quene { //定义程序队 int front; //队头指针 char data[MAXV]; //寄存队中元素 int rear; //队尾指针 }SqQueue; //struct Queue 的别名//初始化队列 void initQueue(SqQueue*& q) { q = (SqQueue*)malloc(sizeof(SqQueue)); //调配一个空间 q->front = q->rear = -1; //置 -1 }//判断队列是否为空bool emptyQueue(SqQueue*& q) { if (q->front == q->rear) { //首指针和尾指针相等，阐明为空 return true; //返回真 } else { return false; //返回假 }}//进队列int enQueue(SqQueue*& q, char c) { if (q->rear == MAXV - 1) { //判断队列是否满了 return -1; //返回 -1 } q->rear++; //头指针加 1 q->data[q->rear] = c; //传值 return c; //返回 c}//出队列 int deQueue(SqQueue*& q, char ch) { if (q->front == q->rear) { //判断是否空了 return -1; //返回假 -1 } q->front++; //尾指针加 1 ch = q->data[q->front]; //取值 return ch; //返回 ch}//创立图的邻接表 void createAdjListGraph(ListGraph* &LG, int A[MAXV][MAXV], int n, int e) { int i, j; EdgeNode* p; LG = (ListGraph*)malloc(sizeof(ListGraph)); for (i = 0; i < n; i++) { LG->adjList[i].firstEdge = NULL; //给邻接表中所有头结点指针域置初值 } for (i = 0; i < n; i++) { //查看邻接矩阵中的每个元素 for (j = n - 1; j >= 0; j--) { if (A[i][j] != 0) { //存在一条边 p = (EdgeNode*)malloc(sizeof(EdgeNode)); //申请一个结点内存 p->adjVer = j; //寄存邻接点 p->weight = A[i][j]; //寄存权值 p->nextEdge = NULL; p->nextEdge = LG->adjList[i].firstEdge; //头插法 LG->adjList[i].firstEdge = p; } } } LG->n = n; LG->e = e;}//输入邻接表 void displayAdjList(ListGraph* LG) { int i; EdgeNode* p; for (i = 0; i < MAXV; i++) { p = LG->adjList[i].firstEdge; printf("%d:", i); while (p != NULL) { if (p->weight != INF) { printf("%2d[%d]->", p->adjVer, p->weight); } p = p->nextEdge; } printf(" NULL\n"); }}//深度优先遍历int visitedDFS[MAXV] = { 0 }; //全局数组，记录是否遍历void DFS(ListGraph* LG, int v) { EdgeNode* p; visitedDFS[v] = 1; //记录已拜访，置 1 printf("%2d", v); //输入顶点编号 p = LG->adjList[v].firstEdge; //p 指向顶点 v 的第一个邻接点 while (p != NULL) { if (visitedDFS[p->adjVer] == 0 && p->weight != INF) { //如果 p->adjVer 没被拜访，递归拜访它 DFS(LG, p->adjVer); } p = p->nextEdge; //p 指向顶点 v 的下一个邻接点 }}//广度优先遍历void BFS(ListGraph* LG, int v) { int ver; //定义出队顶点 EdgeNode* p; SqQueue* sq; //定义指针 initQueue(sq); //初始化队列 int visitedBFS[MAXV] = { 0 }; //初始化拜访标记数组 enQueue(sq, v); //初始点进队 printf("%2d", v); visitedBFS[v] = 1; //打印并标记要出队顶点 while (!emptyQueue(sq)) { //队为空完结循环 ver = deQueue(sq, v); //出队，并失去出队信息 p = LG->adjList[ver].firstEdge; //指向出队的第一个邻接点 while (p != NULL) { //查找 ver 的所有邻接点 if (visitedBFS[p->adjVer] == 0 && p->weight != INF) { //如果没被拜访 printf("%2d", p->adjVer); //打印该顶点信息 visitedBFS[p->adjVer] = 1; //置已拜访状态 enQueue(sq, p->adjVer); //该顶点进队 } p = p->nextEdge; //找下一个邻接点 } } printf("\n");}int main() { ListGraph* LG; int array[MAXV][MAXV] = { { 0, 4, 6, 6,INF,INF,INF}, {INF, 0, 1,INF, 7,INF,INF}, {INF,INF, 0,INF, 6, 4,INF}, {INF,INF, 2, 0,INF, 5,INF}, {INF,INF,INF,INF, 0,INF, 6}, {INF,INF,INF,INF, 1, 0, 8}, {INF,INF,INF,INF,INF,INF, 0} }; int e = 12; createAdjListGraph(LG, array, MAXV, e); printf("邻接表为：\n"); displayAdjList(LG); printf("\n"); printf("深度优先遍历为："); DFS(LG,0); printf("\n"); printf("广度优先遍历为："); BFS(LG, 0); printf("\n"); return 0;}图的进一步了解
最小生成树
Prim算法
最小代价生成树的3条结构准则：
1）.只能应用网络中的边来结构最小生成树；
2）.能且只能应用 n-1 条边来连贯网络中的 n 个顶点；
3）.选用的 n-1 条边不能产生回路。
Prim算法简介
根本思维：给定任意一带权连通网络 N={V,E}，T={U,TE}是N的最小生成树（生成树也是图）。
1.算法始终将顶点汇合V分成没有元素重叠的两局部，U 和 V-U；
2.生成树T的初始状态为 U={u。}（即U只蕴含V中的一个初始顶点），TE为空集；
3.反复执行以下操作：在所有汇合U 和汇合V-U 的边中找出一条代价最小的边（u。, v。）并入汇合TE，同时 v。并入U，直至汇合U中蕴含了V中全副顶点为止。此时TE中必有n-1条边，则T就是N的最小生成树。
4.引入辅助数组 closeEdge，记录 从 U 到 V-U 具备最小代价的边。
（提醒：下面这句话的意思是，汇合U中顶点只能做边的边尾，汇合V-U中的顶点只能做边头，限定了方向； 这样就能保障不会造成回路，（这一点以 lowcost = 0 来实现） 1.新入汇合U中的顶点 不会指向汇合U中的原有顶点； 2.汇合V-U中的顶点 不会指向汇合U中的顶点。）
4.1.汇合V-U中的每个顶点，在closeEdge数组中都对应一个下标，即 vi -> closeEdge[i-1]，它蕴含两个域 adjvex、lowcost；
4.2.adjvex存储汇合U中顶点（下标索引）；
4.3.lowcost存储从 adjvex 到 i 的边的权值；
4.4.当closeEdge对应下标 k 地位的lowcost=0时，代表 k 顶点已从汇合V-U转入到汇合U；
5.Prim算法工夫复杂度为：O(n^2)，即与顶点数无关，与边无关，故实用于边浓密的网的最小生成树的求解。
注：代码中应用的头文件"GraphAdjMat.h"参看之前博文“数据结构之图（邻接矩阵实现）”；头文件"ObjArrayList.h"参看之前博文“数据结构之程序列表（反对对象元素）”。
图解
Code
//文件名："MST_PRIM.cpp"#include "stdafx.h"#include <string>#include "GraphAdjMat.h"using namespace std; struct CloseEdge{ int adjVex; //汇合U 顶点索引 （边尾） int lowCost; //边代价（权重）}; GraphAdjMat * GraphAdjMat::MiniSpanTree_Prim(string * vertex){ /* . 最小（代价）生成树：( Minimum Cost Spanning Tree ) . 入参： . string * vertex: 起始顶点 . 出参： . GraphAdjList *: 生成树的图对象 . 算法实现：（ prim 算法 ） . 工夫复杂度：O(n^2) */ //判断是否为无向网 if (this->type != UDN) return NULL; //初始化最小生成树 图 GraphAdjMat * mst = new GraphAdjMat(GraphAdjMat::UDN); mst->Init(new ObjArrayList<string>(), new ObjArrayList<ArcData>()); //辅助数组 closeEdge， 初始化为最大顶点个数 // 用于寄存 汇合U -> 汇合V-U 中的各条代价边 CloseEdge closeEdge[this->_MAX_VERTEX_NUM]; //定位起始顶点地位 int index = _Locate(*vertex); //最小生成树中 插入第一个顶点 mst->InsertVertex(vertex); //1.1.将 index 地位顶点（第一个顶点） 退出到 汇合U，用 0 标记 closeEdge[index].lowCost = 0; //1.2.向closeEdge 中退出第一个顶点的所有边信息 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { if (index != i) { //初始化 各顶点与起始顶点的附丽关系 到 closeEdge //注：1.思考到顶点删除操作后的不间断存储，故遍历整个动态数组；2.蕴含 无顶点信息的 无穷地位 closeEdge[i].adjVex = index; closeEdge[i].lowCost = this->arcs[index][i].adj; } } //2.循环 n-1 次（即 顶点数 - 1）寻找 n-1 条最小代价边，依据 MST 性质 for (int n = 0; n < this->vexNum - 1; n++) { //输入 closeEdge 数组 cout << endl << "数组：" << endl; for (int i = 0; i < _MAX_VERTEX_NUM; i++) { cout << "(" << closeEdge[i].adjVex << "->" << i << ":" << closeEdge[i].lowCost << ") "; } cout << endl; //2.1.寻找 汇合U -> 汇合V-U 中的最小代价边 int k = 0; //最小代价边 对应的顶点地位 for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { /* . 过滤掉 lowCost == 0 的地位，即只在 代表 汇合V-U 的下标索引 中找 . ** 解析： . 1.从 汇合U 到 汇合V-U 的边中，汇合U 中顶点都充当了 边尾（Tail），汇合V-U 中顶点都充当了 边头（Head） . 2.在 closeedge 数组中，其下标索引代表 汇合V-U ，即为 边头； . 3.在 closeedge 数组中，其某个地位中 lowcost = 0 代表 该地位下标索引 已入 汇合U，即成为 边尾； . 4.在 closeedge 数组中，adjVex 代表 汇合U 中的顶点 ，即为 边尾； . 注：在这样规定了 汇合U 中顶点只能做 边尾 的前提下， . 无效的防止了 新入 汇合U 的顶点 去指向 汇合U 中的原有顶点 */ if (closeEdge[k].lowCost == 0) { k++; continue; //直到找到第一个 汇合V-U 中下标索引 } if (closeEdge[i].lowCost < closeEdge[k].lowCost && closeEdge[i].lowCost > 0) { k = i; } } //2.2.向最小生成树（图）中插入此顶点、最小代价边，并输入边信息 mst->InsertVertex(new string(this->vexs[k])); mst->InsertArc(new ArcData{ this->vexs[closeEdge[k].adjVex], this->vexs[k], closeEdge[k].lowCost }); cout << "k:" << k << " arc: " << this->vexs[closeEdge[k].adjVex] << " -> " << this->vexs[k] << " : " << closeEdge[k].lowCost << endl; //2.3.将 k地位顶点 退出到 汇合U，用 0 标记 closeEdge[k].lowCost = 0; //2.4.将其所有代价最小边退出到 closeEdge for (int i = 0; i < this->_MAX_VERTEX_NUM; i++) { /* . 这一判断其实蕴含了两层含意 . ** 解析： . 1.有个前提：所有边的权重都大于 0，这样 lowcost = 0 的地位（已入 汇合U ， . 其不能再做 边头，即排除了属于 汇合U 外部的 'k -> i' 的这条边 . 2.对于 汇合U 指向 汇合V-U 的边中，存在这样的边：'k1 -> i' 和 'k2 -> i'，只保留权值小的那条边 */ if (this->arcs[k][i].adj < closeEdge[i].lowCost) { closeEdge[i].adjVex = k; closeEdge[i].lowCost = this->arcs[k][i].adj; } } } //3.返回 mst return mst; }Kruskal算法
简介
1，该算法用到了排序算法，要求辅助数组按权值大小排序，代码中应用间接插入排序算法。
2，另外还需设置一个连通重量辅助数组，用来标识两个顶点是否在同一连通重量，因为咱们要抉择的是最小权值的边且边连贯的两个顶点在不同连通重量的边。该算法也称“加边法”，所以克鲁斯卡尔算法更适宜于求稠密网的最小生成树。
Code
#include<stdio.h>#define MaxInt 9 //定义无穷大，这里设置一个比所有边的权值都大的数9#define MVNum 100typedef char VerTexType; //顶点类型typedef int ArcType; //边权值类型//邻接矩阵的存储构造typedef struct{ VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的以后点数和边数}AMGraph;//最小生成树克鲁斯卡尔算法定义//辅助数组边表typedef struct{ VerTexType Head; //边的始点 VerTexType Tail; //变的起点 ArcType lowcost; //边上的权值}Edge[MVNum];Edge E; //创立一个全局边辅助数组int Vexset[MVNum]; //标识各个顶点所属的连通重量，只抉择不再同一连通重量的边//函数申明void printGraph(AMGraph G);int LocateVex(AMGraph G, char v);void InitEArray(int i, VerTexType Head, VerTexType Tail, ArcType lowcost);//创立无向网void CreateUDN(AMGraph &G){ G.vexnum = 6; //输出总顶点数和边数 G.arcnum = 10; G.vexs[0] = 'v1'; //输出顶点信息 G.vexs[1] = 'v2'; G.vexs[2] = 'v3'; G.vexs[3] = 'v4'; G.vexs[4] = 'v5'; G.vexs[5] = 'v6'; //初始化邻接矩阵为极大值 for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { G.arcs[i][j] = MaxInt; } } //建设边 int i, j; i = LocateVex(G, 'v1'); j = LocateVex(G, 'v2'); G.arcs[i][j] = G.arcs[j][i] = 6; InitEArray(1, 'v1', 'v2' , 6); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v1'); j = LocateVex(G, 'v3'); G.arcs[i][j] = G.arcs[j][i] = 1; InitEArray(2, 'v1', 'v3', 1); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v1'); j = LocateVex(G, 'v4'); G.arcs[i][j] = G.arcs[j][i] = 5; InitEArray(3, 'v1', 'v4',5); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v2'); j = LocateVex(G, 'v3'); G.arcs[i][j] = G.arcs[j][i] = 5; InitEArray(4, 'v2', 'v3',5); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v2'); j = LocateVex(G, 'v5'); G.arcs[i][j] = G.arcs[j][i] = 3; InitEArray(5, 'v2', 'v5', 3); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v3'); j = LocateVex(G, 'v5'); G.arcs[i][j] = G.arcs[j][i] = 6; InitEArray(6, 'v3', 'v5',6); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v3'); j = LocateVex(G, 'v6'); G.arcs[i][j] = G.arcs[j][i] = 4; InitEArray(7, 'v3', 'v6',4); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v3'); j = LocateVex(G, 'v4'); G.arcs[i][j] = G.arcs[j][i] = 5; InitEArray(8, 'v3', 'v4', 5); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v4'); j = LocateVex(G, 'v6'); G.arcs[i][j] = G.arcs[j][i] = 2; InitEArray(9, 'v4', 'v6', 2); //初始化克鲁斯卡尔辅助数组E i = LocateVex(G, 'v5'); j = LocateVex(G, 'v6'); G.arcs[i][j] = G.arcs[j][i] = 6; InitEArray(10, 'v5', 'v6',6); //初始化克鲁斯卡尔辅助数组E printGraph(G);}//查找指定顶点的数组下标，并返回int LocateVex(AMGraph G, char v){ for (int i = 0; i < G.vexnum; i++) { if (G.vexs[i] == v) { return i; } }}//打印输出图void printGraph(AMGraph G){ for (int i = 0; i < G.vexnum; i++) { printf("v%d :", i + 1); for (int j = 0; j < G.vexnum; j++) { printf("%d ", G.arcs[i][j]); } printf("\n"); }}//邻接矩阵深度优先遍历bool visited[MVNum];void DFS_AM(AMGraph G, int v){ printf("v%c->", G.vexs[v]); visited[v] = true; for (int w = 0; w < G.vexnum; w++) { if ((G.arcs[v][w]) != 0 && (!visited[w])) { DFS_AM(G, w); } }}//间接插入排序算法void InsertSort(Edge E) { int i, j; for (i = 2; i <= 11; ++i) //辅助数组E的0号不必，故总长度为11 { E[0] = E[i]; //哨兵 j = i - 1; while (E[0].lowcost<E[j].lowcost) { E[j+1] = E[j]; j--; } E[j + 1] = E[0]; }}//最小生成树克鲁斯卡尔算法void MiniSpanTree_Kruskal(AMGraph G){ InsertSort(E); //排序 for (int i = 0; i < G.vexnum; ++i) { Vexset[i] = i; //初始化连通重量辅助数组，各顶点自成一个连通重量 } printf("\n======================\n"); printf("最小生成树结构程序："); for (int i = 0; i < G.arcnum; ++i) { int v1 = LocateVex(G, E[i].Head); //v1为边的始点下标 int v2 = LocateVex(G, E[i].Tail); //v2为边的起点下标 int vs1 = Vexset[v1]; //vs1为v1的连通重量 int vs2 = Vexset[v2]; //vs2为v2的连通重量 if (vs1 != vs2) //抉择不再同一连通重量的顶点 { printf("\nv%c -> v%c", G.vexs[v1], G.vexs[v2]); //输入抉择 //扭转输入顶点的连通重量为同一个 for (int j = 0; j < G.arcnum;++j) { if (Vexset[j] == vs2) { Vexset[j] = vs1; //把连通重量为vs2的全副改成vs1 } } } }}//初始化辅助数组void InitEArray(int i,VerTexType Head, VerTexType Tail, ArcType lowcost){ E[i].Head = Head; E[i].Tail = Tail; E[i].lowcost = lowcost;}int main(){ AMGraph G; CreateUDN(G); int v = 0; printf("\n======================\n"); printf("邻接矩阵深度优先遍历："); DFS_AM(G, v); MiniSpanTree_Kruskal(G);}最短门路
Dijkstra算法
基本原理
Dijkstra算法是依据贪婪算法实现的，首先找出以后点到所有能达到的点之间最短的间隔，而后松弛一次持续循环。所谓松弛一次，就是在曾经拜访过的点中遍历一遍，看看有没有更近的，如果有更近的就更新间隔。这样每次找最近的可达点+松弛遍历历史节点的操作，始终反复就能找到最短门路。
Dijkstra算法是典型最短门路算法，用于计算一个节点到其余节点的最短门路。
它的次要特点是以起始点为核心向外层层扩大(广度优先搜寻思维)，直到扩大到起点为止。
根本步骤
通过Dijkstra计算图G中的最短门路时，须要指定终点s(即从顶点s开始计算)。
此外，引进两个汇合S和U。S的作用是记录已求出最短门路的顶点(以及相应的最短门路长度)，而U则是记录还未求出最短门路的顶点(以及该顶点到终点s的间隔)。
初始时，S中只有终点s；U中是除s之外的顶点，并且U中顶点的门路是"终点s到该顶点的门路"。
而后，从U中找出门路最短的顶点，并将其退出到S中；
接着，更新U中的顶点和顶点对应的门路，再从U中找出门路最短的顶点，并将其退出到S中；
接着，更新U中的顶点和顶点对应的门路。
…
反复该操作，直到遍历完所有顶点。
图解（有向图）
首先看一个图，指标是找到从1到6的最短距离
首先用一个6*6的二维数组存储间隔信息，纵坐标为终点，横坐标为起点，对应的坐标值就是终点到起点的间隔，其中，不可达点的间隔为无穷大，到本身的间隔为0。
接着用一个一维数组来存储门路
从点1开始，遍历二维数组的第一行，发现间隔1是最小的，对应点1到点2，选定点2；松弛，没有更近值；
从点2开始，遍历二维数组的第二行，发现间隔3是最小的，对应点2到点4，选定点4；松弛，没有更近值；
从点4开始，遍历二维数组的第四行，发现间隔4是最小的，对应点4到点3，选定点3；松弛，没有更近值；
从点3开始，遍历二维数组的第三行，发现间隔5是最小的，对应点3到点5，选定点5；松弛，没有更近值；
从点5开始，遍历二维数组的第五行，发现间隔4是最小的，对应点5到点6，选定点6；松弛，没有更近值；
点6，曾经达到指标节点，遍历完结
图解（无向图）
留神：B（23）应该为B（13）
初始状态：S是已计算出最短门路的顶点汇合，U是未计算除最短门路的顶点的汇合！
第1步：将顶点D退出到S中。
此时，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 注:C(3)示意C到终点D的间隔是3。
第2步：将顶点C退出到S中。
上一步操作之后，U中顶点C到终点D的间隔最短；因而，将C退出到S中，同时更新U中顶点的间隔。以顶点F为例，之前F到D的间隔为∞；然而将C退出到S之后，F到D的间隔为9=(F,C)+(C,D)。
此时，S={D(0),C(3)}, U={A(∞),B(13),E(4),F(9),G(∞)}。
第3步：将顶点E退出到S中。
上一步操作之后，U中顶点E到终点D的间隔最短；因而，将E退出到S中，同时更新U中顶点的间隔。还是以顶点F为例，之前F到D的间隔为9；然而将E退出到S之后，F到D的间隔为6=(F,E)+(E,D)。
此时，S={D(0),C(3),E(4)}, U={A(∞),B(13),F(6),G(12)}。
第4步：将顶点F退出到S中。
此时，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。
第5步：将顶点G退出到S中。
此时，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。
第6步：将顶点B退出到S中。
此时，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。
第7步：将顶点A退出到S中。
此时，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。
此时，终点D到各个顶点的最短距离就计算出来了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。
Code
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#define Inf 0x3f3f3f3f using namespace std; int map[1005][1005]; int vis[1005],dis[1005];int n,m;//n个点，m条边 void Init (){ memset(map,Inf,sizeof(map)); for(int i=1;i<=n;i++) { map[i][i]=0; }} void Getmap(){ int u,v,w; for(int t=1;t<=m;t++) { scanf("%d%d%d",&u,&v,&w); if(map[u][v]>w) { map[u][v]=w; map[v][u]=w; } } } void Dijkstra(int u){ memset(vis,0,sizeof(vis)); for(int t=1;t<=n;t++) { dis[t]=map[u][t]; } vis[u]=1; for(int t=1;t<n;t++) { int minn=Inf,temp; for(int i=1;i<=n;i++) { if(!vis[i]&&dis[i]<minn) { minn=dis[i]; temp=i; } } vis[temp]=1; for(int i=1;i<=n;i++) { if(map[temp][i]+dis[temp]<dis[i]) { dis[i]=map[temp][i]+dis[temp]; } } } } int main(){ scanf("%d%d",&m,&n); Init(); Getmap(); Dijkstra(n); printf("%d\n",dis[1]); return 0;}//邻接矩阵// 邻接矩阵typedef struct _graph{ char vexs[MAX]; // 顶点汇合 int vexnum; // 顶点数 int edgnum; // 边数 int matrix[MAX][MAX]; // 邻接矩阵}Graph, *PGraph;// 边的构造体typedef struct _EdgeData{ char start; // 边的终点 char end; // 边的起点 int weight; // 边的权重}EData;/*Graph是邻接矩阵对应的构造体。vexs用于保留顶点，vexnum是顶点数，edgnum是边数；matrix则是用于保留矩阵信息的二维数组。例如，matrix[i][j]=1，则示意"顶点i(即vexs[i])"和"顶点j(即vexs[j])"是邻接点；matrix[i][j]=0，则示意它们不是邻接点。EData是邻接矩阵边对应的构造体。*//* * Dijkstra最短门路。 * 即，统计图(G)中"顶点vs"到其它各个顶点的最短门路。 * * 参数阐明： * G -- 图 * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短门路。 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短门路所经验的全副顶点中，位于"顶点i"之前的那个顶点。 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短门路的长度。 */void dijkstra(Graph G, int vs, int prev[], int dist[]){ int i,j,k; int min; int tmp; int flag[MAX]; // flag[i]=1示意"顶点vs"到"顶点i"的最短门路已胜利获取。 // 初始化 for (i = 0; i < G.vexnum; i++) { flag[i] = 0; // 顶点i的最短门路还没获取到。 prev[i] = 0; // 顶点i的前驱顶点为0。 dist[i] = G.matrix[vs][i];// 顶点i的最短门路为"顶点vs"到"顶点i"的权。 } // 对"顶点vs"本身进行初始化 flag[vs] = 1; dist[vs] = 0; // 遍历G.vexnum-1次；每次找出一个顶点的最短门路。 for (i = 1; i < G.vexnum; i++) { // 寻找以后最小的门路； // 即，在未获取最短门路的顶点中，找到离vs最近的顶点(k)。 min = INF; for (j = 0; j < G.vexnum; j++) { if (flag[j]==0 && dist[j]<min) { min = dist[j]; k = j; } } // 标记"顶点k"为曾经获取到最短门路 flag[k] = 1; // 修改以后最短门路和前驱顶点 // 即，当曾经"顶点k的最短门路"之后，更新"未获取最短门路的顶点的最短门路和前驱顶点"。 for (j = 0; j < G.vexnum; j++) { tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 避免溢出 if (flag[j] == 0 && (tmp < dist[j]) ) { dist[j] = tmp; prev[j] = k; } } } // 打印dijkstra最短门路的后果 printf("dijkstra(%c): \n", G.vexs[vs]); for (i = 0; i < G.vexnum; i++) printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]);}堆优化Dijkstra
代码如下，正文集体感觉曾经很分明了。#include<iostream>#include<cstdio>#include<cstring>#include<queue>using namespace std;int cnt=0;//边的序号 int dis[5000010],vis[5000010],h[5000010];//dis：终点到该点的长度 vis：是否拜访过了 h：终点为h[?]的暂存平台 struct node//next：下一个连贯某个点的下一条边 to:该边指向的下一条边 val：边权 { int next,to,val; //int from; from在链式前向星的遍历里意义不大 }edg[5000010];struct heapnode//重载小根堆{ int num,dist;//num：标号 dist:间隔 bool operator<(heapnode t) const//记住这种非凡写法就能够了 { return dist>t.dist;//与sort相同，此处为从小到大 }};priority_queue<heapnode>q;//定义一个heapnode模式的优先队列q int cread()//快读 { int f=1,x=0; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f;}void add(int u,int v,int val){ ++cnt;//一条新边 edg[cnt].to=v;//记录到哪里 edg[cnt].val=val;//记录边权 edg[cnt].next=h[u];//链式前向星的菊花搜图法 h[u]=cnt;//暂存桌面 }int main(){ int n,m,s;//n：点数 m：边数 s：终点 n=cread();m=cread();s=cread(); int x,y,z; for(int i=1;i<=m;i++) { x=cread();y=cread();z=cread(); add(x,y,z); } for(int i=1;i<=n;i++)dis[i]=0x7fffffff;//初始化极大值须要用for，memset会出错 memset(vis,0,sizeof(vis));//初始化拜访标记 dis[s]=0;//终点到终点天然为0 heapnode tem;//定义一个跑腿tem tem.dist=0;tem.num=s;//记录终点信息 q.push(tem);//跑腿记录的货色入队 while(!q.empty())//队不空 { heapnode u=q.top();//应用u记录队首信息（最小值） q.pop();//队首gg if(vis[u.num])continue;//如果曾经拜访过了，跳过 vis[u.num]=1;//标记拜访过了 for(int i=h[u.num];i!=0;i=edg[i].next)//链式前向星式菊花搜图 { int v=edg[i].to;//记录某条边的达到处 if(!vis[v]&&(dis[v]>dis[u.num]+edg[i].val))//如果说v没被拜访过并且原来到v的途程大于从这条边通过的到v途程 { dis[v]=dis[u.num]+edg[i].val;//更新到v的途程 tem.num=v;tem.dist=dis[v];//跑腿记录v的信息 q.push(tem);//跑腿入队 } } } for(int i=1;i<=n;i++) printf("%d ",dis[i]);//到每个点的间隔输入 return 0;}Floyd算法
简介
通过Floyd计算图G=(V,E)中各个顶点的最短门路时，须要引入一个矩阵S，矩阵S中的元素ai示意顶点i(第i个顶点)到顶点j(第j个顶点)的间隔。
假如图G中顶点个数为N，则须要对矩阵S进行N次更新。初始时，矩阵S中顶点ai的间隔为顶点i到顶点j的权值；如果i和j不相邻，则ai=∞。 接下来开始，对矩阵S进行N次更新。第1次更新时，如果"ai的间隔" > "ai+a0"(ai+a0示意"i与j之间通过第1个顶点的间隔")，则更新ai为"ai+a0"。 同理，第k次更新时，如果"ai的间隔" > "ai+ak"，则更新ai为"ai+ak"。更新N次之后，操作实现！
Code
class MatrixUDG { #define MAX 100 #define INF (~(0x1<<31)) // 无穷大(即0X7FFFFFFF) private: char mVexs[MAX]; // 顶点汇合 int mVexNum; // 顶点数 int mEdgNum; // 边数 int mMatrix[MAX][MAX]; // 邻接矩阵 public: // 创立图(本人输出数据) MatrixUDG(); // 创立图(用已提供的矩阵) //MatrixUDG(char vexs[], int vlen, char edges[][2], int elen); MatrixUDG(char vexs[], int vlen, int matrix[][9]); ~MatrixUDG(); // 深度优先搜寻遍历图 void DFS(); // 广度优先搜寻（相似于树的档次遍历） void BFS(); // prim最小生成树(从start开始生成最小生成树) void prim(int start); // 克鲁斯卡尔（Kruskal)最小生成树 void kruskal(); // Dijkstra最短门路 void dijkstra(int vs, int vexs[], int dist[]); // Floyd最短门路 void floyd(int path[][MAX], int dist[][MAX]); // 打印矩阵队列图 void print(); private: // 读取一个输出字符 char readChar(); // 返回ch在mMatrix矩阵中的地位 int getPosition(char ch); // 返回顶点v的第一个邻接顶点的索引，失败则返回-1 int firstVertex(int v); // 返回顶点v绝对于w的下一个邻接顶点的索引，失败则返回-1 int nextVertex(int v, int w); // 深度优先搜寻遍历图的递归实现 void DFS(int i, int *visited); // 获取图中的边 EData* getEdges(); // 对边依照权值大小进行排序(由小到大) void sortEdges(EData* edges, int elen); // 获取i的起点 int getEnd(int vends[], int i);};/*Graph是邻接矩阵对应的构造体。vexs用于保留顶点，vexnum是顶点数，edgnum是边数；matrix则是用于保留矩阵信息的二维数组。例如，matrix[i][j]=1，则示意"顶点i(即vexs[i])"和"顶点j(即vexs[j])"是邻接点；matrix[i][j]=0，则示意它们不是邻接点。*//* * floyd最短门路。 * 即，统计图中各个顶点间的最短门路。 * * 参数阐明： * path -- 门路。path[i][j]=k示意，"顶点i"到"顶点j"的最短门路会通过顶点k。 * dist -- 长度数组。即，dist[i][j]=sum示意，"顶点i"到"顶点j"的最短门路的长度是sum。 */void MatrixUDG::floyd(int path[][MAX], int dist[][MAX]){ int i,j,k; int tmp; // 初始化 for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) { dist[i][j] = mMatrix[i][j]; // "顶点i"到"顶点j"的门路长度为"i到j的权值"。 path[i][j] = j; // "顶点i"到"顶点j"的最短门路是通过顶点j。 } } // 计算最短门路 for (k = 0; k < mVexNum; k++) { for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) { // 如果通过下标为k顶点门路比原两点间门路更短，则更新dist[i][j]和path[i][j] tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]); if (dist[i][j] > tmp) { // "i到j最短门路"对应的值设，为更小的一个(即通过k) dist[i][j] = tmp; // "i到j最短门路"对应的门路，通过k path[i][j] = path[i][k]; } } } } // 打印floyd最短门路的后果 cout << "floyd: " << endl; for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) cout << setw(2) << dist[i][j] << " "; cout << endl; }}邻接表Code
/** * C++: Dijkstra算法获取最短门路(邻接表) * * @author skywang * @date 2014/04/24 */#include <iomanip>#include <iostream>#include <vector>using namespace std;// 示例类：边的构造体(用来演示)class EData{ public: char start; // 边的终点 char end; // 边的起点 int weight; // 边的权重 public: EData(){} EData(char s, char e, int w):start(s),end(e),weight(w){}};// 邻接表class ListUDG{#define MAX 100#define INF (~(0x1<<31)) // 最大值(即0X7FFFFFFF) private: // 外部类 // 邻接表中表对应的链表的顶点 class ENode { int ivex; // 该边所指向的顶点的地位 int weight; // 该边的权 ENode *nextEdge; // 指向下一条弧的指针 friend class ListUDG; }; // 邻接表中表的顶点 class VNode { char data; // 顶点信息 ENode *firstEdge; // 指向第一条附丽该顶点的弧 friend class ListUDG; }; private: // 公有成员 int mVexNum; // 图的顶点的数目 int mEdgNum; // 图的边的数目 VNode mVexs[MAX]; public: // 创立邻接表对应的图(本人输出) ListUDG(); // 创立邻接表对应的图(用已提供的数据) ListUDG(char vexs[], int vlen, EData *edges[], int elen); ~ListUDG(); // 深度优先搜寻遍历图 void DFS(); // 广度优先搜寻（相似于树的档次遍历） void BFS(); // 打印邻接表图 void print(); // prim最小生成树 void prim(int start); // 克鲁斯卡尔（Kruskal)最小生成树 void kruskal(); // Dijkstra最短门路 void dijkstra(int vs, int vexs[], int dist[]); // Floyd最短门路 void floyd(int path[][MAX], int dist[][MAX]); private: // 读取一个输出字符 char readChar(); // 返回ch的地位 int getPosition(char ch); // 深度优先搜寻遍历图的递归实现 void DFS(int i, int *visited); // 将node节点链接到list的最初 void linkLast(ENode *list, ENode *node); // 获取边<start, end>的权值；若start和end不是连通的，则返回无穷大。 int getWeight(int start, int end); // 获取图中的边 EData* getEdges(); // 对边依照权值大小进行排序(由小到大) void sortEdges(EData* edges, int elen); // 获取i的起点 int getEnd(int vends[], int i);};/* * 创立邻接表对应的图(本人输出) */ListUDG::ListUDG(){ char c1, c2; int v, e; int i, p1, p2; int weight; ENode *node1, *node2; // 输出"顶点数"和"边数" cout << "input vertex number: "; cin >> mVexNum; cout << "input edge number: "; cin >> mEdgNum; if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1)))) { cout << "input error: invalid parameters!" << endl; return ; } // 初始化"邻接表"的顶点 for(i=0; i<mVexNum; i++) { cout << "vertex(" << i << "): "; mVexs[i].data = readChar(); mVexs[i].firstEdge = NULL; } // 初始化"邻接表"的边 for(i=0; i<mEdgNum; i++) { // 读取边的起始顶点和完结顶点 cout << "edge(" << i << "): "; c1 = readChar(); c2 = readChar(); cin >> weight; p1 = getPosition(c1); p2 = getPosition(c2); // 初始化node1 node1 = new ENode(); node1->ivex = p2; node1->weight = weight; // 将node1链接到"p1所在链表的开端" if(mVexs[p1].firstEdge == NULL) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 node2 = new ENode(); node2->ivex = p1; node2->weight = weight; // 将node2链接到"p2所在链表的开端" if(mVexs[p2].firstEdge == NULL) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); }}/* * 创立邻接表对应的图(用已提供的数据) */ListUDG::ListUDG(char vexs[], int vlen, EData *edges[], int elen){ char c1, c2; int i, p1, p2; int weight; ENode *node1, *node2; // 初始化"顶点数"和"边数" mVexNum = vlen; mEdgNum = elen; // 初始化"邻接表"的顶点 for(i=0; i<mVexNum; i++) { mVexs[i].data = vexs[i]; mVexs[i].firstEdge = NULL; } // 初始化"邻接表"的边 for(i=0; i<mEdgNum; i++) { // 读取边的起始顶点和完结顶点 c1 = edges[i]->start; c2 = edges[i]->end; weight = edges[i]->weight; p1 = getPosition(c1); p2 = getPosition(c2); // 初始化node1 node1 = new ENode(); node1->ivex = p2; node1->weight = weight; // 将node1链接到"p1所在链表的开端" if(mVexs[p1].firstEdge == NULL) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 node2 = new ENode(); node2->ivex = p1; node2->weight = weight; // 将node2链接到"p2所在链表的开端" if(mVexs[p2].firstEdge == NULL) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); }}/* * 析构函数 */ListUDG::~ListUDG() {}/* * 将node节点链接到list的最初 */void ListUDG::linkLast(ENode *list, ENode *node){ ENode *p = list; while(p->nextEdge) p = p->nextEdge; p->nextEdge = node;}/* * 返回ch的地位 */int ListUDG::getPosition(char ch){ int i; for(i=0; i<mVexNum; i++) if(mVexs[i].data==ch) return i; return -1;}/* * 读取一个输出字符 */char ListUDG::readChar(){ char ch; do { cin >> ch; } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z'))); return ch;}/* * 深度优先搜寻遍历图的递归实现 */void ListUDG::DFS(int i, int *visited){ ENode *node; visited[i] = 1; cout << mVexs[i].data << " "; node = mVexs[i].firstEdge; while (node != NULL) { if (!visited[node->ivex]) DFS(node->ivex, visited); node = node->nextEdge; }}/* * 深度优先搜寻遍历图 */void ListUDG::DFS(){ int i; int visited[MAX]; // 顶点拜访标记 // 初始化所有顶点都没有被拜访 for (i = 0; i < mVexNum; i++) visited[i] = 0; cout << "DFS: "; for (i = 0; i < mVexNum; i++) { if (!visited[i]) DFS(i, visited); } cout << endl;}/* * 广度优先搜寻（相似于树的档次遍历） */void ListUDG::BFS(){ int head = 0; int rear = 0; int queue[MAX]; // 辅组队列 int visited[MAX]; // 顶点拜访标记 int i, j, k; ENode *node; for (i = 0; i < mVexNum; i++) visited[i] = 0; cout << "BFS: "; for (i = 0; i < mVexNum; i++) { if (!visited[i]) { visited[i] = 1; cout << mVexs[i].data << " "; queue[rear++] = i; // 入队列 } while (head != rear) { j = queue[head++]; // 出队列 node = mVexs[j].firstEdge; while (node != NULL) { k = node->ivex; if (!visited[k]) { visited[k] = 1; cout << mVexs[k].data << " "; queue[rear++] = k; } node = node->nextEdge; } } } cout << endl;}/* * 打印邻接表图 */void ListUDG::print(){ int i,j; ENode *node; cout << "List Graph:" << endl; for (i = 0; i < mVexNum; i++) { cout << i << "(" << mVexs[i].data << "): "; node = mVexs[i].firstEdge; while (node != NULL) { cout << node->ivex << "(" << mVexs[node->ivex].data << ") "; node = node->nextEdge; } cout << endl; }}/* * 获取边<start, end>的权值；若start和end不是连通的，则返回无穷大。 */int ListUDG::getWeight(int start, int end){ ENode *node; if (start==end) return 0; node = mVexs[start].firstEdge; while (node!=NULL) { if (end==node->ivex) return node->weight; node = node->nextEdge; } return INF;}/* * prim最小生成树 * * 参数阐明： * start -- 从图中的第start个元素开始，生成最小树 */void ListUDG::prim(int start){ int min,i,j,k,m,n,tmp,sum; int index=0; // prim最小树的索引，即prims数组的索引 char prims[MAX]; // prim最小树的后果数组 int weights[MAX]; // 顶点间边的权值 // prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。 prims[index++] = mVexs[start].data; // 初始化"顶点的权值数组"， // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。 for (i = 0; i < mVexNum; i++ ) weights[i] = getWeight(start, i); for (i = 0; i < mVexNum; i++) { // 因为从start开始的，因而不须要再对第start个顶点进行解决。 if(start == i) continue; j = 0; k = 0; min = INF; // 在未被退出到最小生成树的顶点中，找出权值最小的顶点。 while (j < mVexNum) { // 若weights[j]=0，意味着"第j个节点曾经被排序过"(或者说曾经退出了最小生成树中)。 if (weights[j] != 0 && weights[j] < min) { min = weights[j]; k = j; } j++; } // 通过下面的解决后，在未被退出到最小生成树的顶点中，权值最小的顶点是第k个顶点。 // 将第k个顶点退出到最小生成树的后果数组中 prims[index++] = mVexs[k].data; // 将"第k个顶点的权值"标记为0，意味着第k个顶点曾经排序过了(或者说曾经退出了最小树后果中)。 weights[k] = 0; // 当第k个顶点被退出到最小生成树的后果数组中之后，更新其它顶点的权值。 for (j = 0 ; j < mVexNum; j++) { // 获取第k个顶点到第j个顶点的权值 tmp = getWeight(k, j); // 当第j个节点没有被解决，并且须要更新时才被更新。 if (weights[j] != 0 && tmp < weights[j]) weights[j] = tmp; } } // 计算最小生成树的权值 sum = 0; for (i = 1; i < index; i++) { min = INF; // 获取prims[i]在矩阵表中的地位 n = getPosition(prims[i]); // 在vexs[0...i]中，找出到j的权值最小的顶点。 for (j = 0; j < i; j++) { m = getPosition(prims[j]); tmp = getWeight(m, n); if (tmp < min) min = tmp; } sum += min; } // 打印最小生成树 cout << "PRIM(" << mVexs[start].data <<")=" << sum << ": "; for (i = 0; i < index; i++) cout << prims[i] << " "; cout << endl;}/* * 获取图中的边 */EData* ListUDG::getEdges(){ int i,j; int index=0; ENode *node; EData *edges; edges = new EData[mEdgNum]; for (i=0; i < mVexNum; i++) { node = mVexs[i].firstEdge; while (node != NULL) { if (node->ivex > i) { edges[index].start = mVexs[i].data; // 终点 edges[index].end = mVexs[node->ivex].data; // 起点 edges[index].weight = node->weight; // 权 index++; } node = node->nextEdge; } } return edges;}/* * 对边依照权值大小进行排序(由小到大) */void ListUDG::sortEdges(EData* edges, int elen){ int i,j; for (i=0; i<elen; i++) { for (j=i+1; j<elen; j++) { if (edges[i].weight > edges[j].weight) { // 替换"边i"和"边j" swap(edges[i], edges[j]); } } }}/* * 获取i的起点 */int ListUDG::getEnd(int vends[], int i){ while (vends[i] != 0) i = vends[i]; return i;}/* * 克鲁斯卡尔（Kruskal)最小生成树 */void ListUDG::kruskal(){ int i,m,n,p1,p2; int length; int index = 0; // rets数组的索引 int vends[MAX]={0}; // 用于保留"已有最小生成树"中每个顶点在该最小树中的起点。 EData rets[MAX]; // 后果数组，保留kruskal最小生成树的边 EData *edges; // 图对应的所有边 // 获取"图中所有的边" edges = getEdges(); // 将边依照"权"的大小进行排序(从小到大) sortEdges(edges, mEdgNum); for (i=0; i<mEdgNum; i++) { p1 = getPosition(edges[i].start); // 获取第i条边的"终点"的序号 p2 = getPosition(edges[i].end); // 获取第i条边的"起点"的序号 m = getEnd(vends, p1); // 获取p1在"已有的最小生成树"中的起点 n = getEnd(vends, p2); // 获取p2在"已有的最小生成树"中的起点 // 如果m!=n，意味着"边i"与"曾经增加到最小生成树中的顶点"没有造成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的起点为n rets[index++] = edges[i]; // 保留后果 } } delete[] edges; // 统计并打印"kruskal最小生成树"的信息 length = 0; for (i = 0; i < index; i++) length += rets[i].weight; cout << "Kruskal=" << length << ": "; for (i = 0; i < index; i++) cout << "(" << rets[i].start << "," << rets[i].end << ") "; cout << endl;}/* * Dijkstra最短门路。 * 即，统计图中"顶点vs"到其它各个顶点的最短门路。 * * 参数阐明： * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短门路。 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短门路所经验的全副顶点中，位于"顶点i"之前的那个顶点。 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短门路的长度。 */void ListUDG::dijkstra(int vs, int prev[], int dist[]){ int i,j,k; int min; int tmp; int flag[MAX]; // flag[i]=1示意"顶点vs"到"顶点i"的最短门路已胜利获取。 // 初始化 for (i = 0; i < mVexNum; i++) { flag[i] = 0; // 顶点i的最短门路还没获取到。 prev[i] = 0; // 顶点i的前驱顶点为0。 dist[i] = getWeight(vs, i); // 顶点i的最短门路为"顶点vs"到"顶点i"的权。 } // 对"顶点vs"本身进行初始化 flag[vs] = 1; dist[vs] = 0; // 遍历mVexNum-1次；每次找出一个顶点的最短门路。 for (i = 1; i < mVexNum; i++) { // 寻找以后最小的门路； // 即，在未获取最短门路的顶点中，找到离vs最近的顶点(k)。 min = INF; for (j = 0; j < mVexNum; j++) { if (flag[j]==0 && dist[j]<min) { min = dist[j]; k = j; } } // 标记"顶点k"为曾经获取到最短门路 flag[k] = 1; // 修改以后最短门路和前驱顶点 // 即，当曾经"顶点k的最短门路"之后，更新"未获取最短门路的顶点的最短门路和前驱顶点"。 for (j = 0; j < mVexNum; j++) { tmp = getWeight(k, j); tmp = (tmp==INF ? INF : (min + tmp)); // 避免溢出 if (flag[j] == 0 && (tmp < dist[j]) ) { dist[j] = tmp; prev[j] = k; } } } // 打印dijkstra最短门路的后果 cout << "dijkstra(" << mVexs[vs].data << "): " << endl; for (i = 0; i < mVexNum; i++) cout << " shortest(" << mVexs[vs].data << ", " << mVexs[i].data << ")=" << dist[i] << endl;}/* * floyd最短门路。 * 即，统计图中各个顶点间的最短门路。 * * 参数阐明： * path -- 门路。path[i][j]=k示意，"顶点i"到"顶点j"的最短门路会通过顶点k。 * dist -- 长度数组。即，dist[i][j]=sum示意，"顶点i"到"顶点j"的最短门路的长度是sum。 */void ListUDG::floyd(int path[][MAX], int dist[][MAX]){ int i,j,k; int tmp; // 初始化 for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) { dist[i][j] = getWeight(i, j); // "顶点i"到"顶点j"的门路长度为"i到j的权值"。 path[i][j] = j; // "顶点i"到"顶点j"的最短门路是通过顶点j。 } } // 计算最短门路 for (k = 0; k < mVexNum; k++) { for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) { // 如果通过下标为k顶点门路比原两点间门路更短，则更新dist[i][j]和path[i][j] tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]); if (dist[i][j] > tmp) { // "i到j最短门路"对应的值设，为更小的一个(即通过k) dist[i][j] = tmp; // "i到j最短门路"对应的门路，通过k path[i][j] = path[i][k]; } } } } // 打印floyd最短门路的后果 cout << "floyd: " << endl; for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) cout << setw(2) << dist[i][j] << " "; cout << endl; }}int main(){ int prev[MAX] = {0}; int dist[MAX] = {0}; int path[MAX][MAX] = {0}; // 用于保留floyd门路 int floy[MAX][MAX] = {0}; // 用于保留floyd长度 // 顶点 char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; // 边 EData *edges[] = { // 终点 起点 权 new EData('A', 'B', 12), new EData('A', 'F', 16), new EData('A', 'G', 14), new EData('B', 'C', 10), new EData('B', 'F', 7), new EData('C', 'D', 3), new EData('C', 'E', 5), new EData('C', 'F', 6), new EData('D', 'E', 4), new EData('E', 'F', 2), new EData('E', 'G', 8), new EData('F', 'G', 9), }; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); ListUDG* pG; // 自定义"图"(输出矩阵队列) //pG = new ListUDG(); // 采纳已有的"图" pG = new ListUDG(vexs, vlen, edges, elen); //pG->print(); // 打印图 //pG->DFS(); // 深度优先遍历 //pG->BFS(); // 广度优先遍历 //pG->prim(0); // prim算法生成最小生成树 //pG->kruskal(); // Kruskal算法生成最小生成树 // dijkstra算法获取"第4个顶点"到其它各个顶点的最短距离 //pG->dijkstra(3, prev, dist); // floyd算法获取各个顶点之间的最短距离 pG->floyd(path, floy); return 0;}邻接矩阵Code
/** * C++: Floyd算法获取最短门路(邻接矩阵) * * @author skywang * @date 2014/04/25 */#include <iomanip>#include <iostream>#include <vector>using namespace std;// 边的构造体class EData{ public: char start; // 边的终点 char end; // 边的起点 int weight; // 边的权重 public: EData(){} EData(char s, char e, int w):start(s),end(e),weight(w){}};class MatrixUDG { #define MAX 100 #define INF (~(0x1<<31)) // 无穷大(即0X7FFFFFFF) private: char mVexs[MAX]; // 顶点汇合 int mVexNum; // 顶点数 int mEdgNum; // 边数 int mMatrix[MAX][MAX]; // 邻接矩阵 public: // 创立图(本人输出数据) MatrixUDG(); // 创立图(用已提供的矩阵) //MatrixUDG(char vexs[], int vlen, char edges[][2], int elen); MatrixUDG(char vexs[], int vlen, int matrix[][9]); ~MatrixUDG(); // 深度优先搜寻遍历图 void DFS(); // 广度优先搜寻（相似于树的档次遍历） void BFS(); // prim最小生成树(从start开始生成最小生成树) void prim(int start); // 克鲁斯卡尔（Kruskal)最小生成树 void kruskal(); // Dijkstra最短门路 void dijkstra(int vs, int vexs[], int dist[]); // Floyd最短门路 void floyd(int path[][MAX], int dist[][MAX]); // 打印矩阵队列图 void print(); private: // 读取一个输出字符 char readChar(); // 返回ch在mMatrix矩阵中的地位 int getPosition(char ch); // 返回顶点v的第一个邻接顶点的索引，失败则返回-1 int firstVertex(int v); // 返回顶点v绝对于w的下一个邻接顶点的索引，失败则返回-1 int nextVertex(int v, int w); // 深度优先搜寻遍历图的递归实现 void DFS(int i, int *visited); // 获取图中的边 EData* getEdges(); // 对边依照权值大小进行排序(由小到大) void sortEdges(EData* edges, int elen); // 获取i的起点 int getEnd(int vends[], int i);};/* * 创立图(本人输出数据) */MatrixUDG::MatrixUDG(){ char c1, c2; int i, j, weight, p1, p2; // 输出"顶点数"和"边数" cout << "input vertex number: "; cin >> mVexNum; cout << "input edge number: "; cin >> mEdgNum; if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1)))) { cout << "input error: invalid parameters!" << endl; return ; } // 初始化"顶点" for (i = 0; i < mVexNum; i++) { cout << "vertex(" << i << "): "; mVexs[i] = readChar(); } // 1. 初始化"边"的权值 for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) { if (i==j) mMatrix[i][j] = 0; else mMatrix[i][j] = INF; } } // 2. 初始化"边"的权值: 依据用户的输出进行初始化 for (i = 0; i < mEdgNum; i++) { // 读取边的起始顶点，完结顶点，权值 cout << "edge(" << i << "): "; c1 = readChar(); c2 = readChar(); cin >> weight; p1 = getPosition(c1); p2 = getPosition(c2); if (p1==-1 || p2==-1) { cout << "input error: invalid edge!" << endl; return ; } mMatrix[p1][p2] = weight; mMatrix[p2][p1] = weight; }}/* * 创立图(用已提供的矩阵) * * 参数阐明： * vexs -- 顶点数组 * vlen -- 顶点数组的长度 * matrix-- 矩阵(数据) */MatrixUDG::MatrixUDG(char vexs[], int vlen, int matrix[][9]){ int i, j; // 初始化"顶点数"和"边数" mVexNum = vlen; // 初始化"顶点" for (i = 0; i < mVexNum; i++) mVexs[i] = vexs[i]; // 初始化"边" for (i = 0; i < mVexNum; i++) for (j = 0; j < mVexNum; j++) mMatrix[i][j] = matrix[i][j]; // 统计边的数目 for (i = 0; i < mVexNum; i++) for (j = 0; j < mVexNum; j++) if (i!=j && mMatrix[i][j]!=INF) mEdgNum++; mEdgNum /= 2;}/* * 析构函数 */MatrixUDG::~MatrixUDG() {}/* * 返回ch在mMatrix矩阵中的地位 */int MatrixUDG::getPosition(char ch){ int i; for(i=0; i<mVexNum; i++) if(mVexs[i]==ch) return i; return -1;}/* * 读取一个输出字符 */char MatrixUDG::readChar(){ char ch; do { cin >> ch; } while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z'))); return ch;}/* * 返回顶点v的第一个邻接顶点的索引，失败则返回-1 */int MatrixUDG::firstVertex(int v){ int i; if (v<0 || v>(mVexNum-1)) return -1; for (i = 0; i < mVexNum; i++) if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF) return i; return -1;}/* * 返回顶点v绝对于w的下一个邻接顶点的索引，失败则返回-1 */int MatrixUDG::nextVertex(int v, int w){ int i; if (v<0 || v>(mVexNum-1) || w<0 || w>(mVexNum-1)) return -1; for (i = w + 1; i < mVexNum; i++) if (mMatrix[v][i]!=0 && mMatrix[v][i]!=INF) return i; return -1;}/* * 深度优先搜寻遍历图的递归实现 */void MatrixUDG::DFS(int i, int *visited){ int w; visited[i] = 1; cout << mVexs[i] << " "; // 遍历该顶点的所有邻接顶点。若是没有拜访过，那么持续往下走 for (w = firstVertex(i); w >= 0; w = nextVertex(i, w)) { if (!visited[w]) DFS(w, visited); } }/* * 深度优先搜寻遍历图 */void MatrixUDG::DFS(){ int i; int visited[MAX]; // 顶点拜访标记 // 初始化所有顶点都没有被拜访 for (i = 0; i < mVexNum; i++) visited[i] = 0; cout << "DFS: "; for (i = 0; i < mVexNum; i++) { //printf("\n== LOOP(%d)\n", i); if (!visited[i]) DFS(i, visited); } cout << endl;}/* * 广度优先搜寻（相似于树的档次遍历） */void MatrixUDG::BFS(){ int head = 0; int rear = 0; int queue[MAX]; // 辅组队列 int visited[MAX]; // 顶点拜访标记 int i, j, k; for (i = 0; i < mVexNum; i++) visited[i] = 0; cout << "BFS: "; for (i = 0; i < mVexNum; i++) { if (!visited[i]) { visited[i] = 1; cout << mVexs[i] << " "; queue[rear++] = i; // 入队列 } while (head != rear) { j = queue[head++]; // 出队列 for (k = firstVertex(j); k >= 0; k = nextVertex(j, k)) //k是为拜访的邻接顶点 { if (!visited[k]) { visited[k] = 1; cout << mVexs[k] << " "; queue[rear++] = k; } } } } cout << endl;}/* * 打印矩阵队列图 */void MatrixUDG::print(){ int i,j; cout << "Martix Graph:" << endl; for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) cout << setw(10) << mMatrix[i][j] << " "; cout << endl; }}/* * prim最小生成树 * * 参数阐明： * start -- 从图中的第start个元素开始，生成最小树 */void MatrixUDG::prim(int start){ int min,i,j,k,m,n,sum; int index=0; // prim最小树的索引，即prims数组的索引 char prims[MAX]; // prim最小树的后果数组 int weights[MAX]; // 顶点间边的权值 // prim最小生成树中第一个数是"图中第start个顶点"，因为是从start开始的。 prims[index++] = mVexs[start]; // 初始化"顶点的权值数组"， // 将每个顶点的权值初始化为"第start个顶点"到"该顶点"的权值。 for (i = 0; i < mVexNum; i++ ) weights[i] = mMatrix[start][i]; // 将第start个顶点的权值初始化为0。 // 能够了解为"第start个顶点到它本身的间隔为0"。 weights[start] = 0; for (i = 0; i < mVexNum; i++) { // 因为从start开始的，因而不须要再对第start个顶点进行解决。 if(start == i) continue; j = 0; k = 0; min = INF; // 在未被退出到最小生成树的顶点中，找出权值最小的顶点。 while (j < mVexNum) { // 若weights[j]=0，意味着"第j个节点曾经被排序过"(或者说曾经退出了最小生成树中)。 if (weights[j] != 0 && weights[j] < min) { min = weights[j]; k = j; } j++; } // 通过下面的解决后，在未被退出到最小生成树的顶点中，权值最小的顶点是第k个顶点。 // 将第k个顶点退出到最小生成树的后果数组中 prims[index++] = mVexs[k]; // 将"第k个顶点的权值"标记为0，意味着第k个顶点曾经排序过了(或者说曾经退出了最小树后果中)。 weights[k] = 0; // 当第k个顶点被退出到最小生成树的后果数组中之后，更新其它顶点的权值。 for (j = 0 ; j < mVexNum; j++) { // 当第j个节点没有被解决，并且须要更新时才被更新。 if (weights[j] != 0 && mMatrix[k][j] < weights[j]) weights[j] = mMatrix[k][j]; } } // 计算最小生成树的权值 sum = 0; for (i = 1; i < index; i++) { min = INF; // 获取prims[i]在mMatrix中的地位 n = getPosition(prims[i]); // 在vexs[0...i]中，找出到j的权值最小的顶点。 for (j = 0; j < i; j++) { m = getPosition(prims[j]); if (mMatrix[m][n]<min) min = mMatrix[m][n]; } sum += min; } // 打印最小生成树 cout << "PRIM(" << mVexs[start] << ")=" << sum << ": "; for (i = 0; i < index; i++) cout << prims[i] << " "; cout << endl;}/* * 获取图中的边 */EData* MatrixUDG::getEdges(){ int i,j; int index=0; EData *edges; edges = new EData[mEdgNum]; for (i=0; i < mVexNum; i++) { for (j=i+1; j < mVexNum; j++) { if (mMatrix[i][j]!=INF) { edges[index].start = mVexs[i]; edges[index].end = mVexs[j]; edges[index].weight = mMatrix[i][j]; index++; } } } return edges;}/* * 对边依照权值大小进行排序(由小到大) */void MatrixUDG::sortEdges(EData* edges, int elen){ int i,j; for (i=0; i<elen; i++) { for (j=i+1; j<elen; j++) { if (edges[i].weight > edges[j].weight) { // 替换"边i"和"边j" swap(edges[i], edges[j]); } } }}/* * 获取i的起点 */int MatrixUDG::getEnd(int vends[], int i){ while (vends[i] != 0) i = vends[i]; return i;}/* * 克鲁斯卡尔（Kruskal)最小生成树 */void MatrixUDG::kruskal(){ int i,m,n,p1,p2; int length; int index = 0; // rets数组的索引 int vends[MAX]={0}; // 用于保留"已有最小生成树"中每个顶点在该最小树中的起点。 EData rets[MAX]; // 后果数组，保留kruskal最小生成树的边 EData *edges; // 图对应的所有边 // 获取"图中所有的边" edges = getEdges(); // 将边依照"权"的大小进行排序(从小到大) sortEdges(edges, mEdgNum); for (i=0; i<mEdgNum; i++) { p1 = getPosition(edges[i].start); // 获取第i条边的"终点"的序号 p2 = getPosition(edges[i].end); // 获取第i条边的"起点"的序号 m = getEnd(vends, p1); // 获取p1在"已有的最小生成树"中的起点 n = getEnd(vends, p2); // 获取p2在"已有的最小生成树"中的起点 // 如果m!=n，意味着"边i"与"曾经增加到最小生成树中的顶点"没有造成环路 if (m != n) { vends[m] = n; // 设置m在"已有的最小生成树"中的起点为n rets[index++] = edges[i]; // 保留后果 } } delete[] edges; // 统计并打印"kruskal最小生成树"的信息 length = 0; for (i = 0; i < index; i++) length += rets[i].weight; cout << "Kruskal=" << length << ": "; for (i = 0; i < index; i++) cout << "(" << rets[i].start << "," << rets[i].end << ") "; cout << endl;}/* * Dijkstra最短门路。 * 即，统计图中"顶点vs"到其它各个顶点的最短门路。 * * 参数阐明： * vs -- 起始顶点(start vertex)。即计算"顶点vs"到其它顶点的最短门路。 * prev -- 前驱顶点数组。即，prev[i]的值是"顶点vs"到"顶点i"的最短门路所经验的全副顶点中，位于"顶点i"之前的那个顶点。 * dist -- 长度数组。即，dist[i]是"顶点vs"到"顶点i"的最短门路的长度。 */void MatrixUDG::dijkstra(int vs, int prev[], int dist[]){ int i,j,k; int min; int tmp; int flag[MAX]; // flag[i]=1示意"顶点vs"到"顶点i"的最短门路已胜利获取。 // 初始化 for (i = 0; i < mVexNum; i++) { flag[i] = 0; // 顶点i的最短门路还没获取到。 prev[i] = 0; // 顶点i的前驱顶点为0。 dist[i] = mMatrix[vs][i]; // 顶点i的最短门路为"顶点vs"到"顶点i"的权。 } // 对"顶点vs"本身进行初始化 flag[vs] = 1; dist[vs] = 0; // 遍历mVexNum-1次；每次找出一个顶点的最短门路。 for (i = 1; i < mVexNum; i++) { // 寻找以后最小的门路； // 即，在未获取最短门路的顶点中，找到离vs最近的顶点(k)。 min = INF; for (j = 0; j < mVexNum; j++) { if (flag[j]==0 && dist[j]<min) { min = dist[j]; k = j; } } // 标记"顶点k"为曾经获取到最短门路 flag[k] = 1; // 修改以后最短门路和前驱顶点 // 即，当曾经"顶点k的最短门路"之后，更新"未获取最短门路的顶点的最短门路和前驱顶点"。 for (j = 0; j < mVexNum; j++) { tmp = (mMatrix[k][j]==INF ? INF : (min + mMatrix[k][j])); if (flag[j] == 0 && (tmp < dist[j]) ) { dist[j] = tmp; prev[j] = k; } } } // 打印dijkstra最短门路的后果 cout << "dijkstra(" << mVexs[vs] << "): " << endl; for (i = 0; i < mVexNum; i++) cout << " shortest(" << mVexs[vs] << ", " << mVexs[i] << ")=" << dist[i] << endl;}/* * floyd最短门路。 * 即，统计图中各个顶点间的最短门路。 * * 参数阐明： * path -- 门路。path[i][j]=k示意，"顶点i"到"顶点j"的最短门路会通过顶点k。 * dist -- 长度数组。即，dist[i][j]=sum示意，"顶点i"到"顶点j"的最短门路的长度是sum。 */void MatrixUDG::floyd(int path[][MAX], int dist[][MAX]){ int i,j,k; int tmp; // 初始化 for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) { dist[i][j] = mMatrix[i][j]; // "顶点i"到"顶点j"的门路长度为"i到j的权值"。 path[i][j] = j; // "顶点i"到"顶点j"的最短门路是通过顶点j。 } } // 计算最短门路 for (k = 0; k < mVexNum; k++) { for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) { // 如果通过下标为k顶点门路比原两点间门路更短，则更新dist[i][j]和path[i][j] tmp = (dist[i][k]==INF || dist[k][j]==INF) ? INF : (dist[i][k] + dist[k][j]); if (dist[i][j] > tmp) { // "i到j最短门路"对应的值设，为更小的一个(即通过k) dist[i][j] = tmp; // "i到j最短门路"对应的门路，通过k path[i][j] = path[i][k]; } } } } // 打印floyd最短门路的后果 cout << "floyd: " << endl; for (i = 0; i < mVexNum; i++) { for (j = 0; j < mVexNum; j++) cout << setw(2) << dist[i][j] << " "; cout << endl; }}int main(){ int prev[MAX] = {0}; int dist[MAX] = {0}; int path[MAX][MAX] = {0}; // 用于保留floyd门路 int floy[MAX][MAX] = {0}; // 用于保留floyd长度 char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; int matrix[][9] = { /*A*//*B*//*C*//*D*//*E*//*F*//*G*/ /*A*/ { 0, 12, INF, INF, INF, 16, 14}, /*B*/ { 12, 0, 10, INF, INF, 7, INF}, /*C*/ { INF, 10, 0, 3, 5, 6, INF}, /*D*/ { INF, INF, 3, 0, 4, INF, INF}, /*E*/ { INF, INF, 5, 4, 0, 2, 8}, /*F*/ { 16, 7, 6, INF, 2, 0, 9}, /*G*/ { 14, INF, INF, INF, 8, 9, 0}}; int vlen = sizeof(vexs)/sizeof(vexs[0]); MatrixUDG* pG; // 自定义"图"(输出矩阵队列) //pG = new MatrixUDG(); // 采纳已有的"图" pG = new MatrixUDG(vexs, vlen, matrix); //pG->print(); // 打印图 //pG->DFS(); // 深度优先遍历 //pG->BFS(); // 广度优先遍历 //pG->prim(0); // prim算法生成最小生成树 //pG->kruskal(); // Kruskal算法生成最小生成树 // dijkstra算法获取"第4个顶点"到其它各个顶点的最短距离 //pG->dijkstra(3, prev, dist); // floyd算法获取各个顶点之间的最短距离 pG->floyd(path, floy); return 0;}拓扑排序
简介
对一个有向无环图(Directed Acyclic Graph, DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中呈现在v之前。
通常，这样的线性序列称为满足拓扑秩序(Topological Order)的序列，简称拓扑序列。
留神:1)只有有向无环图才存在拓扑序列;
2)对于一个DAG,可能存在多个拓扑序列;
如:
该DAG的拓扑序列为 A B C D 或者 A C B D
而此有向图是不存在拓扑序列的，因为图中存在环路
1、从有向图中选取一个没有前驱（入度为0）的顶点，并输入之
2、从有向图中删去此顶点以及所有以它为尾的弧
3、反复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止
应用邻接表和一个存储入度为0的节点的栈实现
在算法中须要用定量的形容代替定性的概念
没有前驱的顶点 <==> 入度为零的顶点删除顶点及以它为尾的弧 <==> 弧头顶点的入度减1为实现拓扑排序，采纳邻接表作为有向图的存储构造，并增设一个入度数组indegree[ ]
为了防止每一次选入度为0的顶点时反复扫描入度数组，能够利用栈来存储入度为0的顶点
Code1
#include<stdio.h>#include<stdlib.h>#define m 100#define n 6#define e 8typedef struct node1 { int info; int adjvertex;//这个域就是本节点在数组中的地位 struct node1 *nextarc;} glinklistnode;//这个是在前面邻接的节点typedef struct node2 { int vertexinfo; glinklistnode *firstarc;} glinkheadnode;//邻接表的数组，vertexinfo存的是每个点的入度//数组中的节点比邻接表中的节点多了一个vertexinfo域，用来存储入度值//创立邻接链表void createAdjlist(glinkheadnode g[]) { int i,j,k; glinklistnode *p; for(i=0; i<n; i++) { g[i].vertexinfo=i; g[i].firstarc=0; }//初始化每个节点在数组中的地位 for(k=0; k<e; k++) { scanf("%d%d",&i,&j);//输出两个关联节点 p=(glinklistnode *)malloc(sizeof(glinklistnode)); p->adjvertex=j; p->nextarc=g[i].firstarc;//应用的插入方式建设，起初的更靠近根节点 g[i].firstarc=p;//第一个邻接点是p }}//拓扑排序函数void toposort(glinkheadnode g[]) { int i,v,w,sum=0, indegree[n]; struct { int s[n]; int top; } stack;//建设一个栈，栈中的s数组用来存入度为0的节点 glinklistnode *p; for (i=0; i<n; i++) indegree[i]=0;//初始化indegree数组，齐全能够应用memset for (i=0; i<n; i++) for(p=g[i].firstarc; p!=0; p=p->nextarc) //这一层for循环用来统计 indegree[p->adjvertex]++;//通过两个for循环，即可把所有节点的入度算统计进去 for(i=0,stack.top= -1; i<n; i++) if(indegree[i]==0) { stack.top++; stack.s[stack.top]=i; }//这个for循环用来入栈入度为0的节点 while(stack.top!= -1) { printf("%d\t",stack.s[stack.top]); sum=sum+1; v=stack.s[stack.top]; stack.top=stack.top-1;//出栈top p=g[v].firstarc;//读取该节点的第一个邻接点 while (p!=0) {//遍历p的所有邻接点 w=p->adjvertex; indegree[w]=indegree[w]-1;//因为前导节点会被删掉，因而它的入度值须要-1 if (indegree[w]==0) {//如果它的入度等于0，就将这个节点也入栈 stack.top=stack.top+1; stack.s[stack.top]=w; } p=p->nextarc;//往下走 } } if(sum<n) printf("The AOV network has a cycle\n");//如果最初输入的节点个数少于总结点数，阐明图中有回路}int main() { glinkheadnode g[m]; createAdjlist(g); toposort(g); return 0;}Code2
#include <iostream>#include <fstream>#include <stack>#include <cstring>using namespace std; #define MAX_VERTEX_NUM 26 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; ArcNode(){nextarc=NULL;}}ArcNode; typedef struct VNode{ int data; ArcNode *firstarc; VNode(){firstarc=NULL;}}VNode,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices; int vexnum,arcnum;}ALGraph; bool TopologicalSort(ALGraph G,int *indegree){ stack<int> s; int i,k; for(i=1;i<G.vexnum+1;i++) { if(!indegree[i]) s.push(i); } int count=0; ArcNode *p; while(!s.empty()) { i = s.top(); s.pop(); cout<<G.vertices[i].data<<"->"; count++; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k = p->adjvex; indegree[k]--; if(!indegree[k]) s.push(k); } } if(count<G.vexnum) return false; return true;} int main(){ int i; ALGraph g; cout<<"载入图中..."<<endl; ifstream fin("in.txt"); fin>>g.vexnum>>g.arcnum; for(i=1;i<g.vexnum+1;i++) g.vertices[i].data = i; int b,e; ArcNode *p; int *indegree = new int[g.vexnum+1]; //留神 int *a=new int(n); 申请一个整型变量空间，赋初值为n，并定义一个整型指针a指向该地址空间 //int *indegree=(int *)malloc(sizeof(int)*(g.vexnum+1)); memset(indegree,0,sizeof(int)*(g.vexnum+1)); for(i=1;i<g.arcnum+1;i++) { fin>>b>>e; cout<<"第"<<i<<"条边："<<b<<"->"<<e<<endl; p = new ArcNode(); p->adjvex = e; p->nextarc = g.vertices[b].firstarc; g.vertices[b].firstarc = p; indegree[e]++; } if(TopologicalSort(g,indegree)) cout<<"失常实现！"<<endl; else cout<<"该有向图有回路！"<<endl; return 0;}要害门路
概念
AOE网：在一个示意工程的带权有向图中，用顶点示意事件，用有向边示意流动，边上的权值示意流动的持续时间，称这样的有向图叫做边示意流动的网，简称AOE网。AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为起点（或汇点）。
AOE网的性质⑴ 只有在某顶点所代表的事件产生后，从该顶点登程的各流动能力开始；
⑵ 只有在进入某顶点的各流动都完结，该顶点所代表的事件能力产生。
要害门路：在AOE网中，从始点到起点具备最大门路长度（该门路上的各个流动所继续的工夫之和）的门路称为要害门路。
要害流动：要害门路上的流动称为要害流动。要害流动：e[i]=l[i]的流动
因为AOE网中的某些流动可能同时进行，故实现整个工程所必须破费的工夫应该为始点到起点的最大门路长度。要害门路长度是整个工程所需的最短工期。
与要害流动无关的量：
⑴ 事件的最早产生工夫ve[k]
ve[k]是指从始点开始到顶点vk的最大门路长度。这个长度决定了所有从顶点vk收回的流动可能动工的最早工夫。
⑵ 事件的最迟产生工夫vl[k]
vl[k]是指在不推迟整个工期的前提下,事件vk容许的最晚产生工夫。
⑶ 流动的最早开始工夫e[i]
若流动ai是由弧<vk , vj>示意，则流动ai的最早开始工夫应等于事件vk的最早产生工夫。因而，有：e[i]=ve[k]
⑷ 流动的最晚开始工夫l[i]
流动ai的最晚开始工夫是指，在不推迟整个工期的前提下， ai必须开始的最晚工夫。若ai由弧<vk，vj>示意，则ai的最晚开始工夫要保障事件vj的最迟产生工夫不拖后。因而，有：l[i]=vl[j]-len<vk, vj>
Code
#include<cstdio>#include<vector>#include<queue>#include<stack>#include<algorithm>using namespace std;const int maxn = 1000;int n;int ve[maxn], vl[maxn];struct Node{ int v, w;}node;int inDegree[maxn] = { 0 };stack<int> topOrder;vector<Node> G[maxn];vector<int> pre[maxn];bool topologicalSort(){ queue<int> q; int c = 0; for (int i = 0; i < n; i++) { if (inDegree[i] == 0) q.push(i); } while (!q.empty()) { int u = q.front(); c++; topOrder.push(u); q.pop(); for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].v, w = G[u][i].w; inDegree[v]--; if (inDegree[v] == 0) q.push(v); if (ve[u] + w > ve[v])ve[v] = ve[u] + w; } } return c == n ? true : false;}vector<int> path;void DFS(int s, int e){ if (s == e) { path.push_back(s); for (int i = path.size() - 1; i >= 0; i--) { printf("%d", path[i]); if (i > 0)printf("->"); else printf("\n"); } path.pop_back(); return; } path.push_back(e); for (int i = 0; i < pre[e].size(); i++) { DFS(s, pre[e][i]); } path.pop_back();}int criticalPath(){ fill(ve, ve + n, 0); if (!topologicalSort()) { return -1; } fill(vl, vl + n, ve[n - 1]); while (!topOrder.empty()) { int u = topOrder.top(); topOrder.pop(); for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].v, w = G[u][i].w; if (vl[v] - w < vl[u]) { vl[u] = vl[v] - w; } } } printf("所有的要害流动如下所示：\n"); for (int u = 0; u < n; u++) { for (int i = 0; i < G[u].size(); i++) { int v = G[u][i].v, w = G[u][i].w; int e = ve[u], l = vl[v] - w; if (e == l) { printf("%d->%d\n", u + 1, v + 1);//输入时加1以还原输出时做出的扭转 pre[v + 1].push_back(u + 1); } } } printf("所有的要害门路如下所示：\n"); DFS(1, n); return ve[n - 1];} int main(){ freopen("i.txt", "r", stdin);//键盘输入流重定向为i.txt文件输出流 int m; scanf("%d %d", &n,&m);//n为点数，m为边数 int a, b, w; for (int i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &w);//a、b为事件，w为ab这条边所示意的流动消耗的工夫 node.v = b-1; node.w = w; G[a-1].push_back(node);//理论存储时为了不便a、b都减1 } printf("要害门路长度为：%d\n",criticalPath()); return 0;}/*输出为（即i.txt内容）：9 111 2 61 3 41 4 52 5 13 5 14 6 25 7 95 8 76 8 47 9 28 9 4*/Kosaraju算法
强连通重量
在一个有向图中如果两个结点（结点v与结点w）在同一个环中（等价于v可通过有向门路达到w，w也能够达到v）它们两
个就是强连通的，所有互为强连通的点组成了一个汇合，在一幅有向图中这种汇合的数量就是这幅图的强连通重量的数量
思路
1、按topSort办法，失去有向图的伪topSort的序列，为什么说是伪？因为topSort是对无回环的图，而当初是对有回环的图进行雷同算法失去的后果。但不论图是否有回边，这里就用topSort排序算法，失去一个栈sortTopStack。
2、反置图G, 失去图GT
3、以第一步中的sortTopStack的弹出程序进行DFS连通树的生成，生成的所有树组成的森林即为最强连通所有分支。
算法工夫复杂度为O(V+E)
示例
对上面的图进行最大连通算法
1、按算法第一步执行后，失去sortTopStack，栈的内容
FDECBA
2、把图进行转置，后后果：
3、按DFS进行连通树的提取，终点程序按第一步栈中的弹出程序
第一步获取的栈为FDECBA ， 获取连通树的程序为 ABCEDF ,
如从A开始，连通的点为 ACBE , 则其为一个最强边通分支。
接着栈中没有最拜访到的点为FD,
从D开始，连通的点为DF , 则其为一个最强分支。
再看一个例子
1、topsort排序栈为： BAFDEC
2、图转置为
3、所有连通分支为：{C}{E}{DF}{A}{B}
从后果上看，这个办法是正确的，如何从原理上来看些算法是正确的，援用了 dm_vincent 的一段形容：（好好了解一下吧）
证实：设在图GR中，调用DFS(s)可能达到顶点v，那么顶点s和v是强连通的。
两个顶点如果是强连通的，那么彼此之间都有一条门路可达，因为DFS(s)可能达到顶点v，因而从s到v的门路必然存在。当初要害就是须要证实在GR中从v到s也是存在一条门路的，也就是要证实在G中存在s到v的一条门路。
而之所以DFS(s)可能在DFS(v)之前被调用，是因为在对G获取ReversePost-Order序列时，s呈现在v之前，这也就意味着，v是在s之前退出该序列的(因为该序列应用栈作为数据结构，先退出的反而会在序列的前面)。因而依据DFS调用的递归性质，DFS(v)应该在DFS(s)之前返回，而有两种情景满足该条件：
DFS(v) START -> DFS(v) END -> DFS(s) START -> DFS(s) END
DFS(s) START -> DFS(v) START -> DFS(v) END -> DFS(s) END
是因为而依据目前的已知条件，GR中存在一条s到v的门路，即意味着G中存在一条v到s的门路，而在第一种情景下，调用DFS(v)却没能在它返回前递归调用DFS(s)，这是和G中存在v到s的门路相矛盾的，因而不可取。故情景二为惟一合乎逻辑的调用过程。而依据DFS(s) START -> DFS(v) START能够推导出从s到v存在一条门路。
所以从s到v以及v到s都有门路可达，证实结束。
#### JavaCode
import java.util.ArrayList;import java.util.List;/*图对象 ，链接表法 */public class Digraph<T> { GraphVertex<T>[] di; int vertexNum; public Digraph(GraphVertex<T>[] di) { this.di = di; vertexNum = di.length; } public int getVertexNum(){ return vertexNum; } public List<Integer> getEdge(int v){ return di[v].edge; } public T getVertexData(int v){ return (T) di[v].date; } public Digraph<T> reverseGraph(){ GraphVertex<T>[] newDi = new GraphVertex[vertexNum]; for (int i = 0; i < vertexNum; i++) { newDi[i] = new GraphVertex<>(di[i].date); } for (int i = 0; i < vertexNum; i++) { for (Integer nextVertex:di[i].edge) { newDi[nextVertex].edge.add(i); } } return new Digraph<>(newDi); } public static class GraphVertex<T>{ T date;//数据 List<Integer> edge;//相邻结点的下标list public GraphVertex(T date) { this.date = date; edge = new ArrayList<>(); } public GraphVertex(T date, List<Integer> edge) { this.date = date; this.edge = edge; } } } import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Stack; /*Kosaraju 算法实现最强连通算法 */public class KosarajuSCC { //返回的SCC的森林,每一个元素都是一个最强通子集 public List<List<Integer>> sccLists; // visited数组，DFS实现须要用到 private boolean[] visited; // 应用栈来保留topsort的后果，因为会先收集没有出度的点，所以须要倒序，应用stack构造 private Stack<Integer> reversePost; public KosarajuSCC(Digraph di) { this.visited = new boolean[di.getVertexNum()]; this.reversePost = new Stack<Integer>(); sccLists = new ArrayList<List<Integer>>(); } /* scc算法，输入后果在sccLists中 */ public void scc(Digraph di) { //先做topSort排序 ，失去排序后的后果，存在reversePost中 topSortByDFS(di); //重置visited, 进行scc的DFS 过程 Arrays.fill(visited, false); //转置DI Digraph diT = di.reverseGraph(); //顺次对topSort的后果进行scc 的DFS while (!reversePost.empty()) { Integer v = reversePost.pop(); if (visited[v] == false) { List<Integer> sccList = new ArrayList<>(); dfsForScc(diT, v , sccList); sccLists.add(sccList); } } } private void dfsForScc(Digraph di, Integer v , List sccList) { visited[v] = true; List<Integer> edges = di.getEdge(v); for (Integer w : edges) { if (!visited[w]) { dfsForScc(di, w , sccList); } } //后续结点都解决完了，把以后结点入stack sccList.add(v); } /* 应用DFS对图进行拓扑排序 工夫复杂度 O(V+E) */ public void topSortByDFS(Digraph di) { //顺次查找所有的 for (int i = 0; i < di.getVertexNum(); i++) { if (!visited[i]) { dfsForTopsort(di, i);//顺次解决没有解决过的点 } } } public void dfsForTopsort(Digraph di, int v) { visited[v] = true; //递归解决所有的子结点（后续结点） List<Integer> edges = di.getEdge(v); for (Integer w : edges) { if (!visited[w]) { dfsForTopsort(di, w); } } //后续结点都解决完了，把以后结点入stack reversePost.push(v); } }C++Code
Kosaraju算法
- 算法思路
基本思路：
这个算法能够说是最容易了解，最通用的算法，其比拟要害的局部是同时利用了原图G和反图GT。(步骤1)先用对原图G进行深搜造成森林(树)，（步骤2）而后任选一棵树对其进行深搜(留神这次深搜节点A能往子节点B走的要求是EAB存在于反图GT)，能遍历到的顶点就是一个强连通重量。余下局部和原来的森林一起组成一个新的森林，持续步骤2直到 没有顶点为止。
改良思路：
当然，基本思路实现起来是比拟麻烦的(因为步骤2每次对一棵树进行深搜时，可能深搜到其余树上去，这是不容许的，强连通重量只能存在单棵树中(由开篇第一句话可知))，咱们当然不这么做，咱们能够奇妙的抉择第二深搜抉择的树的程序，使其不可能深搜到其余树上去。设想一下，如果步骤2是从森林里抉择树，那么哪个树是不连通(对于GT来说)到其余树上的呢？就是最初遍历进去的树，它的根节点在步骤1的遍历中来到工夫最晚，而且可知它也是该树中来到工夫最晚的那个节点。这给咱们提供了很好的抉择，在第一次深搜遍历时，记录时间i来到的顶点j，即numb[i]=j。那么，咱们每次只需找到没有找过的顶点中具备最晚来到工夫的顶点间接深搜(对于GT来说)就能够了。每次深搜都失去一个强连通重量。
暗藏性质:
剖析到这里，咱们曾经晓得怎么求强连通重量了。然而，大家有没有留神到咱们在第二次深搜抉择树的程序有一个特点呢？如果在看上述思路的时候，你的脑子在思考，置信你曾经晓得了！！！它就是：如果咱们把求进去的每个强连通重量膨胀成一个点，并且用求出每个强连通重量的程序来标记膨胀后的节点，那么这个程序其实就是强连通重量膨胀成点后造成的有向无环图的拓扑序列。为什么呢？首先，应该明确搜寻后的图肯定是有向无环图呢？废话，如果还有环，那么环上的顶点对应的所有原来图上的顶点形成一个强连通重量，而不是形成环上那么多点对应的单独的强连通重量了。而后就是为什么是拓扑序列，咱们在改良剖析的时候，不是先选的树不会连通到其余树上（对于反图GT来说），也就是后选的树没有连通到先选的树，也即先呈现的强连通重量膨胀的点只能指向后呈现的强连通重量膨胀的点。那么拓扑序列不是天经地义的吗？这就是Kosaraju算法的一个暗藏性质。
算法思路：
找到一个正当程序，使得咱们只须要依照这个程序进行DFS遍历，那么每一次的DFS就能够使咱们失去一个强连通重量（SCC）
若遍历程序由B中顶点开始，则需通过两个DFS遍历，可顺利找到A和B两个SCC，
若从A中顶点开始，则只通过一次DFS遍历，无奈找到两个SCC
因而要害是如何让DFS以正确的程序开始遍历（即由B开始）
由图可知：
不论从A开始DFS，还是从B开始DFS，因为A到B有一条边，所以最初退出DFS的点肯定在A上，若选最初退出DFS的点为始点（位于A中）并对上图的 反图 进行一次DFS，则能够失去图中的两个SCC。
由此失去以下算法步骤：
对有向图G做DFS（第一次），按退出DFS函数的程序（B先退出，A后退出）将顶点退出数组finished[]中（此时深度大的顶点（B）在前，深度小的顶点（A）在后）
求G的反图Gr
对反图Gr按finished数组中从后到前的程序做DFS（第二次），遍历完结便可失去有向图中的所有SCC
#include<bits/stdc++.h>using namespace std;const int maxn=1e6+5;struct edge{ int to,next;}edge1[maxn],edge2[maxn];//edge1是原图，edge2是逆图int head1[maxn],head2[maxn];bool mark1[maxn],mark2[maxn];int tot1,tot2;int cnt1,cnt2;int st[maxn];//对原图进行dfs，点的完结程序从小到大排列。int belong[maxn];//每个点属于哪个联通重量int num;//每个联通重量的个数int setnum[maxn];//每个联通重量中点的个数 void addedge(int u,int v){ edge1[tot1].to=v;edge1[tot1].next=head1[u];head1[u]=tot1++; edge2[tot2].to=u;edge2[tot2].next=head2[v];head2[v]=tot2++;} void dfs1(int u){ mark1[u]=true; for(int i=head1[u];i!=-1;i=edge1[i].next) if(!mark1[edge1[i].to]) dfs1(edge1[i].to); st[cnt1++]=u;}void dfs2(int u){ mark2[u]=true; num++; belong[u]=cnt2; for(int i=head2[u];i!=-1;i=edge2[i].next) if(!mark2[edge2[i].to]) dfs2(edge2[i].to);}void solve(int n){//点编号从1开始 memset(mark1,false,sizeof(mark1)); memset(mark2,false,sizeof(mark2)); cnt1=cnt2=0; for(int i=1;i<=n;i++) if(!mark1[i]) dfs1(i); for(int i=cnt1-1;i>=0;i--) if(!mark2[st[i]]){ num=0; dfs2(st[i]); setnum[cnt2++]=num; }}int main(){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int s,d; cin>>s>>d; addedge(s,d); } solve(1); return 0;} 高级搜寻
迭代加深（例题）
Addition Chains
已知一个数列 （其中 ）。对于每个 ，须要满足 （，这里 与 能够相等）。现给定 的值，要求 的最小值（并不要求输入），及这个数列每一项的值（可能存在多个数列，只输入任一个满足条件的就能够了）。
输出格局
多组数据，每行给定一个正整数 。
输出以 完结。
输入格局
对于每组数据，输入满足条件的长度最小的数列。
样例
样例输出
5
7
12
15
77
0
样例输入1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
n 小于等于 100
思路
一拿到这道好题，就能够晓得，搜寻！那该怎么搜？爆搜？非也，就要用到迭代加深
他既要搜寻又要深度小，那么就用迭代加深，限度一个深度，如果不行，限度放大，一次一次的进行搜寻
首先初始化 a[1] = 1 , a[2] = 2 , 而后要让一个 a[x] = a[i] + a[j] ，且最初一项为 n，项数又要最小
先用贪婪思维，要最小，每一个 a[i] 都为前一个数两倍，求出贪婪的最小长度
while( a[1] < n ) { a[1] *= 2 ; len ++ ;}而后就缓缓地进行搜寻...
每一次在以后层搜寻正解，如果不行，长度减少
for( len ; ; ++ len ) { dfs( 1 ); if( flag ) break;}最初就是搜寻局部咱们晓得，要让这个序列成立，那么这个就须要是递增的，即 a[dep+1] > a[dep] ，那么搜寻枚举 a[dep+1] 时，必须保障 a[i] + a[j] > a[dep] ，且 a[dep+1] 后的最初项的最大值不能小于 n
Code
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>using namespace std; int n , a[10007] , len ;bool flag ; void dfs( int dep ) { if( dep > len ) return ; if( dep == len && a[dep] == n ) {//找到解 for(int i = 1 ; i <= dep ; ++ i ) printf("%d ", a[i] ); printf("\n"); flag = 1 ; return ; } for(int i = dep ; i >= 1 ; -- i ) {//枚举 a[dep+1] 的组成 for(int j = dep ; j >= i ; -- j ) { if( a[i]+a[j] > a[dep] && a[i]+a[j] <= n ) {//是否成立 a[dep+1] = a[i]+a[j] ; int x = a[dep+1] ; for(int k = dep+2 ; k <= len ; ++ k )//最初一项的最大值 x *= 2 ; if( x < n )//剪枝 continue ; dfs( dep+1 ); if( flag ) return ; } } }} int main(){ while( scanf("%d", &n ) != EOF ) { len = 1 ; memset( a , 0 , sizeof( a ) ); a[1] = 1 ; a[2] = 2 ; if( n == 0 ) break; int x = 1 ; while( x < n ) {//最小的长度 x *= 2 ; len ++ ; } for( len ; ; ++ len ) {//迭代加深 dfs( 1 ); if( flag ) break; } flag = 0 ; } return 0;}双向BFS
题目粗心：给定一个终点和一个起点，按骑士的走法（走日字），从终点到起点的起码挪动多少次
剖析
其实其和BFS并没有多大差异，只是它用了两个队列，而其外围局部为1和2的标记，利用标记来判断其是否相交，所有color数组为其可能双向的外围局部，其次visit数组用来记录步数，也是其相连的要害！
综上：要分外留神visit[]和color[]这两个数组，，这是其外围
Code
#include <iostream>#include <cstdio>#include <cstring>#include <queue>using namespace std; struct knight{ int x,y,step;}; int dir[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};int sx, sy, ex, ey;int visit[8][8];int color[8][8];int bfs(); int main(){ int x1, x2; char y1, y2; while(scanf("%c%d %c%d", &y1, &x1, &y2, &x2) != EOF) { getchar(); sx = x1 - 1; sy = y1 - 'a'; ex = x2 - 1; ey = y2 - 'a'; memset(visit, -1, sizeof(visit)); memset(color, 0, sizeof(color)); int cost = bfs(); printf("To get from %c%d to %c%d takes %d knight moves.\n", y1, x1, y2, x2, cost); } return 0;} int bfs(){ if(sx == ex && sy == ey) return 0; queue<knight> que_front;//创立队列 queue<knight> que_back; knight front, back;//构造体 front.x = sx; front.y = sy; front.step = 0;//赋初值 back.x = ex; back.y = ey; back.step = 1; que_front.push(front);//进队列 que_back.push(back);//进队列 visit[sx][sy] = 0; visit[ex][ey] = 1; //由这两个来辨别这两个队列 color[sx][sy] = 1; color[ex][ey] = 2; int ans1 = 0, ans2 = 0; while(!que_front.empty() || !que_back.empty())//当两个队列都为空时退出 { if(!que_front.empty())//队列不空 { front = que_front.front();//构造体赋值 que_front.pop();//出队列 for(int i = 0; i < 8; i++) { int dx = front.x + dir[i][0]; int dy = front.y + dir[i][1]; if(dx >= 0 && dx < 8 && dy >= 0 && dy < 8 && color[dx][dy] != 1)//判断是否被队列1走过 { if(color[dx][dy] == 0) { knight tmp;//建设新构造体，并赋值 tmp.x = dx; tmp.y = dy; tmp.step = front.step + 1; visit[dx][dy] = tmp.step;//记录相应步数 color[dx][dy] = 1;//赋队列1的标记值 que_front.push(tmp);//进队列 } else //即不等于1也不等于0 则必定是等于2，所以两个相交 return front.step + visit[dx][dy]; } } } if(!que_back.empty())//第二个和第一个同理 { back = que_back.front(); que_back.pop(); for(int i = 0; i < 8; i++) { int dx = back.x + dir[i][0]; int dy = back.y + dir[i][1]; if(dx >= 0 && dx < 8 && dy >= 0 && dy < 8 && color[dx][dy] != 2) { if(color[dx][dy] == 0) { knight tmp; tmp.x = dx; tmp.y = dy; tmp.step = back.step + 1; visit[dx][dy] = tmp.step; color[dx][dy] = 2; que_back.push(tmp); } else return back.step + visit[dx][dy]; } } } } return -1;//没有门路相通，则返回-1 }概念
如果指标也已知的话，用双向BFS能很大进步速度
单向时，是 b^len的扩大。
双向的话，2*b^(len/2) 快了很多，特地是分支因子b较大时
至于实现上，网上有些做法是用两个队列，交替节点搜寻 ×，如上面的伪代码：
while(!empty()){
扩大正向一个节点
遇到反向曾经扩大的return
扩大反向一个节点
遇到正向曾经扩大的return
}
但这种做法是有问题的，如上面的图：
求S-T的最短路，交替节点搜寻（一次正向节点，一次反向节点）时
Step 1 : S –> 1 , 2
Step 2 : T –> 3 , 4
Step 3 : 1 –> 5
Step 4 : 3 –> 5 返回最短路为4，谬误的，事实是3，S-2-4-T
我想，正确做法的是交替逐层搜寻，保障了不会先遇到非最优解就跳出，而是查看完该层所有节点，失去最优值。
也即如果该层搜寻遇到了对方曾经拜访过的，那么曾经搜寻过的层数就是答案了，能够跳出了，当前不会更优的了。
当某一边队列空时就无解了。
优化：提供速度的关键在于使状态扩大得少一些，所以优先选择队列长度较少的去扩大，放弃两边队列长度均衡。这比拟适宜于两边的扩大状况不同时，一边扩大得快，一边扩大得慢。如果两边扩大状况一样时，加了后成果不大，不过加了也没事。
无向图时，两边扩大状况相似。有向图时，留神反向的扩大是反过来的 x->y（如NOIP2002G2字串变换）
Code
void gao(vector<int> &from , vector<int> &to , Hash &hash){ to.clear(); for(vector<int>::iterator it = from.begin() ; it != from.end() ; it++){ 利用hash判重，扩大*it }}int bibfs(int start , int dest){ if(start == dest){ //留神要先判相等 return 0; } Hash bfs , rbfs; bfs[start] = 0; rbfs[dest] = 0; vector<int> Q[2] , rQ[2]; //用vector做队列，不便遍历 int cur = 0 , rcur = 0; Q[cur].push_back(start); rQ[rcur].push_back(dest); for(int step = 1 ; step <= limit && !Q[cur].empty() && !rQ[rcur].empty(); step++){ //cout<<step<<endl; if(Q[cur].size() <= rQ[rcur].size()){//优先扩大队列长度小的 gao(Q[cur],Q[cur^1],bfs); cur ^= 1; for(vector<int>::iterator it = Q[cur].begin() ; it != Q[cur].end() ; it++){ if(rbfs.find(*it) != rbfs.end()){ return step; } } }else{ gao(rQ[rcur],rQ[rcur^1],bfs); rcur ^= 1; for(vector<int>::iterator it = rQ[rcur].begin() ; it != rQ[rcur].end() ; it++){ if(bfs.find(*it) != bfs.end()){ return step; } } } } return -1;}例题Poj 3131
/* 如图所示，问从初始状态变动到指标状态，不超过步 规模比拟大 状态总数为：*6^8 1个为E，其余格子每个种可能 我这里用了enum，这样编码会直观点吧 用二进制编码，每三位bit代表一个格子 状态很多，要用双向BFS，优先选择队列长度小的扩大，否则会超时 还有留神判重时，用了Hash，节点要用动态数组！！！ 之前每次都make_pair()就超时了！！！ map判重也超时了*/enum Board {RBW, BRW, RWB, WRB, BWR, WBR, E};//0,1,const int MAXN = 500007;struct Node{ int pos; short val; Node *next;};Node nodes[MAXN*20] , *pN;struct Hash{ Node* hash[MAXN]; vector<int> vt; void init(){ for(vector<int>::iterator it = vt.begin() ; it != vt.end() ; it++){ hash[*it] = NULL; } vt.clear(); } void add(int pos , short val){ int mod = pos % MAXN; if(hash[mod] == NULL){ vt.push_back(mod); } pN->pos = pos; pN->val = val; pN->next = hash[mod]; hash[mod] = pN++; //assert(pN < nodes + MAXN*20); } short find(int pos){ int loc = pos % MAXN; Node *p = hash[loc]; while(p != NULL ){ if(p->pos == pos){ return p->val; } p = p->next; } return -1; }};Hash bfs , rbfs;int bin[10];int dx[] = {1,0,-1,0};int dy[] = {0,1,0,-1};Board change[6][4] = { {RWB, WBR, RWB, WBR}, {BWR, WRB, BWR, WRB}, {RBW, BWR, RBW, BWR}, {WBR, BRW, WBR, BRW}, {BRW, RWB, BRW, RWB}, {WRB, RBW, WRB, RBW}};#define iset(val,pos,x) (val ^= val & bin[pos] , val |= x << 3*(pos) )#define get(val,pos) ((val >> 3*(pos) ) & 7)inline bool out(int x , int y){ return x < 0 || x >= 3 || y < 0 || y >= 3;}void gao(vector<int> &from , vector<int> &to , Hash &hash){ to.clear(); for(vector<int>::iterator it = from.begin() ; it != from.end() ; it++){ int &board = *it; int pos , x , y , step = hash.find(board); for(int i = 0 ;i < 9 ; i++){ if(get(board,i) == E){ pos = i; y = i / 3; x = i % 3; break; } } for(int k = 0 ; k < 4 ; k ++){ int xx = x + dx[k]; int yy = y + dy[k]; if(out(xx,yy)){ continue; } int next = board; int nextPos = yy * 3 + xx , val = get(next, nextPos); iset(next,pos,change[val][k]); iset(next,nextPos,E); if(hash.find(next) == -1){ hash.add(next,step+1); to.push_back(next); } } }}int bibfs(int &start , int dest[2]){ vector<int> Q[2] , rQ[2]; int cur = 0 , rcur = 0; pN = nodes; bfs.init(); rbfs.init(); bfs.add(start,0); Q[cur].push_back(start); int pos = 0; while(get(dest[0], pos) != E){ pos++; } for(int mask = 0 ; mask < (1<<9) ; mask++){ if((mask>>pos) & 1){ continue; } int next = 0;//init 0 !!! for(int i = 0 ;i < 9 ; i ++){ iset(next, i, get(dest[(mask>>i)&1], i) ); } if(next == start){ return 0; } rbfs.add(next,0); rQ[rcur].push_back(next); } for(int step = 1 ; step <= 30 ; step++){ if(Q[cur].size() <= rQ[rcur].size()){// gao(Q[cur],Q[cur^1],bfs); cur ^= 1; for(vector<int>::iterator it = Q[cur].begin() ; it != Q[cur].end() ; it++){ if(rbfs.find(*it) != -1){ return step; } } }else{ gao(rQ[rcur],rQ[rcur^1],rbfs); rcur ^= 1; for(vector<int>::iterator it = rQ[rcur].begin() ; it != rQ[rcur].end() ; it++){ if(bfs.find(*it) != -1){ return step; } } } } return -1;} int main(){ //freopen("in","r",stdin); //freopen("out","w",stdout); bin[0] = 7; for(int pos = 1 ; pos < 9 ; pos++){ bin[pos] = bin[pos-1]<<3; } for(int x,y;scanf("%d%d",&x,&y) , x != 0;){ x--; y--; int dest[2] , start = 0; for(int i = 0; i < 3 ; i ++){ for(int j = 0 ; j < 3 ; j++){ char ch; scanf(" %c",&ch); if(ch == 'W'){ iset(dest[0],3*i+j,RBW); iset(dest[1],3*i+j,BRW); }else if(ch == 'B'){ iset(dest[0],3*i+j,RWB); iset(dest[1],3*i+j,WRB); }else if(ch == 'R'){ iset(dest[0],3*i+j,BWR); iset(dest[1],3*i+j,WBR); }else{ iset(dest[0],3*i+j,E); iset(dest[1],3*i+j,E); } } } iset(start, 3*y+x, E); cout<<bibfs(start , dest)<<endl; } return 0;}参考文献
自己图论根本拉胯，所以只能总结一些大佬的思路和Code。
https://blog.csdn.net/shuiyix...
https://www.cnblogs.com/ECJTU...
https://blog.csdn.net/KLFTESP...
https://blog.csdn.net/s634772...
https://blog.csdn.net/s634772...
https://blog.csdn.net/qq_3815...
https://blog.csdn.net/weixin_...
https://blog.csdn.net/m0_4826...
https://blog.csdn.net/cliukai...
https://blog.csdn.net/qq_4175...
https://www.cnblogs.com/skywa...
https://blog.csdn.net/ywcpig/...
https://blog.csdn.net/zuochao...
https://blog.csdn.net/tony820...
https://blog.csdn.net/mlm5678...
https://blog.csdn.net/chudong...
http://www.cppblog.com/Yuan/a...