实现有向图相关算法

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

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

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

#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; //图的顶点数和弧数

} ALGraph;

/* 5.顶点在头结点数组中的定位 */

int LocateVex(ALGraph G,VertexType v)

{ int i;

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

if(strcmp(v,G.vexhead[i].name)==0) break;

return i; }

/* 6.建立图（邻接表） */

int CreateGraph(ALGraph *G) //成功建立返回1，不成功则返回0

{ int i,j,k; VertexType v1,v2;ArcNode *newarc;

printf("\n输入有向图顶点数和弧数vexnum,arcnum:"); //输入顶点数和弧数

scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); //输入并判断顶点数和弧数是否正确

if((*G).vexnum<0||(*G).arcnum<0||(*G).arcnum>(*G).vexnum*((*G).vexnum-1))

{ printf("\n顶点数或弧数不正确，有向图建立失败！\n");return 0; }

printf("\n输入 %d 个顶点:",(*G).vexnum); //输入顶点名称

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

{ scanf("%s",(*G).vexhead[i].name); }

printf("\n顶点列表:\n共有%d个顶点: ",(*G).vexnum);//输出顶点名称

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

printf("%s ",(*G).vexhead[i].name);

for(i=0;i<(*G).vexnum;i++) //邻接表初始化

{ (*G).vexhead[i].firstarc=NULL;

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

(*G).vexhead[i].indegree=0;}

printf("\n\n输入 %d 条边:vi vj\n",(*G).arcnum); //输入有向图的边

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

{ scanf("%s%s",v1,v2); //v1是弧的起点（先决条件），v2是弧的终点

i=LocateVex(*G,v1);j=LocateVex(*G,v2); //定位顶点并判断顶点是否存在

if(i>=(*G).vexnum)

{ printf("顶点%s不存在，有向图建立失败！\n",v1);return 0; } if(j>=(*G).vexnum)

{ printf("顶点%s不存在，有向图建立失败！\n",v2);return 0; }

newarc=(ArcNode*)malloc(sizeof(ArcNode)); //前插法建顶点链表

newarc->vexpos=j;

if((*G).vexhead[i].firstarc==NULL)

{ newarc->next=NULL;

(*G).vexhead[i].firstarc=newarc; }

else

{ newarc->next=(*G).vexhead[i].firstarc->next;

(*G).vexhead[i].firstarc->next=newarc; }

(*G).vexhead[j].indegree++; //对应顶点入度计数加1

}

printf("\n有向图建立成功！\n");

return 1;

}

/* 7.按邻接表方式输出有向图 */

void PrintGraph(ALGraph G)

{ int i;ArcNode *p;

printf("\n输出有向图:\n");

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

{ printf("\n顶点:%s ",G.vexhead[i].name);

printf("入度:%3d\n",G.vexhead[i].indegree);

p=G.vexhead[i].firstarc;

printf("邻接点:");

while(p!=NULL)

{ printf("%s ",G.vexhead[p->vexpos].name);

p=p->next; }

printf("\n");

}

}

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

/* 以下为拓扑排序算法 */

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

/* 8.拓扑排序 */

void TopologicalSort(ALGraph G)

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

{ int i,k,count;ElemType e;ArcNode *p;

LinkQueue Q; /*定义队列*/

InitQueue(&Q);

for(i=0; i<G.vexnum; i++) //入度为0入队列

if(!G.vexhead[i].indegree) EnQueue(&Q,i);

count=0; //初始化变量

printf("\n\n\n其中一个拓扑排序序列为:\n");

while(!QueueEmpty(Q))

{ DeQueue(&Q,&e); //输出入度为零的点

printf("%s ",G.vexhead[e].name);

count++; //对输出的顶点计数

for(p=G.vexhead[e].firstarc;p;p=p->next) //遍历当前点的邻接点

{ k=p->vexpos; //邻接点位置

if(!(--G.vexhead[k].indegree)) //每个邻接点入度减1后若为零则入队列 EnQueue(&Q,k);

}

}

printf("\n");

if(count<G.vexnum)

{ printf("\n该有向图有回路，无法完成拓扑排序！\n"); }

}

void main()

{ ALGraph G; int menu,menu2;

while(1)

{

printf("\n **********************************************\n"); printf(" * 1.建立有向图并求一个拓扑排序序列 *\n"); printf(" * 2.输出有向图的邻接矩阵(可达性分析) *\n"); printf(" * 3.任意两点的最短路径算法 *\n"); printf(" * 4.退出 *\n"); printf(" **********************************************\n"); printf(" 请输入你的选择:");

scanf("%d",&menu);

switch(menu){

case 1:

if(CreateGraph(&G))

{

system("PAUSE");

PrintGraph(G);

//system("PAUSE");

TopologicalSort(G);

}//有向图建成则执操作

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

break;

case 2:

if(CreateGraph(&G)) //有向图建成则执操作 { system("PAUSE");

PrintGraph(G);

}

break;

case 3:

MGraph *G;

G=new MGraph;

CreateDN(*G);

Floyd(*G);

break;

case 4:

return;

}

}

}