实现有向图相关算法

实现有向图相关算法,包括：拓扑排序、任意两点的最短路径算法和可达性分析。要求有个良好的输出显示,同时给出相应的算法时间。

实现有向图相关算法，包括：拓扑排序、任意两点的最短路径算法和可达性分析。

要求有个良好的输出显示，同时给出相应的算法时间。

#include<iostream>

#include<string>

#include "stdlib.h"

#include "stdio.h"

#include "string.h"

using namespace std;

#define INfinity 10000//最大值

#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef struct ArcCell{//储存弧信息

int Distance;

ArcCell *info;

}ArcCell,AdjMatrix[ MAX_VERTEX_NUM][ MAX_VERTEX_NUM];

typedef struct{//储存顶点信息

string vexs[ MAX_VERTEX_NUM];//顶点向量

AdjMatrix arcs;//邻接矩阵

int vexnum , arcnum;//图的当前顶点数和弧数

}MGraph;

int Locate(MGraph &G,string v)

{ int a=0;

for (int i=0;i<G.vexnum;i++)

{

if( G.vexs[i]==v) {

a=i;

break;}

}

return a;

}

void CreateDN(MGraph &G)//采用邻接矩阵表示法，构造有向图G

{ string v1,v2;

int w;

cout<<"请依次输入图的顶点数和弧数"<<endl;

cin>>G.vexnum>>G.arcnum;

for (int i=0;i<G.vexnum;i++)

{ cout<<"请按顺序输入地点"<<endl;

cin>>G.vexs[i];

}

for ( i=0;i<G.vexnum;i++)//初始化邻接矩阵；

{ for (int j=0;j<G.vexnum;j++) G.arcs[i][j].Distance=INfinity;}

for (int k=0;k<G.arcnum;k++){

cout<<"请输入某条路径的初始地点V1,终点V2及他们之间的距离W"<<endl;

实现有向图相关算法,包括：拓扑排序、任意两点的最短路径算法和可达性分析。要求有个良好的输出显示,同时给出相应的算法时间。

cin>>v1>>v2>>w;

int i=Locate(G,v1);

int j=Locate(G,v2);

G.arcs[i][j].Distance=w;

}

}

void Floyd(MGraph &G)

{ int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];

int d[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

for (int v=0;v<G.vexnum;v++)

{ for (int w=0;w<G.vexnum;w++)

{ d[v][w]=G.arcs[v][w].Distance;

for (int u=0;u<G.vexnum;u++)

{ P[v][w][u]=0;

if (d[v][w]<INfinity)//从v到w有直接路径

{P[v][w][v]=1;P[v][w][w]=1; }

}

}

}

for (int u=0;u<G.vexnum;u++)

{for (int v=0;v<G.vexnum;v++)

{for (int w=0;w<G.vexnum;w++)

{ if (d[v][u]+d[u][w]<d[v][w])//从v经u到w的一条路径更短

{

d[v][w]=d[v][u]+d[u][w];

for (int i=0;i<G.vexnum;i++)

{P[v][w][i]=P[v][u][i]||P[u][w][i];}

}

}

}

}

for ( v=0;v<G.vexnum;v++)

{for (int w=0;w<G.vexnum;w++)

{ if(v!=w)

{cout <<"从"<<G.vexs[v]<<"到"<<G.vexs[w]<<"的最短路径为:"<<d[v][w]<<endl;

cout <<"途径城市为:";

for (int u=0;u<G.vexnum;u++)

{ if (P[v][w][u]==1)//P[v][w][u]为，说明u为v到w的最短路劲中的一个顶点

{cout <<G.vexs[u];}

}

cout<<""<<endl;

}

}

}

实现有向图相关算法,包括：拓扑排序、任意两点的最短路径算法和可达性分析。要求有个良好的输出显示,同时给出相应的算法时间。

typedef int ElemType;

typedef struct QNode

{ ElemType data;

struct QNode *next;

} QNode,*QueuePtr;

typedef struct

{ QueuePtr front;

QueuePtr rear;

} LinkQueue;

/* 1.初始化链式队列 */

void InitQueue(LinkQueue *Q)

{ Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));

if (!(Q->front)) exit(0);

Q->front->next=NULL; }

/* 2.判断空队列 */

int QueueEmpty(LinkQueue Q)

{ if(Q.front==Q.rear)

return 1;

else

return 0; }

/* 3.入队列 */

void EnQueue(LinkQueue *Q, ElemType e)

{ QueuePtr p;

p=(QueuePtr)malloc(sizeof(QNode));

if (!p) exit(0);

p->data=e; p->next=NULL;

Q->rear->next=p;

Q->rear=p; }

/* 4.出队列 */

void DeQueue(LinkQueue *Q, ElemType *e)

{ QueuePtr p;

if(Q->front!=Q->rear)

{ p=Q->front->next;

*e=p->data;

Q->front->next=p->next;

if (Q->rear==p) Q->rear=Q->front;

free(p); }

实现有向图相关算法,包括：拓扑排序、任意两点的最短路径算法和可达性分析。要求有个良好的输出显示,同时给出相应的算法时间。

/****************************************************/

/* 以下为有向图(DAG)邻接表存储结构(ALG)的操作 */

/****************************************************/

typedef char VertexType[20]; //顶点信息（名称）

/* 图的类型定义（邻接表存储结构） */

typedef struct ArcNode //链表结点

{ int vexpos; //该弧所指向的顶点在数组中的位置

struct ArcNode *next; //指向当前起点的下一条弧的指针

} ArcNode;

typedef struct VNode //头结点

{ VertexType name; //顶点信息（名称）

int indegree; //顶点入度

ArcNode *firstarc; //指向当前顶点的第一条弧的指针

} VNode,AdjList[MAX_VERTEX_NUM];

typedef struct

{ AdjList vexhead; //邻接表头结点数组

int vexnum,arcnum; //图的顶点数和弧数