数据结构学习第二十一天

23:34:47 2019-09-06

学校未开课继续接着暑假学习

PTA第21题 Prim最小树生成

  1 #define _CRT_SECURE_NO_WARNINGS  
  2 #include<stdio.h>
  3 #include<malloc.h>
  4 #define INIFITY 65635
  5 
  6 typedef int Vertex;
  7 typedef struct ENode* Edge;
  8 struct ENode
  9 {
 10     Vertex    V1, V2;
 11     int Weight;
 12 };
 13 
 14 typedef struct Graph* MGraph;
 15 struct Graph
 16 {
 17     int Nv;
 18     int Ne;
 19     int G[1001][1001];
 20 };
 21 
 22 MGraph CreateGraph(int VertexNum)
 23 {
 24     MGraph Graph = (MGraph)malloc(sizeof(struct Graph));
 25     Graph->Nv = VertexNum;
 26     Graph->Ne = 0;
 27     for (int i = 0; i < Graph->Nv; i++)
 28         for (int j = 0; j < Graph->Nv; j++)
 29             Graph->G[i][j] = INIFITY;
 30     return Graph;
 31 }
 32 
 33 void Insert(MGraph Graph, Edge E)
 34 {
 35     Graph->G[E->V1][E->V2] = E->Weight;
 36     Graph->G[E->V2][E->V1] = E->Weight;
 37 }
 38 
 39 MGraph BuildGraph()
 40 {
 41     int Nv;
 42     Edge E;
 43     scanf("%d", &Nv);
 44     MGraph Graph = CreateGraph(Nv);
 45     scanf("%d
", &(Graph->Ne));
 46     for (int i = 0; i < Graph->Ne; i++)
 47     {
 48         E = (Edge)malloc(sizeof(struct ENode));
 49         scanf("%d %d %d
", &(E->V1), &(E->V2), &(E->Weight));
 50         Insert(Graph, E);
 51     }
 52     return Graph;
 53 }
 54 
 55 int IsEdge(MGraph Graph, Vertex V, Vertex W)
 56 {
 57     return (Graph->G[V][W] < INIFITY) ? 1 : 0;
 58 }
 59 //利用Prim算法 解决最小生成树的问题
 60 
 61 int Dist[1001];  //表示某点到树的距离
 62 int Parent[1001];
 63 int TotalWeight;    //表示总的成本
 64 int VCount;  //表示收录的点数
 65 int FindMinDist(MGraph Graph)
 66 {
 67     int MinDist = INIFITY;
 68     int MinV;
 69     for (int i = 0; i < Graph->Nv; i++)
 70     {
 71         if (Dist[i]!=-1&& Dist[i] < MinDist)
 72         {
 73             MinDist = Dist[i];
 74             MinV = i;
 75         }
 76     }
 77     if (MinDist < INIFITY)
 78         return MinV;
 79     else
 80         return 0;
 81 }
 82 int Prim(MGraph Graph, Vertex S)
 83 {
 84     for (int i = 0; i < Graph->Nv; i++)
 85     {
 86         Dist[i] = Graph->G[S][i];
 87         if (Dist[i] < INIFITY)
 88             Parent[i] = S;
 89         else
 90             Parent[i] = -1;
 91     }
 92     Dist[S] = -1;
 93     Parent[S] = -1;
 94     VCount++;
 95     while (1)
 96     {
 97         int V = FindMinDist(Graph);
 98         if (!V)
 99             break;
100         TotalWeight += Dist[V];
101         Dist[V] = -1;
102         VCount++;
103         for (int i = 0; i < Graph->Nv; i++)
104         {
105             if (Dist[i]!=-1&& IsEdge(Graph, V, i))
106             {
107                 if (Graph->G[V][i] < Dist[i])
108                 {
109                     Dist[i] = Graph->G[V][i];
110                     Parent[i] = V;
111                 }
112             }
113         }
114     }
115     if (VCount <Graph->Nv)
116         return -1;
117     else
118         return TotalWeight;
119 }
120 int main()
121 {
122     MGraph Graph = BuildGraph();
123     printf("%d", Prim(Graph, 0));
124     return 0;
125 }

View Code

拓扑排序

拓扑序:如果图中从V到W有一条有向路径,则V一定排在W之前.满足此条件的顶点序列称为一个拓扑序

获得一个拓扑序的过程就是拓扑排序

AOV(Acitivity On Vertex)网络如果有合理的拓扑序,则必定是有向无环图(Directed Acyclic Graph,DAG)

关键路径问题(拓扑排序应用)

AOE(Acitivity On Edge)网络（os:PTA上有道题看了我好长时间都不会。。果然我不看教程就啥也不会)

　　一般用于安排项目的工序

关键路径问题中

最短时间

$Earliest[0]=0; \ Earliest[j]=mathop{max}limits_{<i,j>in E} {Earliest[i]+C_<i,j>}$

在保证最短时间下计算机动时间

机动时间: $D_<i,j>=Latest[j]-Earliest[i]-C_<i,j>$

$Latest[Last]=Earliest[Last]$ //Last表示最后一个节点

$Latest[i]=mathop{min}limits_{<i,j>in E} {Earlist[j]-C_<i,j>}$

关键路径由绝对不允许延误的活动组成的路径(没有机动时间)

拓扑排序

  1 #define _CRT_SECURE_NO_WARNINGS  
  2 #include<stdio.h>
  3 #include<malloc.h>
  4 //表示图的两种方法
  5 //邻接矩阵 G[N][N] N个顶点从0到N-1编号
  6 //邻接表 表示
  7 /*Graph Create();  //建立并返回空图
  8 Graph InsertVertex(Graph G, Vertex v); //将v插入G
  9 Graph InsertEdge(Graph G, Edge e); //将e插入G
 10 void DFS(Graph G, Vertex v); //从顶点v出发深度优先遍历图G
 11 void BFS(Graph G, Vertex v); //从顶点v出发宽度优先遍历图G
 12 void ShortestPath(Graph G, Vertex v, int Dist[]); //计算图G中顶点v到任意其它顶点的最短距离
 13 void MST(Graph G); //计算图G的最小生成树*/
 14 //图的邻接表表示法
 15 #define MaxVerterNum 100    //最大顶点数
 16 #define INFINITY 65535        //
 17 typedef int Vertex;            //顶点下标表示顶点
 18 typedef int WeightType;        //边的权值
 19 typedef char DataType;        //顶点存储的数据类型
 20 
 21 //边的定义
 22 typedef struct ENode* PtrToENode;
 23 typedef PtrToENode Edge;
 24 struct ENode
 25 {
 26     Vertex V1, V2; //有向边<V1,V2>
 27     WeightType Weight;  //权重
 28 };
 29 
 30 //邻接点的定义
 31 typedef struct AdjVNode* PtrToAdjVNode;
 32 struct AdjVNode
 33 {
 34     Vertex AdjV;  //邻接点下标
 35     WeightType Weight; //边权重
 36     PtrToAdjVNode Next; //指向下一个邻接点的指针
 37 };
 38 
 39 //顶点表头节点的定义
 40 typedef struct Vnode
 41 {
 42     PtrToAdjVNode FirstEdge;  //边表头指针
 43     DataType Data;            //存顶点的数据
 44     int Indegree;            //入度
 45 }AdjList[MaxVerterNum];        //AdjList是邻接表类型
 46 
 47 //图节点的定义
 48 typedef struct GNode* PtrToGNode;
 49 typedef PtrToGNode LGraph;
 50 struct GNode
 51 {
 52     int Nv;  //顶点数
 53     int Ne;  //边数
 54     AdjList G;  //邻接表
 55 };
 56 
 57 LGraph CreateGraph(int VertexNum)
 58 {//初始化一个有VertexNum个顶点但没有边的图
 59     Vertex V;
 60     LGraph Graph;
 61 
 62     Graph = (LGraph)malloc(sizeof(struct GNode)); //建立图
 63     Graph->Nv = VertexNum;
 64     Graph->Ne = 0;
 65     //初始化邻接表头指针
 66     for (V = 0; V < Graph->Nv; V++)
 67         Graph->G[V].FirstEdge = NULL;
 68     return Graph;
 69 }
 70 void InsertEdge(LGraph Graph, Edge E)
 71 {
 72     PtrToAdjVNode NewNode;
 73     //插入边<V1,V2>
 74     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 75     NewNode->AdjV = E->V2;
 76     NewNode->Weight = E->Weight;
 77     NewNode->Next = Graph->G[E->V1].FirstEdge;
 78     Graph->G[E->V1].FirstEdge = NewNode;
 79     Graph->G[E->V2].Indegree++;
 80 
 81     //若是无向图 还要插入边<V2,V1>
 82     /*NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 83     NewNode->AdjV = E->V1;
 84     NewNode->Weight = E->Weight;
 85     NewNode->Next = Graph->G[E->V2].FirstEdge;
 86     Graph->G[E->V2].FirstEdge = NewNode;*/
 87 }
 88 LGraph BuildGraph()
 89 {
 90     LGraph Graph;
 91     Edge E;
 92     Vertex V;
 93     int Nv, i;
 94 
 95     scanf("%d", &Nv);   /* 读入顶点个数 */
 96     Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */
 97     scanf("%d", &(Graph->Ne));  //读入边数
 98     if (Graph->Ne != 0)
 99     {
100         E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
101         /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
102         for (i = 0; i < Graph->Ne; i++)
103         {
104             scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
105             InsertEdge(Graph, E);
106         }
107     }
108     /* 如果顶点有数据的话，读入数据 */
109     for (V = 0; V < Graph->Nv; V++)
110         scanf(" %c", &(Graph->G[V].Data));
111     return Graph;
112 }
113 
114 #define Size 100
115 int Queue[Size];
116 int Front = 1;
117 int Rear = 0;
118 int size = 0;
119 int Succ(int Num)
120 {
121     if (Num < Size)
122         return Num;
123     else
124         return 0;
125 }
126 void EnQueue(int Num)
127 {
128     Rear = Succ(Rear + 1);
129     Queue[Rear] = Num;
130     size++;
131 }
132 int DeQueue()
133 {
134     int Num = Queue[Front];
135     Front = Succ(Front + 1);
136     size--;
137     return Num;
138 }
139 int IsEmpty()
140 {
141     return (size == 0) ? 1 : 0;
142 }
143 
144 //利用邻接表实现拓扑排序
145 int TopOrder[100];  //顺序存储排序后的顶点下标
146 int TopSort(LGraph Graph)
147 {        //对Graph进为拓扑排序 ,TopOrder[] 顺序存储排序后的顶点下标
148     int Indegree[100];
149     int cnt = 0;
150     for (int i = 0; i < Graph->Nv; i++)    //初始化Indegree
151         Indegree[i] = 0;
152     for(int i=0;i<Graph->Nv;i++)
153         for (PtrToAdjVNode W = Graph->G[i].FirstEdge; W; W = W->Next)
154         {
155             Indegree[W->AdjV]++;
156         }
157     for (int i = 0; i < Graph->Nv; i++)
158         if (Indegree[i] == 0)
159             EnQueue(i);
160 
161     //进入拓扑排序
162     while (!IsEmpty())
163     {
164         int V = DeQueue();
165         TopOrder[cnt++] = V;
166         for (PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W = W->Next)
167             if (--Indegree[W->AdjV] == 0)
168                 EnQueue(W->AdjV);
169     }
170     if (cnt != Graph->Nv)
171         return 0;
172     else
173         return 1;
174 }

View Code

PTA 第22题拓扑排序(关键路径) 注意关键路径找完成时间时取所有中最大值

  1 #define _CRT_SECURE_NO_WARNINGS  
  2 #include<stdio.h>
  3 #include<malloc.h>
  4 //表示图的两种方法
  5 //邻接矩阵 G[N][N] N个顶点从0到N-1编号
  6 //邻接表 表示
  7 /*Graph Create();  //建立并返回空图
  8 Graph InsertVertex(Graph G, Vertex v); //将v插入G
  9 Graph InsertEdge(Graph G, Edge e); //将e插入G
 10 void DFS(Graph G, Vertex v); //从顶点v出发深度优先遍历图G
 11 void BFS(Graph G, Vertex v); //从顶点v出发宽度优先遍历图G
 12 void ShortestPath(Graph G, Vertex v, int Dist[]); //计算图G中顶点v到任意其它顶点的最短距离
 13 void MST(Graph G); //计算图G的最小生成树*/
 14 //图的邻接表表示法
 15 #define MaxVerterNum 100    //最大顶点数
 16 #define INFINITY 65535        //
 17 typedef int Vertex;            //顶点下标表示顶点
 18 typedef int WeightType;        //边的权值
 19 typedef char DataType;        //顶点存储的数据类型
 20 
 21 //边的定义
 22 typedef struct ENode* PtrToENode;
 23 typedef PtrToENode Edge;
 24 struct ENode
 25 {
 26     Vertex V1, V2; //有向边<V1,V2>
 27     WeightType Weight;  //权重
 28 };
 29 
 30 //邻接点的定义
 31 typedef struct AdjVNode* PtrToAdjVNode;
 32 struct AdjVNode
 33 {
 34     Vertex AdjV;  //邻接点下标
 35     WeightType Weight; //边权重
 36     PtrToAdjVNode Next; //指向下一个邻接点的指针
 37 };
 38 
 39 //顶点表头节点的定义
 40 typedef struct Vnode
 41 {
 42     PtrToAdjVNode FirstEdge;  //边表头指针
 43     DataType Data;            //存顶点的数据
 44     int Indegree;            //入度
 45 }AdjList[MaxVerterNum];        //AdjList是邻接表类型
 46 
 47 //图节点的定义
 48 typedef struct GNode* PtrToGNode;
 49 typedef PtrToGNode LGraph;
 50 struct GNode
 51 {
 52     int Nv;  //顶点数
 53     int Ne;  //边数
 54     AdjList G;  //邻接表
 55 };
 56 
 57 LGraph CreateGraph(int VertexNum)
 58 {//初始化一个有VertexNum个顶点但没有边的图
 59     Vertex V;
 60     LGraph Graph;
 61 
 62     Graph = (LGraph)malloc(sizeof(struct GNode)); //建立图
 63     Graph->Nv = VertexNum;
 64     Graph->Ne = 0;
 65     //初始化邻接表头指针
 66     for (V = 0; V < Graph->Nv; V++)
 67         Graph->G[V].FirstEdge = NULL;
 68     return Graph;
 69 }
 70 void InsertEdge(LGraph Graph, Edge E)
 71 {
 72     PtrToAdjVNode NewNode;
 73     //插入边<V1,V2>
 74     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 75     NewNode->AdjV = E->V2;
 76     NewNode->Weight = E->Weight;
 77     NewNode->Next = Graph->G[E->V1].FirstEdge;
 78     Graph->G[E->V1].FirstEdge = NewNode;
 79     Graph->G[E->V2].Indegree++;
 80 
 81     //若是无向图 还要插入边<V2,V1>
 82     /*NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 83     NewNode->AdjV = E->V1;
 84     NewNode->Weight = E->Weight;
 85     NewNode->Next = Graph->G[E->V2].FirstEdge;
 86     Graph->G[E->V2].FirstEdge = NewNode;*/
 87 }
 88 LGraph BuildGraph()
 89 {
 90     LGraph Graph;
 91     Edge E;
 92     Vertex V;
 93     int Nv, i;
 94 
 95     scanf("%d", &Nv);   /* 读入顶点个数 */
 96     Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */
 97     scanf("%d", &(Graph->Ne));  //读入边数
 98     if (Graph->Ne != 0)
 99     {
100         E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */
101         /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
102         for (i = 0; i < Graph->Ne; i++)
103         {
104             scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
105             InsertEdge(Graph, E);
106         }
107     }
108     return Graph;
109 }
110 
111 #define Size 100
112 int Queue[Size];
113 int Front = 1;
114 int Rear = 0;
115 int size = 0;
116 int Succ(int Num)
117 {
118     if (Num < Size)
119         return Num;
120     else
121         return 0;
122 }
123 void EnQueue(int Num)
124 {
125     Rear = Succ(Rear + 1);
126     Queue[Rear] = Num;
127     size++;
128 }
129 int DeQueue()
130 {
131     int Num = Queue[Front];
132     Front = Succ(Front + 1);
133     size--;
134     return Num;
135 }
136 int IsEmpty()
137 {
138     return (size == 0) ? 1 : 0;
139 }
140 
141 //利用邻接表实现拓扑排序
142 int TopOrder[100];  //顺序存储排序后的顶点下标
143 int Earliest[100];
144 int TopSort(LGraph Graph)
145 {        //对Graph进为拓扑排序 ,TopOrder[] 顺序存储排序后的顶点下标
146     int Indegree[100];
147     int cnt = 0;
148     for (int i = 0; i < Graph->Nv; i++)    //初始化Indegree
149         Indegree[i] = 0;
150     for (int i = 0; i < Graph->Nv; i++)
151         for (PtrToAdjVNode W = Graph->G[i].FirstEdge; W; W = W->Next)
152         {
153             Indegree[W->AdjV]++;
154         }
155     for (int i = 0; i < Graph->Nv; i++)
156         if (Indegree[i] == 0)
157         {
158             EnQueue(i);
159             Earliest[i] = 0;
160         }
161     //进入拓扑排序
162     while (!IsEmpty())
163     {
164         int V = DeQueue();
165         TopOrder[cnt++] = V;
166         for (PtrToAdjVNode W = Graph->G[V].FirstEdge; W; W = W->Next)
167         {
168             if (--Indegree[W->AdjV] == 0)
169             {
170                 if ((Earliest[V] + W->Weight) > Earliest[W->AdjV])
171                     Earliest[W->AdjV] = Earliest[V] + W->Weight;
172                 EnQueue(W->AdjV);
173             }
174         }
175     }
176     if (cnt != Graph->Nv)
177         return 0;
178     else
179     {
180         int Max=-1;
181         int V;
182         for (int i = 0; i < Graph->Nv; i++)
183         {
184             if (Earliest[i]>Max)
185             {
186                 Max = Earliest[i];
187                 V = i;
188             }
189         }
190         return Max;
191     }
192 }
193 
194 int main()
195 {
196     LGraph Graph = BuildGraph();
197     int Sum;
198     if (!(Sum = TopSort(Graph)))
199         printf("Impossible");
200     else   //找到最大的那个
201         printf("%d", Sum);
202 }

View Code