共计 71933 个字符，预计需要花费 180 分钟才能阅读完成。
图基本概念
图的定义
图 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 10
typedef 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 0
typedef 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 0
typedef 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 100
typedef 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 8
typedef 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 11
1 2 6
1 3 4
1 4 5
2 5 1
3 5 1
4 6 2
5 7 9
5 8 7
6 8 4
7 9 2
8 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…
正文完