数据结构图的应用-关键路径(有向图+邻接表存储结构+C语言代码)-附带终端输入+图片
数据结构图的应用关键路径代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<stdbool.h>
#define MVNum 100
//图的邻接表
typedef struct ArcNode
{
int adjvex;//顶点
int weight;//权值
struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode
{
char data;
ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct
{
AdjList vertices;//邻接表
AdjList converse_vertices;//逆邻接表
int vexnum, arcnum;
}ALGraph;
//顺序栈的结构体
typedef struct
{
int* base;
int* top;
int stacksize;
}spStack;
//全局变量
spStack S;
int indegree[MVNum];//数组indegree存放个顶点的入度
int ve[MVNum];//vi的最早发生时间
int vl[MVNum];//vi的最迟发生时间
int topo[MVNum];//记录拓扑排序的顶点顺序
//栈的初始化
void InitStack(spStack* S)
{
S->base = (int*)malloc(sizeof(int) * MVNum);
if (!S->base)
{
exit(1);
}
S->top = S->base;
S->stacksize = MVNum;
}
//入栈
void Push(spStack* S, int i)
{
if (S->top - S->base == S->stacksize)
{
return;
}
*S->top++ = i;
}
//出栈
void Pop(spStack* S, int* i)
{
if (S->top == S->base)
{
return;
}
*i = *--S->top;
}
bool StackEmpty(spStack S)
{
if (S.top == S.base)
{
return true;//为空返回对
}
return false;
}
int Locate(ALGraph G,char u)
{
int i;
for (i = 0; i < G.vexnum; i++)
{
if (G.vertices[i].data == u)
{
return i;
}
}
return -1;
}
//创建邻接表
int CreateUDG(ALGraph* G)
{
int i, k;
printf("请输入顶点数+边数\n");
scanf("%d %d", &G->vexnum, &G->arcnum);
getchar();
printf("请输入顶点的信息\n");
for (i = 0; i < G->vexnum; i++)
{
printf("请输入第%d个顶点:", i + 1);
scanf(" %c", &G->vertices[i].data);
G->converse_vertices[i].data = G->vertices[i].data;
G->vertices[i].firstarc = NULL;
G->converse_vertices[i].firstarc = NULL;
}
printf("请输入边依附的顶点以及权值\n");
for (k = 0; k < G->arcnum; k++)
{
char v1, v2;
int i, j, w;
printf("请输入第%d条边依附的顶点和权值:",k+1);
scanf(" %c %c %d", &v1, &v2, &w);
i = Locate(*G, v1);
j = Locate(*G, v2);
//邻接表的边表插入(出度)
ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode));
p1->adjvex = j;
p1->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p1;
p1->weight = w;
//逆邻接表的边表插入（入度）
ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode));
p2->adjvex = i;
p2->nextarc = G->converse_vertices[j].firstarc;
G->converse_vertices[j].firstarc = p2;
p2->weight = w;
}
return 1;
}
void FindInDegree(ALGraph G)
{
int i, count;
//将入度存储到indegree
for (i = 0; i < G.vexnum; i++)
{
count = 0;
ArcNode* p = G.converse_vertices[i].firstarc;
while (p)
{
p = p->nextarc;
count++;
}
indegree[i] = count;
}
}
int TopologicalOrder(ALGraph G, int topo[])
{
int m;
//统计入度函数
FindInDegree(G);
InitStack(&S);
//把入度为0的进栈
for (int i = 0; i < G.vexnum; i++)
{
if (indegree[i] == 0)
{
Push(&S, i);
}
}
m = 0;//统计顶点数
while (!StackEmpty(S))
{
int i;
Pop(&S, &i);
topo[m] = i;
m++;
ArcNode* p = G.vertices[i].firstarc;
while (p)
{
int k = p->adjvex;//3 2 1
--indegree[k];//顶点被取出，指向它的相邻的顶点的入度-1
if (indegree[k] == 0)
{
Push(&S, k);
}
p = p->nextarc;
}
}
if (m<G.vexnum)
{
return 0;
}
else {
return 1;
}
}
int CriticalPath(ALGraph G)
{
int n, i, k, j, e, l;
//调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR
if (!TopologicalOrder(G,topo))
{
return 0;
}
n = G.vexnum;
for (i = 0; i < n; i++)
{
ve[i] = 0;//最早开始时间数组置为0
}
/*――――――――――按拓扑次序求每个事件的最早发生时间－――――－―――――*/
for (i = 0; i < n; i++)
{
k = topo[i];//第一个肯定是0
ArcNode* p = G.vertices[k].firstarc;
//从0出发对0-1 0-2 0-3的权值赋值
while (p)
{
j = p->adjvex;//3 2 1
if (ve[j] < ve[k]+p->weight)//MAX[ve(0)+wij];
{
ve[j] = ve[k] + p->weight;//7
}
p = p->nextarc;//2 1
}
}
//全部权值置为18
for (i = 0; i < n; i++)
{
vl[i] = ve[n - 1];
}
/*――――――――――按逆拓扑次序求每个事件的最迟发生时间－――――－―――――*/
for (i = n - 1; i >= 0; i--)//8->0
{
k = topo[i];//8 7
ArcNode* p = G.vertices[k].firstarc;
while (p)//i = 8跳过
{
j = p->adjvex;//8
if (vl[k] > vl[j] - p->weight)
{
vl[k] = vl[j] - p->weight;
}
p = p->nextarc;
}
}
/*――――――――――――判断每一活动是否为关键活动－――――――－―――――*/
printf("关键路径为: ");
for (i = 0; i < n; i++)
{
ArcNode* p = G.vertices[i].firstarc;
while (p)
{
j = p->adjvex;// 3
e = ve[i];//取出0的最早开始时间
l = vl[j] - p->weight;//取出当前j的最迟开始时间
if (e == l)
{
printf(" %c --> %c ", G.vertices[i].data, G.vertices[j].data);
}
p = p->nextarc;
}
}
return 1;
}
int main()
{
printf("************算法6.13 关键路径算法**************\n");
ALGraph G;
CreateUDG(&G);
CriticalPath(G);
return 0;
}数据结构图的应用关键路径图片如下：
数据结构图的应用关键路径终端输入如下：
请输入顶点+边数
9 11
请输入顶点的信息
请输入第1个顶点：0
请输入第2个顶点：1
请输入第3个顶点：2
请输入第4个顶点：3
请输入第5个顶点：4
请输入第6个顶点：5
请输入第7个顶点：6
请输入第8个顶点：7
请输入第9个顶点：8
请输入(vi,vj)以及权值
请输入第1条边的顶点和权值:0 1 6
请输入第2条边的顶点和权值:0 2 4
请输入第3条边的顶点和权值:0 3 5
请输入第4条边的顶点和权值:1 4 1
请输入第5条边的顶点和权值:2 4 1
请输入第6条边的顶点和权值:3 5 2
请输入第7条边的顶点和权值:4 6 9
请输入第8条边的顶点和权值:4 7 7
请输入第9条边的顶点和权值:5 7 4
请输入第10条边的顶点和权值:6 8 2
请输入第11条边的顶点和权值:7 8 4
关键路径为： 0 -> 1 1 -> 4 4 -> 7 4 -> 6 6 -> 8 7 -> 8