图的算法 谁比较强 进来帮帮我吧
哪位大神帮帮我吧 我实在是不知道怎么办了 拓扑排序 和关键路径怎么就是融不进去呢？其他功能都实现了 就差这两个功能了 #include <stdio.h>
#include <stdlib.h>
#define INFINITY 3000 //定义一个权值的最大值
#define MAX_VERTEX_NUM 20 //图的最大顶点数
#define MAXQSIZE 30 //队列的最大容量
#define MAXEDGE 100 /*MAXEDEG为边的最大数目*/
typedef char VertexType[MAX_VERTEX_NUM];
enum BOOL {False,True};
typedef float AdjType;
typedef struct ArcNode
{
int adjvex; //该弧所指向的顶点的位置
AdjType weight;
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode; //弧结点
typedef struct VNode
{ VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 边表头指针 */
}VNode,AdjL[MAX_VERTEX_NUM]; /* 顶点表中的结点 */
typedef struct
{
AdjL vertices;
ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点和边数
int indegree[MAX_VERTEX_NUM];
}Graph;
typedef struct //队列结构
{
int elem[MAXQSIZE]; //数据域
int front; //队头指针
int rear; //队尾指针
}SqQueue;
BOOL visited[MAX_VERTEX_NUM]; //全局变量--访问标志数组
void CreateGraph(Graph &G)
{//构造邻接矩阵结构的图G
int i,j;
int start,end,weight;
for(i=1;i<=G.vexnum;i++) G.AdjList[i]=NULL; //初始化指针数组
for(i=1;i<=G.vexnum;i++)
{
for(j=1;j<=G.vexnum;j++)
{
G.arcs[i][j]=INFINITY; //初始化邻接矩阵
}
}
printf("输入时，顶点从1开始编号:\n",i);
for(i=1;i<=G.arcnum;i++)
{
printf("输入第%d条弧及其权值(格式：弧尾，弧头，权值):\n",i);
scanf("%d,%d,%d",&start,&end,&weight); //输入边的起点和终点及权值
G.arcs[start][end]=weight;
}
}
void FindInDegree(Graph G,int inDegree[])
{ int i;
ArcNode *s;
for(i=0;i<G.vexnum;i++)
inDegree[i]=0; /*顶点入度数组赋初值*/
for(i=0;i<G.vexnum;i++)
{s=G.vertices[i].firstarc;//取该元素边表中的第一个边结点，删除该结点,构造新的AOV网
while(s)
{ inDegree[s->adjvex]++;
s=s->nextarc;
}
}
}
void makeNewAOV(ArcNode *s,int *indegree, int &top)
{ int k;
while(s) /* 删除以该顶点为起点的边 */
{ k=s->adjvex;
indegree[k]--;
if(indegree[k]==0) /* 将新的入度为零的边入栈 */
{ indegree[k]=top;
top=k;
}
s=s->nextarc;
}
}
int topoSort(Graph G,int *topo) /*拓扑排序算法*/
{ ArcNode *s;
int i,j,count=0,top=-1;
int indegree[MAX_VERTEX_NUM];
FindInDegree(G,indegree); /* 求出图中所有顶点的入度 */
for(i=0;i<G.vexnum;i++)
if(indegree[i]==0) /* 将入度为零的顶点入栈*/
{ indegree[i]=top;
top=i;
}
while(top!=-1) /* 栈不为空 */
{ j=top;
top=indegree[top]; /* 取出当前栈顶元素 */
topo[count++]=j; /*ptopo数组存放拓扑序列*/
s=G.vertices[j].firstarc;
//取该元素边表中的第一个边结点，删除该结点,构造新的AOV网
makeNewAOV(s,indegree,top); //对indegree数组进行修改
}
if(count<G.vexnum) /* AOV网中存在回路 */
{ printf("The aov network has a cycle\n");
return False;
}
printf("拓扑序列为： "); //输出拓扑序列
for(i=0;i<G.vexnum;i++) printf("V%1d ",topo[i]+1); printf("\n");
return True;
}
void countve(Graph G,int *topo,AdjType *ve) /* 计算各事件的最早发生时间*/
{ int i,j,k;
ArcNode *s;
for(i=0;i<G.vexnum;i++) ve[i]=0; /*ee数组赋初值*/
for(k=0;k<G.vexnum;k++) /* 求事件vj可能的最早发生时间ee(j) */
{ i=topo[k]; //k仅起控制作用
s=G.vertices[i].firstarc;
while(s!=NULL)
{ j=s->adjvex;
if(ve[i]+s->weight>ve[j]) ve[j]=ve[i]+s->weight;
s=s->nextarc;
}
}
}
void countvl(Graph G,int *topo,AdjType *ve, AdjType *vl) /*计算各事件的最迟发生时间*/
{ int i,j,k; ArcNode *s;
for(i=0;i<G.vexnum;i++) //求事件vi允许的最迟发生时间vl(i)
vl[i]=ve[G.vexnum-1]; /*每个事件的最迟发生时间赋初值为最生事件的最早发生时间（本例均为18）*/
for(k=G.vexnum-2;k>=0;k--) /*下标从0开始，最后一个顶点无后继，所以减2*/
{ i=topo[k];
s=G.vertices[i].firstarc;
while(s!=NULL)
{ j=s->adjvex;
if(vl[j]-s->weight<vl[i]) vl[i]=vl[j]-s->weight;
s=s->nextarc;
}
}
}
void counte_l(Graph G,AdjType *ve,AdjType *vl,AdjType *ee,AdjType *el)
/*计算各活动的最早发生时间和最迟发生时间，并输出关键路径*/
{ int i=0,j,k; ArcNode *s;
printf("关键路径是： ");
for(j=0;j<G.vexnum;j++) /*求活动ai的最早开始时间ee(i)及最晚开始时间el(i) */
{ s=G.vertices[j].firstarc;
while(s!=NULL)
{ k=s->adjvex;
ee[i]=ve[j];
el[i]=vl[k]-s->weight;
if(ee[i]==el[i]) printf("<v%1d, v%1d>, ",j+1,k+1);
i++; //i表示弧的序号。弧的序号自第一个顶点开始到最后一个顶点止顺序编号。
s=s->nextarc;
} } }
int CriticalPath(Graph G) /*关键路径算法*/
{ AdjType ve[MAX_VERTEX_NUM],vl[MAX_VERTEX_NUM],ee[MAX_VERTEX_NUM],el[MAX_VERTEX_NUM];
int topo[MAX_VERTEX_NUM];
if(topoSort(G,topo)==False) /*求AOE网的一个拓扑序列*/
return False; /*若有环则返回FALSE*/
countve(G,topo,ve); /*计算数组ve，ve存放事件可能的最早发生时间*/
countvl(G,topo,ve,vl); /*计算数组vl，vl存放事件可能的最迟发生时间*/
counte_l(G,ve,vl,ee,el); /*计算数组ee,el并输出结果*/
printf("\n"); /*数组ee存放活动的最早开始时间,数组el存放活动的最晚开始时间*/
return True;
}
void ShortestPath_DiJ(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[])
{ //用迪杰斯特拉算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权路径长度D[v]
//若P[v][0]≠0,表明从源点出发存在一条到顶点v的最短路径，该路径存放在P[v]中
//final[v]为True则表明已经找到从v0到v的最短路径
int i,j,w,v;
int min;
BOOL final[MAX_VERTEX_NUM];
for(v=1;v<=G.vexnum;v++) //初始化
{
final[v]=False; D[v]=G.arcs[v0][v];
for(i=0;i<=G.vexnum;i++) P[v][i]=0; //设空路径
//if(D[v]<INFINITY) P[v][0]=v0; //若从v0到v有直达路径
}
D[v0]=0; final[v0]=True; //初始时，v0属于S集
//开始主循环，每次求得v0到某个顶点v的最短路径，并加v到S集
for(i=1;i<=G.vexnum;i++) //寻找其余G.vexnum-1个顶点
{
v=0;
min=INFINITY;
for(w=1;w<=G.vexnum;w++) //寻找当前离v0最近的顶点v
{
if((!final[w])&&(D[w]<min))
{
v=w;min=D[w];
}
}
if(!v) break; //若v=0表明所有与v0有通路的顶点均已找到了最短路径，退出主循环
final[v]=True; //将v加入S集
for(j=0;P[v][j]!=0;j++) ;
P[v][j]=v; //将路径P[v]延伸到顶点v
for(w=1;w<=G.vexnum;w++) //更新当前最短路径及距离
{
if(!final[w]&&(min+G.arcs[v][w]<D[w]))
{
D[w]=min+G.arcs[v][w];
for(j=0;P[v][j]!=0;j++)
{
P[w][j]=P[v][j];
}
}
}
}
}
void Print_ShortestPath(Graph G,int v0,int P[][MAX_VERTEX_NUM],int D[])
{//显示从顶点u到其余顶点的最短路径及距离
int v,j;
printf("到各个顶点的最短路径分别为:\n");
for(v=1;v<=G.vexnum;v++)
{
if(P[v][0]==0) continue; //表明顶点v0到顶点v没有通路
printf("%-4d",D[v]);
printf("%d->",v0);
for(j=0;P[v][j]!=0;j++)
printf("%d->",P[v][j]);
printf("\b\b \n");
}
}
int FirstAdjVex(Graph G,int v)
{//在图G中寻找第v个顶点的第一个邻接顶点
if(!G.AdjList[v]) return 0;
else return(G.AdjList[v]->adjvex);
}
int NextAdjVex(Graph G,int v,int u)
{//在图G中寻找第v个顶点的相对于u的下一个邻接顶点
ArcNode *p;
p=G.AdjList[v];
while(p->adjvex!=u) p=p->nextarc; //在顶点v的弧链中找到顶点u
if(p->nextarc==NULL) return 0; //若已是最后一个顶点，返回0
else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号
}
void DFS(Graph G,int i)
{//从第i个顶点出发递归地深度遍历图G
int w;
visited[i]=True; //访问第i个顶点
printf("%d->",i);
for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))
if(!visited[w]) DFS(G,w); //对尚未访问的邻接顶点w调用DFS
}
void DFSTraverse(Graph G)
{//深度优先遍历图G
int i;
printf("DFSTraverse:");
for(i=1;i<=G.vexnum;i++) visited[i]=False; //访问标志数组初始化
for(i=1;i<=G.vexnum;i++)
if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS
printf("\b\b \n");
}
void Initial(SqQueue &Q)
{//队列初始化
Q.front=Q.rear=0;
}
BOOL QueueEmpty(SqQueue Q)
{//判断队列是否已空，若空返回True,否则返回False
if(Q.front==Q.rear) return True;
else return False;
}
BOOL EnQueue(SqQueue &Q,int ch)
{//入队列，成功返回True，失败返回False
if((Q.rear+1)%MAXQSIZE==Q.front) return False;
Q.elem[Q.rear]=ch;
Q.rear=(Q.rear+1)%MAXQSIZE;
return True;
}
BOOL DeQueue(SqQueue &Q,int &ch)
{//出队列,成功返回True，并用ch返回该元素值，失败返回False
if(Q.front==Q.rear) return False;
ch=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return True; //成功出队列，返回True
}
void BFSTraverse(Graph G)
{//按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited
int i,u,w;
SqQueue Q;
printf("BFSTreverse:");
for(i=1;i<= G.vexnum;i++) visited[i]=False; //访问标志数组初始化
Initial(Q); //初始化队列
for(i=1;i<=G.vexnum;i++)
if(!visited[i])
{visited[i]=True; //访问顶点i
printf("%d->",i);
EnQueue(Q,i); //将序号i入队列
while(!QueueEmpty(Q)) //若队列不空，继续
{DeQueue(Q,u); //将队头元素出队列并置为u
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if(!visited[w]) //对u的尚未访问的邻接顶点w进行访问并入队列
{visited[w]=True;
printf("%d->",w);
EnQueue(Q,w);
}
}
}
printf("\b\b \n");
}
void main()
{
Graph G; //采用邻接矩阵结构的图
int u;
int indegree[MAX_VERTEX_NUM];
int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径
int D[MAX_VERTEX_NUM]; //存放从源点到各顶点的最短路径的距离
int topo[MAX_VERTEX_NUM];
printf("请输入有向图顶点数和弧数(格式为:n,m)：");
scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和弧数
CreateGraph(G); //生成邻接表结构的图
DFSTraverse(G); //深度优先搜索遍历图
BFSTraverse(G); //广度优先搜索遍历图
printf("从哪个顶点出发:");
scanf("%d",&u); //输入迪杰斯特拉算法中的起始顶点
ShortestPath_DiJ(G,u,P,D); //利用迪杰斯特拉算法求最短路径
Print_ShortestPath(G,u,P,D); //显示最短路径
topoSort(G,topo);
CriticalPath(G);
if(CriticalPath(G)== False)
printf("There is no critical path!\n");
}
