本篇文章给大家谈谈求有向网的关键路径c语言,以及c语言相对路径和绝对路径对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。
本文目录一览:
1、关键路径怎么求?求详解。2、关键路径c++代码实现3、c语言数据结构 最短路径问题代码4、数据结构(C语言版) 图的遍历和拓扑排序
关键路径怎么求?求详解。
关键路径的算法是建立在拓扑排序的基础之上的,这个算法中用到了拓扑排序。
1.什么是拓扑排序?
举个例子先:一个软件专业的学生学习一系列的课程,其中一些课程必须再学完它的基础的先修课程才能开始。如:在《程序设计基础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条件定义了课程之间的领先(优先)关系。这个关系可以用有向图更清楚地表示。图中顶点表示课程,有向边表示先决条件。若课程i是课程j的先决条件,则图中有弧i,j。若要对这个图中的顶点所表示的课程进行拓扑排序的话,那么排序后得到的序列,必须是按照先后关系进行排序,具有领先关系的课程必然排在以它为基础的课程之前,若上例中的《程序设计基础》和《离散数学》必须排在《数据结构》之前。进行了拓扑排序之后的序列,称之为拓扑序列。
2.如何实现拓扑排序?
很简单,两个步骤:
1.在有向图中选一个没有前驱的顶点且输出。
2.从图中删除该顶点和以它为尾的弧。
重复上述两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。
3.什么是关键路径?
例子开头仍然,图1是一个假想的有11项活动的A0E-网。其中有9个事件v1,v2……,v9,每个事件表示在它之前的活动一完成,在它之后的活动可以开始。如v1表示整个工程的开始,v9表示整个工程结束,v5表示a4和a5已完成,a7和a8可以开始。与每个活动相联系的数是执行该活动所需的时间。比如,活动a1需要6天,a2需要4天。
由于整个工程只有一个开始点和一个完成点,故在正常情况(无环)下,网中只有一个入度为零的点(称作源点)和一个出度为零的点(叫做汇点)。
那么该工程待研究的问题是:1.完成整项工程至少需要多少时间?2.哪些活动是影响工程进度的关键?
由于在AOE-网中有些活动可以并行进行,所以完成工程的最短时间是从开始点到完成点的最长路径的长度(这里所说的路径长度是指路径上各活动持续时间之和,不是路径上弧的数目)。路径长度最长的路径叫做关键路径(Critical path)。
假设开始点是v1,从v1到vi的最长路径叫做时间vi的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间。还可以定义一个活动开始的最迟时间l(i),这是在不推迟整个工程完成的前提下,活动ai最迟必须开始进行的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。当这个时间余量等于0的时候,也即是l(i)=e(i)的活动,我们称其为关键活动。显然,关键路径上的所有活动都是关键活动,因此提前完成非关键活动并不能加快工程的进度。
因此,分析关键路径的目的是辨别哪些是关键活动,以便争取提高关键活动的功效,缩短整个工期。
4.如何实现关键路径?
由上面的分析可知,辨别关键活动就是要找e(i)=l(i)的活动。为了求得e(i)和l(i),首先应求得事件的最早发生时间ve(j)和最迟发生时间vl(j)。如果活动ai由弧j,k表示,其持续时间记为dut(j,k),则有如下关系
e(i) = ve(j)
l(i) = vl(k) – dut(j,k)
求解ve(j)和vl(j)需分两个步进行:
1)从ve(0)=0开始向前推进求得ve(j)
Ve(j) = Max{ve(i) + dut(i,j) };i,j属于T,j=1,2…,n-1
其中T是所有以第j个顶点为头的弧的集合。
2)从vl(n-1) = ve(n-1)起向后推进求得vl(j)
vl(i) = Min{vl(j) – dut(i,j};i,j属于S,i=n-2,…,0
其中,S是所有以第i个顶点为尾的弧的集合。
这两个递推公式的计算必须分别在拓扑有序和逆拓扑有序的前提先进行。也就是说,ve(j-1)必须在vj的所有前驱的最早发生时间求得之后才能确定,而vl(j-1)必须在Vj的所有后继的最迟发生时间求得之后才能确定。因此可以在拓扑排序的基础上计算ve(j-1)和vl(j-1)。
具体算法描述如下:
1.输入e条弧j,k,建立AOE-网的存储结构。
2.拓扑排序,并求得ve[]。从源点V0出发,令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤3。
3.拓扑逆序,求得vl[]。从汇点Vn出发,令vl[n-1] = ve[n-1],按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
4.求得关键路径。根据各顶点的ve和vl值,求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s),则为关键活动。
为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值,需记下在拓扑排序的过程中求得的拓扑有序序列,这就需要在拓扑排序算法中,增设一个栈,以记录拓扑有序序列,则在计算求得各顶点的ve值之后,从栈顶到栈底便为逆拓扑有序序列。
package graph;
import java.util.*;
public class Grph_CriticalPath
{
Graph_AdjList adjList;
StackInteger T = new StackInteger();
int ve[];
int vl[];
final int max = 10000;
public Grph_CriticalPath(Graph_AdjList adjList) //图的存储结构是用的邻接表
{
this.adjList = adjList;
int length = adjList.vetexValue.length;
ve = new int[length];
vl = new int[length];
for(int i=0;ilength;i++)
{
ve[i] = 0;
vl[i] = max;
}
}
public void getCriticalPath()
{
topologicalOrder();
int t = T.pop();
T.push(t);
vl[t] = ve[t];
while(!T.isEmpty())
{
int j = T.pop();
for(Graph_AdjList.ArcNode p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(vl[k]-p.weightvl[j])
{
vl[j] = vl[k]-p.weight;
}
}
}
for(int i=0;ive.length;i++)
{
for(Graph_AdjList.ArcNode p = adjList.vetex[i].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
int ee = ve[i];
int el = vl[k]-p.weight;
if(ee==el)
{
System.out.print(i+”,”+k+” “);
}
}
}
}
public void topologicalOrder()
{
StackInteger S = new StackInteger();
S.push(0);
int count = 0;
while(!S.isEmpty())
{
int j = S.pop();
T.push(j);
count++;
Graph_AdjList.ArcNode p = null;
for(p = adjList.vetex[j].firstArc; p!=null ;p = p.next)
{
int k = p.adjvex;
if(–adjList.degree[k]==0)
{
S.push(k);
}
if(ve[j]+p.weightve[k])
{
ve[k] = ve[j]+p.weight;
}
}
}
if(countadjList.vetexValue.length)
{
System.out.println(“图中存在环路!”);
return;
}
}
public void print()
{
while(!T.isEmpty())
{
System.out.print(T.pop()+” “);
}
}
public void printVel()
{
System.out.println();
for(int i=0;ive.length;i++)
{
System.out.print(ve[i]+” “);
}
System.out.println();
for(int i=0;ivl.length;i++)
{
System.out.print(vl[i]+” “);
}
}
}
转自:
关键路径c++代码实现
/*
AOE网研究的问题
(1) 完成整个工程至少需要多少时间;
(2) 哪些活动是影响工程的关键。
注意:该程序可以计算多条关键路径的情况,
只是输出有些不仅人意
数据文件aaa.txt的内容
A B 1
A F 3
A H 4
B C 2
F C 6
H I 4
C D 3
C G 4
I G 1
D E 5
G E 3
*/
#includeiostream
#includefstream
using namespace std;
#define N 9
#define MAX 10000
int g[N][N];/*存储图,有向图,有权*/
int into[N];/*存储入度*/
int ans[N];/*存储结果序列,模拟栈*/
int ve[N];/*点的最早时间 ve[j]=Max(ve[k]+g[k][j]) */
int vl[N];/*点的最迟时间 vl[i]=Min(v[k]-g[i][k]) */
//int ee[N*N];/*边的最早时间 ee[m]=ve[i]*/
//int el[N*N];/*边的最迟时间 el[m]=vl[j]-g[i][j]*/
bool topoSort()
{
/*初始化*/
for(int i=0;iN;i++)
{
into[i]=-1;
ans[i]=-1;
ve[i]=0;/*初始化ve*/
}
/*计算入度*/
for(int i=0;iN;i++)
{
for(int j=0;jN;j++)
{
if(g[i][j]MAX) into[j]++;
}
}
/*零入度顶点入栈*/
int top=0; /*栈顶指针*/
for(int i=0;iN;i++)
{
int j=0;
while(0!=into[j])
{
j++;
if(jN)
{
cout”晕!有环”endl;
return false;
}
}
/*进入队列*/
ans[i]=j;
into[j]=-1;
/*计算Ve*/
for(int k=0;k=i;k++)
{
if(g[ans[k]][j] MAX)/*寻找前驱,k是ans中的标号*/
{
cout”ans[“(char(k+’A’))”]= “ans[k]” “;
if(ve[j] ve[ans[k]]+g[ans[k]][j])/*更新数据 ve[j]=Max(ve[k]+g[k][j])*/
{
ve[j] = ve[ans[k]]+g[ans[k]][j];
cout”ve[“(char(j+’A’))”]= “ve[j]endl;
}
}
}
coutendlendl;
for(int k=0;kN;k++)
{
if(MAX g[j][k])
into[k]–;
}
}
for(int m=0;mN;m++)
{
coutchar(ans[m]+’A’)” “;
}
coutendl;
for(int m=0;mN;m++)
{
coutve[m]” “;
}
coutendl;
/*计算vl, vl[i]=Min(v[k]-g[i][k])*/
/*初始化vl*/
int temp=ve[ans[N-1]];
for(int m=0;mN;m++)
{
vl[m]=temp;
}
/*计算*/
for(int i=N-1;i=0;i–)
{
for(int k=i;kN;k++)
{
if(g[ans[i]][ans[k]] MAX)/*是后继,k和i都是ans中的标号*/
{
if(vl[ans[i]] vl[ans[k]]-g[ans[i]][ans[k]])/*更新数据*/
{
vl[ans[i]] = vl[ans[k]]-g[ans[i]][ans[k]];
}
}
}
}
for(int m=0;mN;m++)
{
coutvl[m]” “;
}
coutendl;
/*找关键点,i,j ve[i]==vl[j]-g[i][j]*/
for(int i=0;iN;++i)
{
for(int j=i;jN;j++)
{
if(g[ans[i]][ans[j]] MAX ans[i]!=ans[j])/*存在一条边i,j*/
{
/*剩余时间为零,该边在关键路径上,其两个顶点为关键点*/
//coutvl[ans[i]]” “g[ans[i]][ans[j]]” “ve[ans[i]]endl;
if(vl[ans[j]]-g[ans[i]][ans[j]]==ve[ans[i]])
{
cout””char(ans[i]+’A’)” , “char(ans[j]+’A’)” “;
}
}
}
}
coutendl;
return true;
}
int main()
{
/*输入数据*/
fstream fin(“aaa.txt”);
if(!fin)
{
cerr”Cannot open aaa.txt”endl;
}
/*初始化邻接表*/
for(int m=0;mN;m++)
{
for(int n=0;nN;n++)
{
if(m==n) g[m][n]=0;
else g[m][n]=MAX;
}
}
//memset(g, MAX, sizeof(g));
char i,j;
int k;
while(finijk)
{
g[(int)(i-‘A’)][(int)(j-‘A’)]=k;
}
for(int m=0;mN;m++)
{
for(int n=0;nN;n++)
coutg[m][n]” “;
coutendl;
}
/*拓扑排序*/
int noRing=topoSort();
if(!noRing)
{
return 0;
}
return 1;
}
c语言数据结构 最短路径问题代码
直接看代码:
#include stdlib.h
#define MAXVEX 10
typedef struct graph{
int n,e;//顶点数、边数
char vexs[MAXVEX];//顶点数组
int arcs[MAXVEX][MAXVEX];//邻接矩阵
int kind;//类型:0有向图;1无向图;2有向网;3无向网
} MGraph;
void PrintPath(MGraph G,int *p,int i){
if(p[i]=0){
PrintPath(G,p,p[i]);//先输出前驱顶点
}
printf(“%c”,G.vexs[i]);//输出本顶点
}
void Dijkstra(MGraph G, int v){
//用Dijkstra算法求有向网G中序号为v的顶点到
//其余各顶点的最短路径
int *s,*d,*p,i,j,k,min;
if(v0||v=G.n){//顶点编号参数错误
printf(“Dijkstra parameter ERROR! v0 Or v=%d”,G.n);
return;
}
s=(int *)malloc(sizeof(int)*G.n);
d=(int *)malloc(sizeof(int)*G.n);
p=(int *)malloc(sizeof(int)*G.n);
for(i=0;iG.n;i++){ //初始化辅助数组,置0
s[i]=0;d[i]=G.arcs[v][i];
if(d[i]!=0)p[i]=v; //v是vi的直接前驱
else p[i]=-1; //-1表示无直接前驱
}
s[v]=1;d[v]=0; //确定源点自身的最短路径长度
printf(“Dijkstra: (The shortest path from %c:)\n”,G.vexs[v]);
for(i=0;iG.n-1;i++){
//确定v到其余n-1个顶点的最短路径
min=32767;k=-1;
for(j=0;jG.n;j++){
//找出路径长度最小的顶点k
if(!s[j]d[j]!=0d[j]min){
k=j; min=d[k];
}
}
if(k0){//有未能到达的顶点,把它们输出
for(j=0;jG.n;++j){
if(j==v)continue;
if(s[j]==0){
printf(“%c-%c: No path.\n”,G.vexs[v],G.vexs[j]);
}
}
free(s); free(d); free(p);
return; //已完成或出现不连通的顶点
}
s[k]=1;
printf(“%c-%c: d=%-5d, p=”,G.vexs[v],G.vexs[k],d[k]);
PrintPath(G,p,k);//输出v到i的路径(正序)
printf(“\n”);
for(j=0;jG.n;j++){
//更新其余顶点的最短路径及前驱
if(!s[j]G.arcs[k][j]!=0(d[j]==0||d[j]d[k]+G.arcs[k][j])){
d[j]=d[k]+G.arcs[k][j]; p[j]=k;
}
}
}
free(s); free(d); free(p);
}
这是单源的最短路径算法。
数据结构(C语言版) 图的遍历和拓扑排序
#includestring.h
#includectype.h
#includemalloc.h /* malloc()等*/
#includelimits.h /* INT_MAX 等*/
#includestdio.h /* EOF(=^Z 或F6),NULL */
#includestdlib.h /* atoi() */
#includeio.h /* eof() */
#includemath.h /* floor(),ceil(),abs() */
#includeprocess.h /* exit() */
/* 函数结果状态代码*/
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h 中已定义OVERFLOW 的值为3,故去掉此行*/
typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码,如OK 等*/
typedef int Boolean; Boolean 是布尔类型,其值是TRUE 或FALSE */
/* …………………….*/
#define MAX_VERTEX_NUM 20
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置*/
struct ArcNode *nextarc; /* 指向下一条弧的指针*/
InfoType *info; /* 网的权值指针) */
}ArcNode; /* 表结点*/
typedef struct
{
VertexType data; /* 顶点信息*/
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点*/
typedef struct
{
AdjList vertices;
int vexnum,arcnum; /* 图的当前顶点数和弧数*/
int kind; /* 图的种类标志*/
}ALGraph;
/* …………………….*/
/* …………………….*/
/*ALGraphAlgo.cpp 图的邻接表存储(存储结构由ALGraphDef.h 定义)的基本操作*/
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G 存在,u 和G 中顶点有相同特征*/
/* 操作结果: 若G 中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;iG.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4 种图) */
int i,j,k;
int w; /* 权值*/
VertexType va,vb;
ArcNode *p;
printf(“请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): “);
scanf(“%d”,(G.kind));
printf(“请输入图的顶点数,边数: “);
scanf(“%d,%d”,(G.vexnum),(G.arcnum));
printf(“请输入%d 个顶点的值(%d 个字符):\n”,G.vexnum,MAX_NAME);
for(i=0;iG.vexnum;++i) /* 构造顶点向量*/
{
scanf(“%s”,G.vertices[i].data);
G.vertices[i].firstarc=NULL;
}
if(G.kind==1||G.kind==3) /* 网*/
printf(“请顺序输入每条弧(边)的权值、弧尾和弧头(以空格作为间隔):\n”);
else /* 图*/
printf(“请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n”);
for(k=0;kG.arcnum;++k) /* 构造表结点链表*/
{
if(G.kind==1||G.kind==3) /* 网*/
scanf(“%d%s%s”,w,va,vb);
else /* 图*/
scanf(“%s%s”,va,vb);
i=LocateVex(G,va); /* 弧尾*/
j=LocateVex(G,vb); /* 弧头*/
p=(ArcNode*)malloc(sizeof(ArcNode));
p-adjvex=j;
if(G.kind==1||G.kind==3) /* 网*/
{
p-info=(int *)malloc(sizeof(int));
*(p-info)=w;
}
else
p-info=NULL; /* 图*/
p-nextarc=G.vertices[i].firstarc; /* 插在表头*/
G.vertices[i].firstarc=p;
if(G.kind=2) /* 无向图或网,产生第二个表结点*/
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p-adjvex=i;
if(G.kind==3) /* 无向网*/
{
p-info=(int*)malloc(sizeof(int));
*(p-info)=w;
}
else
p-info=NULL; /* 无向图*/
p-nextarc=G.vertices[j].firstarc; /* 插在表头*/
G.vertices[j].firstarc=p;
}
}
return OK;
}
void DestroyGraph(ALGraph G)
{ /* 初始条件: 图G 存在。操作结果: 销毁图G */
int i;
ArcNode *p,*q;
G.vexnum=0;
G.arcnum=0;
for(i=0;iG.vexnum;++i)
{
p=G.vertices[i].firstarc;
while(p)
{
q=p-nextarc;
if(G.kind%2) /* 网*/
free(p-info);
free(p);
p=q;
}
}
}
VertexType* GetVex(ALGraph G,int v)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点的序号。操作结果: 返回v 的值*/
if(v=G.vexnum||v0)
exit(ERROR);
return G.vertices[v].data;
}
int FirstAdjVex(ALGraph G,VertexType v)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点*/
/* 操作结果: 返回v 的第一个邻接顶点的序号。若顶点在G 中没有邻接顶点,则返回-1 */
ArcNode *p;
int v1;
v1=LocateVex(G,v); /* v1 为顶点v 在图G 中的序号*/
p=G.vertices[v1].firstarc;
if(p)
return p-adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{ /* 初始条件: 图G 存在,v 是G 中某个顶点,w 是v 的邻接顶点*/
/* 操作结果: 返回v 的(相对于w 的)下一个邻接顶点的序号。*/
/* 若w 是v 的最后一个邻接点,则返回-1 */
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v); /* v1 为顶点v 在图G 中的序号*/
w1=LocateVex(G,w); /* w1 为顶点w 在图G 中的序号*/
p=G.vertices[v1].firstarc;
while(pp-adjvex!=w1) /* 指针p 不空且所指表结点不是w */
p=p-nextarc;
if(!p||!p-nextarc) /* 没找到w 或w 是最后一个邻接点*/
return -1;
else /* p-adjvex==w */
return p-nextarc-adjvex; /* 返回v 的(相对于w 的)下一个邻接顶点的序号*/
}
Boolean visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void(*VisitFunc)(char* v); /* 函数变量(全局量) */
void DFS(ALGraph G,int v)
{ /* 从第v 个顶点出发递归地深度优先遍历图G。算法7.5 */
int w;
VertexType v1,w1;
strcpy(v1,*GetVex(G,v));
visited[v]=TRUE; /* 设置访问标志为TRUE(已访问) */
VisitFunc(G.vertices[v].data); /* 访问第v 个顶点*/
for(w=FirstAdjVex(G,v1);w=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 对v 的尚未访问的邻接点w 递归调用DFS */
}
void DFSTraverse(ALGraph G,void(*Visit)(char*))
{ /* 对图G 作深度优先遍历。算法7.4 */
int v;
VisitFunc=Visit; /* 使用全局变量VisitFunc,使DFS 不必设函数指针参数*/
for(v=0;vG.vexnum;v++)
visited[v]=FALSE; /* 访问标志数组初始化*/
for(v=0;vG.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 对尚未访问的顶点调用DFS */
printf(“\n”);
}
typedef int QElemType; /* 队列类型*/
#include”LinkQueueDef.h”
#include”LinkQueueAlgo.h”
void BFSTraverse(ALGraph G,void(*Visit)(char*))
{/*按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited。算法7.6 */
int v,u,w;
VertexType u1,w1;
LinkQueue Q;
for(v=0;vG.vexnum;++v)
visited[v]=FALSE; /* 置初值*/
InitQueue(Q); /* 置空的辅助队列Q */
for(v=0;vG.vexnum;v++) /* 如果是连通图,只v=0 就遍历全图*/
if(!visited[v]) /* v 尚未访问*/
{
visited[v]=TRUE;
Visit(G.vertices[v].data);
EnQueue(Q,v); /* v 入队列*/
while(!QueueEmpty(Q)) /* 队列不空*/
{
DeQueue(Q,u); /* 队头元素出队并置为u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w 为u 的尚未访问的邻接顶点*/
{
visited[w]=TRUE;
Visit(G.vertices[w].data);
EnQueue(Q,w); /* w 入队*/
}
}
}
printf(“\n”);
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{ case DG: printf(“有向图\n”); break;
case DN: printf(“有向网\n”); break;
case AG: printf(“无向图\n”); break;
case AN: printf(“无向网\n”);
}
printf(“%d 个顶点:\n”,G.vexnum);
for(i=0;iG.vexnum;++i)
printf(“%s “,G.vertices[i].data);
printf(“\n%d 条弧(边):\n”,G.arcnum);
for(i=0;iG.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
if(G.kind=1) /* 有向*/
{
printf(“%s→%s “,G.vertices[i].data,G.vertices[p-adjvex].data);
if(G.kind==DN) /* 网*/
printf(“:%d “,*(p-info));
}
else /* 无向(避免输出两次) */
{
if(ip-adjvex)
{
printf(“%s-%s “,G.vertices[i].data,G.vertices[p-adjvex].data);
if(G.kind==AN) /* 网*/
printf(“:%d “,*(p-info));
}
}
p=p-nextarc;
}
printf(“\n”);
}
}
/* …………………….*/
/* …………………….*/
#include “pubuse.h”
#define MAX_NAME 3 /* 顶点字符串的最大长度+1 */
typedef int InfoType; /* 存放网的权值*/
typedef char VertexType[MAX_NAME]; /* 字符串类型*/
#include”ALGraphDef.h”
#include”ALGraphAlgo.h”
void print(char *i)
{
printf(“%s “,i);
}
void main()
{
int i,j,k,n;
ALGraph g;
VertexType v1,v2;
printf(“请选择有向图\n”);
CreateGraph(g);
Display(g);
printf(“深度优先搜索的结果:\n”);
DFSTraverse(g,print);
printf(“广度优先搜索的结果:\n”);
BFSTraverse(g,print);
DestroyGraph(g); /* 销毁图*/
}
求有向网的关键路径c语言的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于c语言相对路径和绝对路径、求有向网的关键路径c语言的信息别忘了在本站进行查找喔。