1. (程序题) 有向无环图
对有向无环图，按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。
输入有向图的相关信息，若图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。
因拓扑有序序列不唯一，故要求如下：
（1）使用邻接表存储图。邻接表的每个链表中，要求按顶点的序号从大到小排列；
（2）使用栈辅助操作。初始时，入度为0的顶点入栈时，也按顶点的序号从大到小的顺序入栈。
输入说明：
输入有向图的顶点数、边数、各顶点的值，各边的信息。
输出说明：
若有向图中无环，输出其拓扑有序序列，否则输出“此有向图不是有向无环图”。
拓扑有序序列的每个顶点数据后有一个空格。
输入样例：
6 8
1 2 3 4 5 6
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5
输出样例：
1 3 2 6 4 5
代码实现
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>
#define MAX_VERTICES 50 //最大顶点数
#define GraphNodeDataType char //顶点类型
//邻接表节点
typedef struct GraphNode {
GraphNodeDataType vertex;//顶点
struct GraphNode* next;
}GraphNode;
//图结构
typedef struct Graph {
GraphNode* adjList[MAX_VERTICES];//邻接表数组
GraphNodeDataType vertex[MAX_VERTICES];//顶点数组
int indegree[MAX_VERTICES]; // 存储每个顶点的入度
int numVertices; // 图中顶点数
int numEdges; // 图中边数
}Graph;
//创建节点
GraphNode* createNode(char vertex) {
GraphNode* newNode = (GraphNode*)malloc(sizeof(GraphNode));
assert(newNode);
newNode->next = NULL;
newNode->vertex = vertex;
return newNode;
}
//创建图
Graph* createGraph(int numVertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
assert(graph);
graph->numVertices = numVertices;
graph->numEdges = 0;
for (int i = 0; i < numVertices; i++) {
graph->adjList[i] = NULL;// 邻接表数组初始化为空
graph->indegree[i] = 0;// 入度数组初始化为0
}
return graph;
}
int FindIndex(Graph* graph, char val) {
for (int i = 0; i < graph->numVertices; i++) {
if (graph->vertex[i] == val) {
return i;
}
}
return -1;
}
void addEdge(Graph* graph, char src, char dest) {
GraphNode* newNode = createNode(dest);//存储终点
int srcIndex = FindIndex(graph,src);
int destIndex = FindIndex(graph, dest);
newNode->next = graph->adjList[srcIndex];
graph->adjList[srcIndex] = newNode;
graph->indegree[destIndex]++;// 更新终点的入度
graph->indegree[destIndex];// 更新图的边数
}
//拓扑排序
void topologicalSort(Graph* graph) {
int visited[MAX_VERTICES] = { 0 };// 记录顶点是否被访问过的数组
int stack[MAX_VERTICES];//模拟栈
int top = -1;//栈顶指针
//将入度为0的顶点入栈
for (int i = graph->numVertices - 1; i >= 0; --i) {
if (graph->indegree[i] == 0) {
stack[++top] = i;//顶点入栈
visited[i] = 1;//标记顶点为已访问
}
}
int count = 0;//记录已输出的顶点数
while (top != -1) {
int vertexIndex = stack[top--];//出栈
printf("%c ", graph->vertex[vertexIndex]);
count++;
// 遍历该顶点的邻居节点
GraphNode* tmp = graph->adjList[vertexIndex];//获取当前顶点的邻接链表头指针
while (tmp != NULL) {
GraphNodeDataType adjVertex = tmp->vertex;// 获取邻居顶点值
int adjVertexIndex = FindIndex(graph,adjVertex);
graph->indegree[adjVertexIndex]--;// 更新邻居顶点的入度
// 如果邻居顶点入度为0且未访问过
if (graph->indegree[adjVertexIndex] == 0 && !visited[adjVertexIndex]) {
stack[++top] = adjVertexIndex;// 将邻居顶点入栈
visited[adjVertexIndex] = 1;// 标记顶点为已访问
}
tmp = tmp->next;
}
}
if (count != graph->numVertices) {
printf("此有向图不是有向无环图\n");
}
}
int main() {
int numVertices = 0;
int numEdges = 0;
scanf("%d %d", &numVertices, &numEdges);
Graph* graph = createGraph(numVertices);
for (int i = 0; i < numVertices; i++) {
char value = 0;
scanf(" %c", &graph->vertex[i]);
}
for (int i = 0; i < numEdges; ++i) { // 输入每条边的起点和终点
char src = 0, dest = 0;
scanf(" %c %c", &src, &dest);
addEdge(graph, src, dest); // 添加边，注意顶点值从a开始，转换为数组下标从0开始
}
topologicalSort(graph); // 进行拓扑排序
}
2. (程序题)
输入有向无环图的相关信息，求关键路径。
算法思路：
（1）使用邻接表存储图。邻接表的每个链表中，要求按顶点的序号从大到小排列；
（2）求DAG图的拓扑排序序列，使用栈辅助操作，初始时，入度为0的顶点入栈时，也按顶点的序号从大到小的顺序入栈；
（3）求每个事件的最早发生时间ve(i)；
（4）求每个事件的最迟发生时间vl(i)；
（5）求每个活动的最早开始时间e(i)和最迟开始时间l(i)，若e(i)等于l(i)，则此活动为关键活动。
输入说明：
输入有向图的顶点数、边数、各顶点的值，各边的信息。
输出说明：
输出所有关键活动，两个顶点用逗号间隔，且用尖括号括起来。所有标点符号为英文标点符号。
注意，因邻接表中链表内的按顶点的序号从大到小排列，所以会有如下输出顺序：
......
<4,7>
<4,6>
......
输入样例：
9 11
0 1 2 3 4 5 6 7 8
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
输出样例：
<0,1>
<1,4>
<4,7>
<4,6>
<6,8>
<7,8>
代码实现
#include<stdio.h>
#include<stdlib.h>
#define MAX_NODES 100 // 定义最大节点数
#define STACK_SIZE 20 // 定义栈的最大容量
// 定义边节点结构
typedef struct EdgeNode {
int targetIndex; // 目标节点索引
int weight; // 权重
struct EdgeNode* next; // 指向下一个边节点
} EdgeNode;
// 定义顶点节点结构
typedef struct VertexNode {
char label; // 顶点的数据（标签）
EdgeNode* edges; // 指向第一个边节点
} VertexNode, AdjacencyList[MAX_NODES];
// 定义图结构
typedef struct {
AdjacencyList vertices; // 顶点数组
int numVertices, numEdges; // 顶点数和边数
} Graph;
// 定义栈结构
typedef struct {
int* top, * base; // 栈顶和栈底指针
} Stack;
// 定义关键路径边结构
typedef struct {
char startVertex, endVertex; // 边的起点和终点
} CriticalEdge;
// 全局栈指针
Stack* globalStack = NULL;
// 查找节点索引
int findVertexIndex(Graph* graph, char label) {
int i = 0;
while (graph->vertices[i].label != label) i++;
return i;
}
// 从栈中弹出一个元素
int pop(Stack* stack) {
int value;
stack->top--;
value = *stack->top;
globalStack = stack;
return value;
}
// 将一个元素压入栈中
Stack* push(Stack* stack, int value) {
*stack->top = value;
stack->top++;
return stack;
}
int main() {
// 变量声明
Graph* graph;
EdgeNode* edge;
CriticalEdge* criticalEdges;
Stack* stack1, * stack2;
// 初始化栈
stack1 = (Stack*)malloc(sizeof(Stack));
stack1->base = stack1->top = (int*)malloc(sizeof(int) * STACK_SIZE);
stack2 = (Stack*)malloc(sizeof(Stack));
stack2->base = stack2->top = (int*)malloc(sizeof(int) * STACK_SIZE);
char tempChar, startLabel, endLabel;
int i, j, k, * inDegrees, vertexCount = 0, tempArray[100] = { 0 }, z = 0, weight, * earliest, * latest, duration, earliestTime, latestTime, criticalEdgeCount = 0, tempCount = 0;
// 初始化图
graph = (Graph*)malloc(sizeof(Graph));
scanf("%d %d", &graph->numVertices, &graph->numEdges);
scanf("%c", &tempChar); // 读取换行符
// 初始化入度数组和最早开始时间数组
inDegrees = (int*)malloc(sizeof(int) * (graph->numVertices));
earliest = (int*)malloc(sizeof(int) * (graph->numVertices));
latest = (int*)malloc(sizeof(int) * (graph->numVertices));
criticalEdges = (CriticalEdge*)malloc(sizeof(CriticalEdge) * (graph->numEdges));
for (i = 0; i < graph->numVertices; i++) inDegrees[i] = earliest[i] = 0;
// 读取顶点数据
for (i = 0; i < graph->numVertices; i++) {
scanf("%c%c", &graph->vertices[i].label, &tempChar);
graph->vertices[i].edges = NULL;
}
// 读取边数据
for (i = 0; i < graph->numEdges; i++) {
scanf("%c %c %d", &startLabel, &endLabel, &weight);
scanf("%c", &tempChar); // 读取换行符
j = findVertexIndex(graph, startLabel); // 获取起点索引
k = findVertexIndex(graph, endLabel); // 获取终点索引
edge = (EdgeNode*)malloc(sizeof(EdgeNode)); // 创建新边节点
edge->targetIndex = k;
edge->weight = weight;
edge->next = graph->vertices[j].edges;
graph->vertices[j].edges = edge;
}
// 计算每个节点的入度
for (i = 0; i < graph->numVertices; i++) {
for (edge = graph->vertices[i].edges; edge; edge = edge->next) {
inDegrees[edge->targetIndex]++;
}
}
// 初始化栈，将入度为0的节点入栈
for (i = graph->numVertices - 1; i >= 0; i--) {
if (inDegrees[i] == 0) stack1 = push(stack1, i);
}
// 拓扑排序
while (stack1->base != stack1->top) {
j = pop(stack1);
stack1 = globalStack;
stack2 = push(stack2, j);
vertexCount++;
// 更新最早开始时间
for (edge = graph->vertices[j].edges; edge; edge = edge->next) {
k = edge->targetIndex;
if (--inDegrees[k] == 0) stack1 = push(stack1, k);
if (earliest[j] + edge->weight > earliest[k]) earliest[k] = earliest[j] + edge->weight;
}
}
// 检查是否为有向无环图
if (vertexCount < graph->numVertices) {
printf("此有向图不是有向无环图");
}
else {
for (i = 0; i < graph->numVertices; i++) latest[i] = earliest[graph->numVertices - 1];
// 计算最晚开始时间
while (stack2->top != stack2->base) {
for (j = pop(stack2), edge = graph->vertices[j].edges; edge; edge = edge->next) {
k = edge->targetIndex;
if (latest[k] - edge->weight < latest[j]) latest[j] = latest[k] - edge->weight;
}
}
// 识别关键路径上的边
for (j = 0; j < graph->numVertices; j++) {
for (edge = graph->vertices[j].edges; edge; edge = edge->next) {
k = edge->targetIndex;
duration = edge->weight;
earliestTime = earliest[j];
latestTime = latest[k] - duration;
if (earliestTime == latestTime) {
criticalEdges[criticalEdgeCount].startVertex = graph->vertices[j].label;
criticalEdges[criticalEdgeCount].endVertex = graph->vertices[k].label;
criticalEdgeCount++;
}
}
}
}
// 打印关键路径
j = 0;
while (j != graph->numVertices - 1) {
for (i = 0; i < criticalEdgeCount; i++) {
if (criticalEdges[i].startVertex == graph->vertices[j].label) {
printf("<%c,%c>\n", criticalEdges[i].startVertex, criticalEdges[i].endVertex);
weight = i;
tempCount++;
}
}
j = findVertexIndex(graph, criticalEdges[weight].endVertex);
}
if (criticalEdgeCount == tempCount);
else {
printf("<%c,%c>", criticalEdges[criticalEdgeCount - 1].startVertex, criticalEdges[criticalEdgeCount - 1].endVertex);
}
return 0;
}
