怎么查看网站的外链,众筹网站开发分析报告,黄页推广引流网站,网站可兼容移动端目录
前言
AOE网
1.相关概念
2.AOE网特征
拓扑排序
1.基本概念
2.方法步骤 3.拓扑排序的应用
拓扑排序代码实现
1.邻接矩阵的代码
2.邻接表代码 前言 今天我们学习图的应用----拓扑排序#xff0c;说到排序#xff0c;你们是不是会想到冒泡排序#xff0c;插入排序… 目录
前言
AOE网
1.相关概念
2.AOE网特征
拓扑排序
1.基本概念
2.方法步骤 3.拓扑排序的应用
拓扑排序代码实现
1.邻接矩阵的代码
2.邻接表代码 前言 今天我们学习图的应用----拓扑排序说到排序你们是不是会想到冒泡排序插入排序快速排序等等排序方法但是拓扑排序跟这些不一样拓扑排序是属于图的一种遍历算法不属于用于纯数字排序那什么是拓扑排序呢下面就一起来看看吧
AOE网
1.相关概念 有向无环图常用来描述一个工程或系统的进行过程。(通常把计划、施工、生产、程序流程等当成是一个工程 一个工程可以分为若干个子工程只要完成了这些子工程活动)就可以导致整个工程的完成。 AOV网 用一个有向图表示一个工程的各子工程及其相互制约的关系其中以顶点表示活动弧表示活动之间的优先制约关系称这种有向图为顶点表示活动的网简称AOV网(Activity On Vertex network)。 如图所示做出AOE网 2.AOE网特征
若从i到j有一条有向路径则i是j的前驱i是i的后继。若ij 是网中有向边则i是j的直接前驱;j是i的直接后继AOV 网中不允许有回路因为如果有回路存在则表明某项活动以自己为先决条件显然这是荒谬的。
拓扑排序
1.基本概念 在AOV 网没有回路的前提下我们将全部活动排列成一个线性序列使得若AOV 网中有弧 ij存在则在这个序列中i一定排在的前面具有这种性质的线性序列称为拓扑有序序列相应的拓扑有序排序的算法称为拓扑排序 拓扑排序是对一个有向图构造拓扑序列解决工程是否能顺利进行的问题。构造时有 2 种结果 此图全部顶点被输出说明说明图中无「环」存在 是 AOV 网 没有输出全部顶点说明图中有「环」存在不是 AOV 网 形象化理解
排序类似 流程图一样 任务
例如早上起床的任务
例如这里你只有穿了衬衣才能穿外套而不是穿了外套再穿衬衣 2.方法步骤 在有向图中选一个没有前驱的顶点且输出之从图中删除该顶点和所有以它为尾的弧重复上述两步直至全部顶点均已输出:或者当图中不存在无前驱的顶点为止 示例1 示例2 3.拓扑排序的应用 检测AOV网中是否存在环方法: 对有向图构造其顶点的拓扑有序序列若网中所有顶点都在它的拓扑有序序列中则该AOV 网必定不存在环。 拓扑排序代码实现
图的存储方式有两种邻接矩阵和邻接表下面我就分别给出了这两种储存方式的代码写法。
1.邻接矩阵的代码
邻接矩阵结构如下
#define Maxint 32767
#define Maxnum 100//最大顶点数//数据类型
typedef struct datatype {char id[10];//……
}
ElemType;
//图的邻接数组
typedef struct graph {ElemType vexs[Maxnum];//图数据int matrix[Maxnum][Maxnum];//二维数组矩阵int vexnum;//点数int arcnum;//边数
}Graph;
拓扑排序代码
//拓扑排序
void Topo_sort(Graph G) {int n G.vexnum;int* result (int*)malloc(sizeof(int) * n);//储存结果int* indegree (int*)malloc(sizeof(int) * n);//入度int*queue (int*)malloc(sizeof(int) * n);//队列,储存下标//初始化for (int i 0; i n; i) {result[i] -1;indegree[i] 0;queue[i] -1;}int que_count 0;int count 0;//统计每一个顶点的入度for (int x 0; x n; x) {for (int y 0; y n; y) {if (G.matrix[y][x] ! 0 G.matrix[y][x] ! Maxint)indegree[x];}}//把入度为0的顶点放入队列for (int i 0; i n; i) {if (indegree[i] 0) {queue[que_count] i;que_count;}}//后继处理while (que_count 0) {//出队操作int pop queue[0];for (int j 0; j que_count-1; j) {queue[j] queue[j 1];}que_count--;result[count] pop;for (int i 0; i n; i) {if (G.matrix[pop][i] ! 0 G.matrix[pop][i] ! Maxint) {indegree[i]--;//把与这个出队的顶点相连的后继顶点入度都-1//以上操作完成了之后如果还有入度为0的顶点就进入到队列当中if (indegree[i] 0) queue[que_count] i;}}}printf(拓扑排序结果:\n);for (int k 0; k n; k) {printf(%s-, G.vexs[result[k]].id);}printf(end\nprint over!\n);//释放空间free(result);free(indegree);free(queue);result queue indegree NULL;
}
2.邻接表代码
队列头文件.h代码:
#pragma once
#includestdio.h
#includestring.h
#include stdbool.h
#includeassert.h//数据结构体
typedef struct datatype {char id[10];//字符串编号//………………
}ElemType;//定义节点
typedef struct node {ElemType data;struct node* next;
}Node;
//定义队列
typedef struct queue {int count; //计数Node* front;//指向队头指针Node* rear;//指向队尾指针
}Queue;void Queue_init(Queue* queue);//初始化
bool isEmpty(Queue* queue);//判空
void enQueue(Queue* queue, ElemType data);//入队
Node* deQueue(Queue* queue);//出队
ElemType head_data(Queue queue);//获取队头数据队列源文件代码.c
#includequeue.h//初始化
void Queue_init(Queue* queue) {assert(queue);queue-front NULL;queue-rear NULL;queue-count0;
}//创建节点
Node* create_node(ElemType data) {Node* new_node (Node*)malloc(sizeof(Node));if (new_node) {new_node-data data;new_node-next NULL;return new_node;}else{printf(ERRPR\n);}
}//判断是否空队列
bool isEmpty(Queue* queue) {assert(queue);if (queue-count 0){return true;}return false;
}//入队
void enQueue(Queue* queue, ElemType data) {assert(queue);Node* new_node create_node(data);if (queue-rear NULL queue-front NULL ) {queue-front new_node;queue-rear new_node;queue-count;}else{queue-rear-next new_node;queue-rear new_node;queue-count;}}//出队
Node* deQueue(Queue* queue) {assert(queue);if (!isEmpty(queue)) {Node* deNode;if (queue-count 1) {deNode queue-front;queue-front NULL;queue-rear NULL;}else {deNode queue-front;queue-front deNode-next;}queue-count--;return deNode;}printf(error\n);return NULL;
}//获取队头数据
ElemType head_data(Queue queue) {return queue.front-data;
}拓扑排序代码
//数据结构体
typedef struct datatype {char id[10];//字符串编号//………………
}ElemType;
//边节点存储结构
typedef struct arcnode {int index;//指向顶点的位置int weight;//权struct arcnode* nextarc;//指向下一个边节点
}Anode;
//顶点结点存储结构
typedef struct vexnode {ElemType data;Anode* firstarc;
}Vhead;
//图结构
typedef struct {Vhead* vertices;int vexnum;int arcnum;
}Graph;//拓扑排序邻接表
void Topo_sort(Graph G) {int* inarry (int*)malloc(sizeof(int) * G.vexnum);//统计每一个顶点的入度int* result (int*)malloc(sizeof(int) * G.vexnum);//储存遍历结果//初始化for (int j 0; j G.vexnum; j) {inarry[j] 0;result[j] -1;}Queue que;Queue_init(que);//统计每个顶点的入度情况for (int i 0; i G.vexnum; i) {Anode* p G.vertices[i].firstarc;while (p) {inarry[p-index];p p-nextarc;}}//把入度为0的节点放入队列for (int i 0; i G.vexnum; i) {if (inarry[i] 0)enQueue(que, G.vertices[i].data);}int count 0;while (!isEmpty(que)) {//出队操作Node* pop deQueue(que);int pop_index Locate_vex(G, pop-data.id);result[count] pop_index;//存入结果当中free(pop);pop NULL;Anode* cur G.vertices[pop_index].firstarc;while (cur) {//把与出队的顶点关联的点入度-1inarry[cur-index]--;//如果减掉入度之后入度为0的话就入队if (inarry[cur-index] 0)enQueue(que, G.vertices[cur-index].data);cur cur-nextarc;}}printf(拓扑排序结果:\n);for (int i 0; i count; i) {printf(%s-, G.vertices[result[i]].data.id);}printf(end\nprintf over!\n);//释放空间;free(inarry);free(result);inarry result NULL;
}
以上就是本期的全部内容了我们下次见
分享一张壁纸