11.1 图的邻接矩阵
#include<iostream>
using namespace std;
/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
bool visited[MVNum];//定义标志数组
typedef struct {
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
int i;
for (int i = 0; i < G.vexnum; i++)
if (u == G.vexs[i]) return i;
return -1;
}
/*--------打印图的邻接矩阵-----------*/
void PrintfAMGraph(AMGraph G) {
//将图的邻接矩阵输出在控制台上
for (int i = 0; i < G.vexnum; i++) {
cout << "v" << i + 1 << ":";
for (int j = 0; j < G.vexnum; j++)
cout << G.arcs[i][j] << " ";
cout << endl;
}
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
//采用邻接矩阵表示法，创建无向网
int i = 0, j = 0, k = 0;
cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
for ( i = 0; i < G.vexnum; i++)//依次输入点的信息
cin >> G.vexs[i];
for ( i = 0; i < G.vexnum; i++)//初始化邻接矩阵
for ( j = 0; j < G.vexnum; j++)
G.arcs[i][j] = 0;
for ( k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;//定义两个顶点v1,v2
cin >> v1 >> v2 ;
i = LocateVex(G, v1);
j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
G.arcs[i][j] = G.arcs[j][i] = 1;
}
}
/*-----------主函数-----------*/
int main() {
AMGraph G;
CreateUDN(G);
PrintfAMGraph(G);
return 0;
}
11.2 图的邻接表
#include<iostream>
#include<string>
using namespace std;
/*--------图的邻接表存储表示----------*/
#define MVNum 100//最大顶点数
#define OK 1
typedef int OtherInfo;
typedef string VerTexType;
typedef int Status;
typedef struct ArcNode {//边结点
int adjvex;//该边所指向的顶点位置
struct ArcNode* nextarc;//指向下一条边的指针
OtherInfo info;//和边相关的信息
}ArcNode;
typedef struct VNode {//顶点信息
VerTexType data;
ArcNode* firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];
typedef struct {
AdjList vertices;
int vexnum, arcnum;//图的当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph G,VerTexType v1) {//返回传入结点在图中的位置下标
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == v1)
return i;
}
return -1;
}
Status CreateUDG(ALGraph& G) {
//采用邻接表表示法，创建无向图G
cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
for (int i = 0; i < G.vexnum; i++) {
//输入各点，构造表头结点表
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
}
for (int k = 0; k < G.arcnum; k++) {
//输入各边，构造邻接表
VerTexType v1, v2;
cin >> v1 >> v2;//输入一条边依附的两个顶点
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点在G.vertices中的序号
ArcNode* p1 = new ArcNode;//生成新的一个边结点*p1
p1->adjvex = j;//邻接点序号为j
p1->nextarc = G.vertices[i].firstarc;//采用头插法
G.vertices[i].firstarc = p1;//将新结点*p1插入顶点vi的边表头部
ArcNode* p2 = new ArcNode;//生成新的一个边结点*p2
p2->adjvex = i;//邻接点序号为i
p2->nextarc = G.vertices[j].firstarc;//采用头插法
G.vertices[j].firstarc = p2;//将新结点*p2插入顶点vj的边表头部
}
return OK;
}
/*--------将邻接表输出在控制台上---------*/
void PrintfALGraph(ALGraph G) {
for (int i = 0; i < G.vexnum; i++) {
cout << G.vertices[i].data << "：";
ArcNode* p = new ArcNode;//生成一个边指针
p = G.vertices[i].firstarc;//边指针指向第一个边结点
while (p!=NULL) {//当边指针不为空时，即指针未遍历完
cout << p->adjvex << " ";
p = p->nextarc;//边指针继续遍历邻接表
}
cout << endl;
}
}
/*----------主函数-----------*/
int main() {
ALGraph G;
CreateUDG(G);
PrintfALGraph(G);
return 0;
}
11.3 广度优先搜索遍历 (BFS)
#include<iostream>
#include<string>
using namespace std;
//#define OK 1
#define ERROR 0
#define MAXQSIZE 100
#define MVNum 100
typedef int Status;
typedef string VexType;
typedef int QElemType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode* NextAdj;
}ArcNode;
typedef struct VNode
{
VexType data;
ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph;
typedef struct
{
QElemType* base;
int q_front;
int q_rear;
}SqQueue;
Status InitQueue(SqQueue& Q)
{
Q.base=new QElemType[MAXQSIZE];
Q.q_front=Q.q_rear=0;
return 1;
}
Status EnQueue(SqQueue& Q,QElemType e)
{
if((Q.q_rear+1)%MAXQSIZE==Q.q_front)
return ERROR;
Q.base[Q.q_rear]=e;
Q.q_rear=(Q.q_rear+1)%MAXQSIZE;
return 1;
}
Status DeQueue(SqQueue& Q,QElemType& e)
{
if(Q.q_front==Q.q_rear) return ERROR;
e=Q.base[Q.q_front];
Q.q_front=(Q.q_front+1)%MAXQSIZE;
return 1;
}
Status QueueEmpty(SqQueue& Q)
{
if(Q.q_front==Q.q_rear) return 1;
return ERROR;
}
int LocateVex(ALGraph G,VexType v)
{
for(int i=0;i<G.vexnum;i++)
{
if(v==G.vertices[i].data) return i;
}
return -1;
}
int CreateUDG(ALGraph& G)
{
cin>>G.vexnum>>G.arcnum;//输入顶点数和边数
for(int i=0;i<G.vexnum;i++)//初始化顶点表，将顶点的数据域赋值并将其指针域置空
{
cin>>G.vertices[i].data;//数据域赋值
G.vertices[i].firstarc=NULL;//指针域置空
}
for(int k=0;k<G.arcnum;k++)
{
VexType v1,v2;
cin>>v1>>v2;//输入依附于一条边的两个顶点
int i=LocateVex(G,v1);//找到v1的位置
int j=LocateVex(G,v2);//找到v2的位置
ArcNode* p1=new ArcNode;//定义指向第一个边结点的指针
p1->NextAdj=G.vertices[i].firstarc;//指针指向第一个边结点
G.vertices[i].firstarc=p1;
p1->adjvex=j;
ArcNode* p2=new ArcNode;
p2->NextAdj=G.vertices[j].firstarc;
p2->adjvex=i;
G.vertices[j].firstarc=p2;
}
return 1;
}
Status GetTop(SqQueue Q)
{
if(Q.q_front!=Q.q_rear)
return Q.base[Q.q_front];
}
/*-------采用邻接表表示广度优先搜素遍历------*/
bool visited[MVNum];
void BFS_AL(ALGraph G,int v)
{
cout<<G.vertices[v].data<<" ";//输出顶点数据域
visited[v]=true;//将该结点的访问数组单位值赋为true
SqQueue Q;
InitQueue(Q);//定义并初始化队列
EnQueue(Q,v);//将该顶点进队
ArcNode* w=new ArcNode;//定义指向边结点的指针
while(Q.q_front!=Q.q_rear)
{
int u=0;//定义接收出队元素的变量
DeQueue(Q,u);//出队
w=G.vertices[u].firstarc;//令指针指向顶点的第一个边结点
while(w!=NULL)
{
if(!visited[w->adjvex])//某边结点的访问数组的单位值为false
{
cout<<G.vertices[w->adjvex].data<<" ";//输出边结点数据域值
visited[w->adjvex]=true;//将边结点数据域所在顶点的访问数组单位值赋为true
EnQueue(Q,w->adjvex);//将边结点所表示的顶点进队
}
w=w->NextAdj;//将指针指向下一个边结点，直到指向最后一个结点将其赋值为空，循环结束
}
}
}
int main()
{
ALGraph G;
CreateUDG(G);
int v=0;
BFS_AL(G,v);
return 0;
}
11.4 深度优先搜索遍历（DFS）
#include<iostream>
#include<string>
using namespace std;
#define OK 1
#define MaxInt 32767//无穷大
#define MVNum 100//最大顶点数
typedef string VerTexType;//假设顶点的数据类型为字符串
typedef int ArcType;//假设边的权值类型为整型
/*---------图的邻接矩阵---------*/
typedef struct {
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum, arcnum;//图的顶点数和边数
}Graph;
/*--------确定顶点在图中的位置--------*/
int LocateVex(Graph G, VerTexType V) {
//确定V在G中的位置
for (int i = 0; i < G.vexnum; i++) {
if (G.vexs[i] == V) return i;
}
return -1;//未找到指定结点
}
/*--------返回顶点的第一个邻接点编号-------*/
int FirstAdjVex(Graph G, int v) {
//返回v的第一个邻接表编号，没有则返回-1
for (int i = 0; i < G.vexnum; i++) {
if (G.arcs[v][i] == 1)//邻接表该处为1，表明形参结点和i号结点之间有边
return i;
}
return -1;
}
/*---------返回v相对于w的下个邻接点--------*/
int NextAdjVex(Graph& G, int v, int w) {
//返回v相对于w的下一个邻接点，没有则返回-1
for (int i = w + 1; i < G.vexnum; i++) {
if (G.arcs[v][i] == 1)
return i;
}
return -1;
}
/*采用邻接矩阵表示法创建无向图*/
int CreateUDG(Graph& G) {
cin >> G.vexnum >> G.arcnum;
for (int i = 0; i < G.vexnum; i++) {//输入各顶点信息
cin >> G.vexs[i];
}
for (int i = 0; i < G.vexnum; i++)
for (int j = 0; j < G.vexnum; j++)
G.arcs[i][j] = 0;//将边结点表都初始化为0
for (int k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;
cin >> v1 >> v2;//输入相连通的两个结点
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);//找到两个结点的位置
G.arcs[i][j] = G.arcs[j][i] = 1;
//G.arcs[i][j] = 1;
}
return OK;
}
bool visited[MVNum];//访问标志数组，其初值为"false"
/*----------深度优先搜索遍历连通图--------*/
void DFS(Graph G, int v) {
//从第v个顶点出发递归地深度优先遍历图G
cout << G.vexs[v] << " "; visited[v] = true;//访问第v个顶点，并置访问标志数组相应分量值为true
for (int w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
//依次检查v的所有邻接点w,FirstAdjVex(G,v)表示v的第一个邻接点
//NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w>=0表示存在邻接点
if (!visited[w]) DFS(G, w);//对v的尚未访问的邻接顶点w递归调用DFS
}
}
/*----------深度优先搜索遍历非连通图---------*/
void DFSTraverse(Graph G) {
//对非连通图G，做深度优先遍历
for (int i = 0; i < G.vexnum; i++)
visited[i] = false;//访问标志数组初始化
for (int i = 0; i < G.vexnum; i++)
if (!visited[i]) DFS(G, i);//对尚未访问的顶点调用DFS
}
/*----------主函数----------*/
int main()
{
Graph G;
CreateUDG(G);
int v = 0;
DFS(G, v);
//DFSTraverse(G);
return 0;
}
11.5最小生成树之Prim算法
#include<iostream>
#include<string>
using namespace std;
#define MVNum 100
#define MAXInt 32767//定义无穷大
typedef string VerTexType;
typedef int ArcType;
/*----------图的邻接矩阵表示法存储结构---------*/
typedef struct {
int arcnum, vexnum;//顶点数和边数
VerTexType vex[MVNum];//定义存储顶点的数组
ArcType arcs[MVNum][MVNum];//定义存储边的数组
}AMGraph;
/*-------辅助数组的定义，用来记录从顶点集U到V-U的权值最小的边-------*/
typedef struct
{
VerTexType adjvex;//最小边在U中的那个顶点
ArcType lowcost;//最小边上的权值
}MinEdge;
MinEdge closedge[MVNum];
/*----------在顶点表中找到传入顶点的位置---------*/
int LocateVex(AMGraph G, VerTexType v) {
//遍历顶点表，返回某顶点在顶点表中的位置下标
for (int i = 0; i < G.vexnum; i++) {
if (G.vex[i] == v)//在顶点表中找到了顶点v
return i;//返回其下标
}
return -1;//没找到返回-1
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
//采用邻接矩阵表示法，创建无向网
int i = 0, j = 0, k = 0, w;
cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
for (i = 0; i < G.vexnum; i++)//依次输入点的信息
cin >> G.vex[i];
for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
for (j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MAXInt;
for (k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;//定义两个顶点v1,v2
cin >> v1 >> v2 >> w;
i = LocateVex(G, v1);
j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
G.arcs[i][j] = G.arcs[j][i] = w;
}
}
/*--------在辅助数组中找到lowcost最小的顶点-------*/
int Min(MinEdge closedge[],int size) {
//取最小权值边的顶点位置
int k = -1;//最后接收最小权值邻接点的下标
for (int i = 0; i < size; i++) {
if (closedge[i].lowcost > 0) {//i号顶点并未被归入到生成树中
int min = closedge[i].lowcost;//设置min中间变量存放最小权值
for (int j = i; j < size; j++) {
if (closedge[j].lowcost > 0 && min >= closedge[j].lowcost) {
min = closedge[j].lowcost;
k = j;
}
}
break;
}
}
return k;
}
/*------------构造最小生成树的Prim算法----------*/
void MiniSpanTree_Prim(AMGraph G, VerTexType u) {
//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边
int k = LocateVex(G, u);//k为顶点u的下标
for (int j = 0; j < G.vexnum; j++) {
//对V-U的每一个顶点vj，初始化closedge[j]
closedge[j].adjvex = u;//{adjvex,lowcost}
closedge[j].lowcost = G.arcs[k][j];
}
closedge[k].lowcost = 0;//初始,U={u}
for (int i = 1; i < G.vexnum; i++) {
//选择其余n-1个结点，生成n-1条边（n=G.vexnum）
int k = Min(closedge,G.vexnum);
//求出T的下一个结点；第k个顶点,closedge[k]中存有当前最小边
ArcType u0 = closedge[k].lowcost;//u0为最小边的一个顶点,u0属于u
VerTexType v0 = G.vex[k];//v0为最小边的另一个顶点，v0属于V-U
cout << u0 << " " << v0 << endl;//输出当前的最小边(u0,v0);
closedge[k].lowcost = 0;//第k个顶点并入U集
for (int j = 0; j < G.vexnum; j++) {
if (G.arcs[k][j] < closedge[j].lowcost)//新顶点并入U后重新选择最小边
{
closedge[j].adjvex = G.vex[k];
closedge[j].lowcost = G.arcs[k][j];
}
}
}
}
int main() {
AMGraph G;
CreateUDN(G);
int v = 0;
MiniSpanTree_Prim(G,G.vex[v]);
return 0;
}
11.6 最小生成树之Kruskal算法
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MVNum 100
#define MAXInt 32767//定义无穷大
typedef string VerTexType;
typedef int ArcType;
/*----------图的邻接矩阵表示法存储结构---------*/
typedef struct {
int arcnum, vexnum;//顶点数和边数
VerTexType vex[MVNum];//定义存储顶点的数组
ArcType arcs[MVNum][MVNum];//定义存储边的数组
}AMGraph;
/*-----------辅助数组Edges的定义--------------*/
typedef struct edge{
VerTexType Head;//边的始点
VerTexType Tail;//边的终点
ArcType lowcost;//边上的权值
}Edgea;
Edgea Edge[MVNum];
/*---------辅助数组Vexset的定义------------*/
int Vexset[MVNum];
/*----------在顶点表中找到传入顶点的位置---------*/
int LocateVex(AMGraph G, VerTexType v) {
//遍历顶点表，返回某顶点在顶点表中的位置下标
for (int i = 0; i < G.vexnum; i++) {
if (G.vex[i] == v)//在顶点表中找到了顶点v
return i;//返回其下标
}
return -1;//没找到返回-1
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
//采用邻接矩阵表示法，创建无向网
int i = 0, j = 0, k = 0, w;
cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
for (i = 0; i < G.vexnum; i++)//依次输入点的信息
cin >> G.vex[i];
for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
for (j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MAXInt;
for (k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;//定义两个顶点v1,v2
cin >> v1 >> v2 >> w;
i = LocateVex(G, v1);
j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
G.arcs[i][j] = G.arcs[j][i] = w;
Edge[k].Head = v1;
Edge[k].Tail = v2;
Edge[k].lowcost = w;
}
}
/*-----获取图的边数---------*/
int getArcnum(int n) {//获取图的边数
return n;
}
bool cmd(edge a,edge b) {
return a.lowcost < b.lowcost;
}
/*----------Kruskal算法的代码实现----------*/
void MiniSpanTree_Kruskal(AMGraph& G) {
//无向网G以邻接矩阵形式存储，构造G的最小生成树T，输出T的各条边
sort(Edge, Edge + G.arcnum, cmd);//将数组Edge中的元素按权值从小到大排序
int sum = 0;
for (int i = 0; i < G.vexnum; i++)//辅助数组，表示各顶点自成一个连通分量
Vexset[i] = i;
for (int i = 0; i < G.arcnum; i++) {//依次查看数组Edge中的边
int v1, v2 = 0;
v1 = LocateVex(G, Edge[i].Head);//v1为边的始点Head的下标
v2 = LocateVex(G, Edge[i].Tail);//v2为边的终点Tail的下标
int vs1, vs2 = 0;
vs1 = Vexset[v1];//获取边Edge[i]的始点所在的连通分量vs1
vs2 = Vexset[v2];//获取边Edge[i]的终点所在的连通分量vs2
if (vs1 != vs2) {//边的两个顶点分属不同的连通分量
cout << Edge[i].Head <<" "<< Edge[i].Tail <<" "<< Edge[i].lowcost << endl;//输出此边
for (int j = 0; j < G.vexnum; j++) {//合并vs1和vs2两个分量，即两个集合统一编号
if (Vexset[j] == vs2) Vexset[j] = vs1;//集合编号为vs2的都改成vs1
}
}
}
}
int main() {
AMGraph G;
CreateUDN(G);
MiniSpanTree_Kruskal(G);
return 0;
}
11.7 最短路径之Dijkstra算法
#include<iostream>
using namespace std;
/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define MaxInt 32767//无穷大
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
bool visited[MVNum];//定义标志数组
typedef struct {
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
/*-----------迪杰斯特拉算法辅助数组的建立----------*/
bool S[MVNum];
int Path[MVNum];
int D[MVNum];
/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
int i;
for (int i = 0; i < G.vexnum; i++)
if (u == G.vexs[i]) return i;
return -1;
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
//采用邻接矩阵表示法，创建无向网
int i = 0, j = 0, k = 0;
cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
for (i = 0; i < G.vexnum; i++)//依次输入点的信息
cin >> G.vexs[i];
for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
for (j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MaxInt;
for (k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;//定义两个顶点v1,v2
int w = 0;
cin >> v1 >> v2 >> w;
i = LocateVex(G, v1);
j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
G.arcs[i][j] = w;
}
}
/*-----------最短路径之迪杰斯特拉算法------------*/
void ShortestPath_DIJ(AMGraph G, int v0) {
//用Dijkstra算法求有向图G的v0顶点到其余顶点的最短路径
int n = G.vexnum;//n为G中顶点的个数
for (int v = 0; v < n; v++) {
S[v] = false;//S初始化为空集
D[v] = G.arcs[v0][v];//将v0到各个终点的最短路径长度初始化为弧上的权值
if (D[v] < MaxInt) Path[v] = v0;//如果v0和v之间有弧，则将v的前驱置为v0
else Path[v] = -1;//如果v0和v之间无弧，则将v的前驱置为-1
}
S[v0] = true;//将v0加入S
D[v0] = 0;//源点到源点的距离为0
/*----------初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集-------*/
for (int i = 1; i < n; i++) {
//对其余n-1个顶点，依次进行计算
int min = MaxInt;
int v = 0;
for (int w = 0; w < n; w++)
if (!S[w] && D[w] < min) {
v = w; min = D[w];//选择一条当前的最短路径，终点为v
}
S[v] = true;//将v加入S
for (int w = 0; w < n; w++) {//更新从v0出发到集合V-S上所有顶点的最短路径长度
if (!S[w] && (D[v] + G.arcs[v][w] < D[w])) {
D[w] = D[v] + G.arcs[v][w];//更新D[w]
Path[w] = v;//更改w的前驱为v
}
}
}
}
/*-----------递归输出最短路径----------*/
void find(int x) {
if (Path[x] == 0) {
cout << 0;
}
else {
find(Path[x]);
}
cout << "->" << x;
return;
}
/*--------输出结果----------*/
void PrintResult(AMGraph G) {
cout << "点v0到其他各点的最短路程为：" << endl;
for (int i = 0; i < G.vexnum; i++) {
cout << D[i] << " ";
}
cout << endl;
for (int i = 1; i < G.vexnum; i++) {
if (D[i] == MaxInt) continue;
cout << "起点v0到v" << i << "的路径为：";
find(i);
cout << endl;
}
}
/*-----------主函数-----------*/
int main() {
AMGraph G;
CreateUDN(G);
ShortestPath_DIJ(G, 0);
PrintResult(G);
return 0;
}
11.8 最短路径之Floyd算法
#include<iostream>
using namespace std;
/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define MaxInt 32767//无穷大
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
bool visited[MVNum];//定义标志数组
typedef struct {
VerTexType vexs[MVNum];//顶点表
ArcType arcs[MVNum][MVNum];//邻接矩阵
int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
/*-----------迪杰斯特拉算法辅助数组的建立----------*/
bool S[MVNum];
int Path[MVNum][MVNum];
int D[MVNum][MVNum];
/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
int i;
for (int i = 0; i < G.vexnum; i++)
if (u == G.vexs[i]) return i;
return -1;
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
//采用邻接矩阵表示法，创建无向网
int i = 0, j = 0, k = 0;
cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
for (i = 0; i < G.vexnum; i++)//依次输入点的信息
cin >> G.vexs[i];
for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
for (j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MaxInt;
for (k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;//定义两个顶点v1,v2
int w = 0;
cin >> v1 >> v2 >> w;
i = LocateVex(G, v1);
j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
G.arcs[i][j] = w;
}
}
/*----------弗洛伊德算法代码实现----------*/
void ShortestPath_Floyd(AMGraph G) {
//用Floyd算法求有向图G中各顶点i和j之间的最短路径
for(int i=0;i<G.vexnum;i++)//各对结点之间初始已知路径及距离
for (int j = 0; j < G.vexnum; j++) {
D[i][j] = G.arcs[i][j];
if (D[i][j] < MaxInt && i != j) Path[i][j] = i;//如果i和j之间有弧，则将j的前驱置为1
else Path[i][j] = -1;//如果i和j之间无弧，则将j的前驱置为-1
}
for(int k=0;k<G.vexnum;k++)
for(int i=0;i<G.vexnum;i++)
for(int j=0;j<G.vexnum;j++)
if (D[i][k] + D[k][j] < D[i][j]) {
D[i][j] = D[i][k] + D[k][j];//更新D[i][j]
Path[i][j] = Path[k][j];//更改j的前驱为k
}
}
/*-----------输出结果-----------*/
void PrintResult(AMGraph G) {
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if (D[i][j] == MaxInt && i != j) {
cout << "-1 ";
}
else if (i == j)
cout << "0 ";
else
cout << D[i][j] << " ";
}
cout << endl;
}
}
/*-----------主函数-----------*/
int main() {
AMGraph G;
CreateUDN(G);
ShortestPath_Floyd(G);
PrintResult(G);
return 0;
}
11.9 拓扑排序的实现
#include<iostream>
#include<string>
using namespace std;
#define MVNum 100
#define OK 1
#define ERROR 0
#define MaxInt 100
typedef string VerTexType;
typedef int Status;
typedef int SElemType;
typedef struct{
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
typedef struct ArcNode {
int adjvex;
struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode {
VerTexType data;
ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct {
int vexnum, arcnum;
AdjList vertices;
}ALGraph;
/*--------拓扑排序辅助数组的存储结构--------*/
int indegree[MVNum];//存放各顶点入度
int topo[MVNum];//记录拓扑序列的顶点编号
Status InitStack(SqStack& S) {
S.base = new SElemType[MaxInt];
if (!S.base) return ERROR;
S.top = S.base;
S.stacksize = MaxInt;
return OK;
}
Status StackEmpty(SqStack S) {
if (S.top == S.base) return OK;
return ERROR;
}
Status Push(SqStack& S, SElemType e) {
if (S.top - S.base == S.stacksize) return ERROR;
*S.top = e;
S.top++;
return OK;
}
Status Pop(SqStack& S, SElemType& e) {
if (S.base == S.top) return ERROR;
S.top--;
e = *S.top;
return OK;
}
int LocateVex(ALGraph G, VerTexType v) {
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == v)
return i;
}
return -1;
}
void CreateUDG(ALGraph& G) {
cin >> G.vexnum >> G.arcnum;
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
}
for (int k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;
cin >> v1 >> v2;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
ArcNode* p1 = new ArcNode;
p1->adjvex = j;
p1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1;
}
}
void FindInDegree(ALGraph G, int indegree[]) {
for (int i = 0; i < G.vexnum; i++) {
int cnt = 0;//设置变量存储邻接点域为i的结点个数
for (int j = 0; j < G.vexnum; j++) {
ArcNode* p = new ArcNode;//定义指向各个边结点的指针
p = G.vertices[j].firstarc;
while (p) {//当p未指到单个链表的末尾时继续循环
if (p->adjvex == i)//当某边结点邻接点域等于i时，计数变量++
cnt++;
p = p->nextarc;//指针不断向后指
}
indegree[i] = cnt;//将计数结果保留在indegree数组中
}
}
}
Status TopologicalSort(ALGraph G, int topo[]) {
//有向图G采用邻接表存储结构
//若G无回路，则生成G的一个拓扑排序topo[]并返回OK，否则ERROR
FindInDegree(G, indegree);//求出各结点的入度存入数组indegree中
SqStack S;
InitStack(S);//初始化栈
for (int i = 0; i < G.vexnum; i++) {
if (!indegree[i]) Push(S, i);//入度为0者进栈
}
int m = 0;//对输出顶点计数u，初始为0
while (!StackEmpty(S)) {
int i = 0;
Pop(S, i);//将栈顶顶点vi出栈
topo[m] = i;//将vi保存在拓扑序列数组topo中
++m;//对输出顶点计数
ArcNode* p = new ArcNode;
p = G.vertices[i].firstarc;//p指向vi的第一个邻接点
while (p != NULL) {
int k = p->adjvex;//vk为vi的邻接点
--indegree[k];//vi的每个邻接点的入度减一
if (indegree[k] == 0) Push(S, k);//若入度减为0，则入栈
p = p->nextarc;//p指向顶点vi下一个邻接结点
}
}
if (m < G.vexnum) return ERROR;//该有向图有回路
else return OK;
}
/*输出拓扑排序后的结果*/
void PrintResult(ALGraph G) {
if (TopologicalSort(G, topo)) {
for (int i = 0; i < G.vexnum; i++) {
cout << G.vertices[topo[i]].data << " ";
}
}
}
int main() {
ALGraph G;
CreateUDG(G);
PrintResult(G);
return 0;
}
11.10 关键路径的实现
#include<iostream>
#include<string>
using namespace std;
#define MVNum 100
#define OK 1
#define ERROR 0
#define MaxInt 100
typedef string VerTexType;
typedef int Status;
typedef int SElemType;
typedef int OtherInfo;
typedef struct{
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
typedef struct ArcNode {
int adjvex;
OtherInfo weight;
struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode {
VerTexType data;
ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct {
int vexnum, arcnum;
AdjList vertices;
}ALGraph;
/*--------拓扑排序辅助数组的存储结构--------*/
int indegree[MVNum];//存放各顶点入度
int topo[MVNum];//记录拓扑序列的顶点编号
/*-------关键路径算法的两个辅助数组---------*/
int ve[MVNum];//事件vi的最早发生时间
int vl[MVNum];//事件vi的最迟发生时间
Status InitStack(SqStack& S) {
S.base = new SElemType[MaxInt];
if (!S.base) return ERROR;
S.top = S.base;
S.stacksize = MaxInt;
return OK;
}
Status StackEmpty(SqStack S) {
if (S.top == S.base) return OK;
return ERROR;
}
Status Push(SqStack& S, SElemType e) {
if (S.top - S.base == S.stacksize) return ERROR;
*S.top = e;
S.top++;
return OK;
}
Status Pop(SqStack& S, SElemType& e) {
if (S.base == S.top) return ERROR;
S.top--;
e = *S.top;
return OK;
}
int LocateVex(ALGraph G, VerTexType v) {
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == v)
return i;
}
return -1;
}
void CreateUDG(ALGraph& G) {
cin >> G.vexnum >> G.arcnum;
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vertices[i].data;
G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
}
for (int k = 0; k < G.arcnum; k++) {
VerTexType v1, v2;
int w=0;
cin >> v1 >> v2 >> w;
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
ArcNode* p1 = new ArcNode;
p1->adjvex = j;
p1->weight = w;
p1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = p1;
}
}
void FindInDegree(ALGraph G, int indegree[]) {
for (int i = 0; i < G.vexnum; i++) {
int cnt = 0;//设置变量存储邻接点域为i的结点个数
for (int j = 0; j < G.vexnum; j++) {
ArcNode* p = new ArcNode;//定义指向各个边结点的指针
p = G.vertices[j].firstarc;
while (p) {//当p未指到单个链表的末尾时继续循环
if (p->adjvex == i)//当某边结点邻接点域等于i时，计数变量++
cnt++;
p = p->nextarc;//指针不断向后指
}
indegree[i] = cnt;//将计数结果保留在indegree数组中
}
}
}
/*----------拓扑排序算法---------------*/
Status TopologicalSort(ALGraph G, int topo[]) {
//有向图G采用邻接表存储结构
//若G无回路，则生成G的一个拓扑排序topo[]并返回OK，否则ERROR
FindInDegree(G, indegree);//求出各结点的入度存入数组indegree中
SqStack S;
InitStack(S);//初始化栈
for (int i = 0; i < G.vexnum; i++) {
if (!indegree[i]) Push(S, i);//入度为0者进栈
}
int m = 0;//对输出顶点计数u，初始为0
while (!StackEmpty(S)) {
int i = 0;
Pop(S, i);//将栈顶顶点vi出栈
topo[m] = i;//将vi保存在拓扑序列数组topo中
++m;//对输出顶点计数
ArcNode* p = new ArcNode;
p = G.vertices[i].firstarc;//p指向vi的第一个邻接点
while (p != NULL) {
int k = p->adjvex;//vk为vi的邻接点
--indegree[k];//vi的每个邻接点的入度减一
if (indegree[k] == 0) Push(S, k);//若入度减为0，则入栈
p = p->nextarc;//p指向顶点vi下一个邻接结点
}
}
if (m < G.vexnum) return ERROR;//该有向图有回路
else return OK;
}
/*---------关键路径算法---------*/
Status CriticalPath(ALGraph& G) {
//G为邻接表存储的有向图，输出G的各项关键活动
if (!TopologicalSort(G, topo)) return ERROR;
//调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR
int n = G.vexnum;//n为顶点个数
for (int i = 0; i < n; i++)//给每个事件的最早发生时间置初值为0
ve[i] = 0;
/*-------------按拓扑序列求每个事件的最早发生时间---------------*/
for (int i = 0; i < n; i++) {
int k = topo[i];//取得拓扑序列中的顶点序号k
ArcNode* p = new ArcNode;
p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点
while (p != NULL) {
int j = p->adjvex;//j为邻接顶点的序号
if (ve[j] < ve[k] + p->weight)//更新顶点j的最早发生时间ve[j]
ve[j] = ve[k] + p->weight;
p = p->nextarc;//p指向k的下一个邻接顶点
}
}
for (int i = 0; i < n; i++)
vl[i] = ve[n - 1];//给每个事件的最迟发生时间置初值ve[n-1]
/*-----------按拓扑次序求每个事件的最迟发生时间-----------*/
for (int i = n - 1; i >= 0; i--) {
int k = topo[i];//取得拓扑序列中的顶点序号k
ArcNode* p = new ArcNode;
p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点
while (p != NULL) {//根据k的邻接点，更新k的最迟发生时间
int j = p->adjvex;//j为邻接顶点的序号
if (vl[k] > vl[j] - p->weight)//更新顶点k的最迟发生时间vl[k]
vl[k] = vl[j] - p->weight;
p = p->nextarc;//p指向k的下一个邻接顶点
}
}
/*-----------判断每一个活动是否为关键活动--------------*/
for (int i = 0; i < n; i++) {
ArcNode* p = new ArcNode;
p = G.vertices[i].firstarc;//p指向i的第一个邻接顶点
while (p != NULL) {
int j = p->adjvex;//j为邻接顶点的序号
int e = ve[i];//计算活动<vi,vj>的最早开始时间
int l = vl[j] - p->weight;//计算活动<vi,vj>的最迟开始时间
if (e == l)
cout << G.vertices[i].data << " " << G.vertices[j].data << endl;
p = p->nextarc;//p指向i的下一个邻接顶点
}
}
}
int main() {
ALGraph G;
CreateUDG(G);
CriticalPath(G);
return 0;
}
