投稿
  1. 首页
  2. C

数据结构--C语言--图的深度优先遍历，广度优先遍历，拓扑排序，用prime算法实现最小生成树，用迪杰斯特拉算法实现关键路径和关键活动的求解，最短路径

电讯技术 • 2022-6-8 • C • 阅读 106

数据结构--C语言--图的深度优先遍历，广度优先遍历，拓扑排序，用prime算法实现最小生成树，用迪杰斯特拉算法实现关键路径和关键活动的求解，最短路径,第1张

概述本文章向大家介绍数据结构--C语言--图的深度优先遍历，广度优先遍历，拓扑排序，用prime算法实现最小生成树，用迪杰斯特拉算法实现关键路径和关键活动的求解，最短路径，主要包括数据结构--C语言--图的深度优先遍历，广度优先遍历，拓扑排序，用prime算法实现最小生成树，用迪杰斯特拉算法实现关键路径和关键活动的求解，最短路径使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

实验七  图的深度优先遍历（选做，验证性实验，4学时）

实验目的

熟悉图的数组表示法和邻接表存储结构，掌握构造有向图、无向图的算法 ，在掌握以上知识的基础上，熟悉图的深度优先遍历算法，并实现。

实验内容

（1）图的数组表示法定义及基本 *** 作的实现。

（2）图的邻接表表示法定义及基本 *** 作的实现。

（3）写函数实现图的深度优先遍历（分别在两种结构上）

（4）在邻接表上实现拓扑排序、关键路径的求法，在邻接矩阵上实现最短路经、最小生成树的求法。

//邻接矩阵表示法存储无向图 深度优先搜索 最短路径 最小生成树

#include

#define MAX_VERTEX_NUM 20

#define INT_MAX unsigned(-1)>>1

typedef int VRType;

typedef int Status;

typedef char VertexType;

typedef char* InfoType;

typedef int Pathmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef int ShortPathtable[MAX_VERTEX_NUM];

int visited[MAX_VERTEX_NUM];//全局变量 访问标志数组

typedef enum{DG,DN,UDG,UDN}GraphKind;

typedef struct{

VertexType adjvex;

int lowcost;

}Closedge[MAX_VERTEX_NUM];//存放所有已经插入的节点到当前顶点的权值最小的那条边 终点就是i位置上的顶点 adj存放边的起点 lowcost存放最小的权值

typedef struct{

VRType adj;//顶点关系

InfoType info;//该弧相关信息的指针 --权值

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct{

VertexType vexs[MAX_VERTEX_NUM];//顶点向量

AdjMatrix arcs;//邻接矩阵

int vexnum,arcnum;

GraphKind kind;//图的种类标志

}MGraph;

int LocateVex(MGraph G,VertexType a){

for(int i=0;i

if(G.vexs[i]==a) return i;

}

Status CreatUDN(MGraph &G){

int IncInfo;

G.kind = GraphKind(UDN);

printf("请输入顶点数 边数 边上是否有相关信息(是1否0)n");

scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);//顶点个数 边数

//先构造顶点向量 给顶点数组赋值

fflush(stdin);

printf("请输入顶点集:n");

for(int i=0;i

//初始化邻接矩阵

for(int i=0;i

for(int j=0;j

G.arcs[i][j].adj=INT_MAX;//初始化全是断路

printf("请输入弧头弧尾和权值n");

for(int i=0;i

char head,tail;//弧头弧尾的两个字符

int weight,headlo,taillo;//边的权值 弧头弧尾在顶点向量中的位置

fflush(stdin);

scanf(" %c %c %d",&tail,&head,&weight);

headlo = LocateVex(G,head);

taillo = LocateVex(G,tail);

G.arcs[taillo][headlo].adj = weight;

if(IncInfo) scanf("%s",G.arcs[headlo][taillo].info);

// G.arcs[taillo][headlo] = G.arcs[headlo][taillo];//无向图的边的关系在矩阵里是对称的

}

}

Status Visit(VertexType c){

printf("%c",c);

}

int FirstAdjVex(MGraph G,int v){

for(int j=0;j

if(G.arcs[v][j].adj) return j;

}

int NextAdjVex(MGraph G,int v,int w){

for(int j=w+1;j

if(G.arcs[v][j].adj) return j;

return -1;

}

Status DFS(MGraph G,int i){

visited[i] = 1;

Visit(G.vexs[i]);

for(int w=FirstAdjVex(G,i);w>=0;w=NextAdjVex(G,i,w))

if(!visited[w])

DFS(G,w);

return 0;

}

Status DFSTraverse(MGraph G,Status (*Visit)(VertexType c)){//深度优先遍历算法

for(int i=0;i

visited[i] = 0;

for(int i=0;i

if(!visited[i])

DFS(G,i);

return 0;

}

voID MiniSpanTree_PRIME(MGraph G,VertexType u){//从u顶点出发开始构造最小生成树

int k = LocateVex(G,u),minlocate;//新插入节点在顶点向量里的下标

Closedge closedge;

for(int i=0;i

if(i!=k){

closedge[i].adjvex = u;//边的起点

closedge[i].lowcost = G.arcs[k][i].adj;//边的权值

}

}

closedge[k].lowcost = 0;

minlocate = 0;

for(int i=1;i

for(int m=0;m

if(!closedge[m].lowcost) continue;

if(!closedge[minlocate].lowcost) minlocate = m;

if(closedge[minlocate].lowcost>closedge[m].lowcost) minlocate = m;

}

k = minlocate;//选出权值最小的边的终点的下标

printf("n%c %c",closedge[k].adjvex,G.vexs[k]);

closedge[k].lowcost = 0;//第k顶点已经插入在树里了 所以不会存在以第k顶点为终点的待插入的边了

for(int j=0;j

if(G.arcs[k][j].adj

closedge[j].lowcost = G.arcs[k][j].adj;

closedge[j].adjvex = G.vexs[k];

}

}

}

}

voID ShortestPath_DIJ(MGraph G,VertexType e,Pathmatrix &P,ShortPathtable &D){

int final[MAX_VERTEX_NUM];

int v0 = LocateVex(G,e);

int newin,min;

//初始化D[] P[][] final[]

for(int i=0;i

D[i] = G.arcs[v0][i].adj;

final[i] = 0;//均设置为没有找到最短路径

for(int j=0;j

if(D[i]

P[i][v0] = 1;//权值不是无穷大 说明存在通路

P[i][i] = 1;

}

}

D[v0] = 0;//从源点到源点的最小路径为0

final[v0] = 1;//初始化v0 v0属于S集

//开始主循环 每次求得v0到某个顶点v的最短路径 并加v到S集

for(int i=1;i

min = INT_MAX;

for(int j=0;j

if(!final[j]){//min存放的是当前与v0最近的的节点的路径 newin是最近的顶点的下标 也就是即将插入S的顶点

if(D[j]

min = D[j];

newin = j;

}

}

}

final[newin] = 1;//将第j个顶点插入S中 说明该顶点已经找到了最短路径

for(int j=0;j

if(!final[j]&&(D[newin]+G.arcs[newin][j].adj>0)&&(D[newin]+G.arcs[newin][j].adj

D[j] = D[newin]+G.arcs[newin][j].adj;

for(int m=0;m

P[j][newin] = 1;

P[j][j]=1;

}

}

}

printf("endvextpastvextpathlengthn");

for(int i=0;i

printf(" %c t",G.vexs[i]);

if(D[i]

for(int j=0;j

printf(" t%dn",D[i]);

}else{

printf("无n");

}

}

}

main(){

MGraph G;

CreatUDN(G);

printf("nn深度优先遍历:");

DFSTraverse(G,Visit);

printf("nn最小生成树的构成:");

MiniSpanTree_PRIME(G,'a');

Pathmatrix P;

ShortPathtable D;

printf("nn从源点a到其余各点的最短路径:n");

ShortestPath_DIJ(G,'a',P,D);

return 0;

}

//邻接表表示法存储有向图 广度优先搜索拓 扑排序 关键路径

#include

#include

#define MAXSIZE 20

#define MAX_VERTEX_NUM 20

typedef int Status;

typedef int QElemType;//队列里放的是元素在一位数组里的下标

typedef char VertexType;

typedef int SElemType;

typedef enum{DG,UDN}GraphKind;

typedef struct{

QElemType *base;//队列的基地址

int front;//队头下标 相当于队头指针 指向队列头元素

int rear;//队尾下标 指向队列尾元素的下一个位置

}SqQue;

typedef struct ArcNode{//表结点

int adjvex;//该弧指向的顶点的位置

int weight;//权重

int info;

struct ArcNode* next;

}ArcNode;

typedef struct{//头结点

VertexType data;//顶点信息

ArcNode *firstarc;//指向第一个邻接点

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{

AdjList vertices;

int vexnum,arcnum;

int kind;

}ALGraph;

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

int visited[MAX_VERTEX_NUM];

int ve[MAX_VERTEX_NUM];

int vl[MAX_VERTEX_NUM];

int indegree[MAX_VERTEX_NUM];

SqStack S,T;//S是零入度顶点栈 T是拓扑序列顶点栈

int LocateVex(ALGraph G,VertexType v){

for(int i=0;i

if(G.vertices[i].data==v) return i;

}

int FirstAdjVex(ALGraph G,int v){

if(!G.vertices[v].firstarc) return -1;//不存在邻接点

return G.vertices[v].firstarc->adjvex;

}

int NextAdjVex(ALGraph G,int w){

ArcNode *p;

for(p=G.vertices[v].firstarc;p;p=p->next)

if(p->adjvex==w&&p->next) return p->next->adjvex;

return -1;

}

Status Visit(VertexType c){

printf("%c",c);

}

//初始化一个空栈

Status InitStack(SqStack &S){

S.base = (SElemType *)malloc(MAX_VERTEX_NUM*sizeof(SElemType));

if(!S.base) exit(-1);

S.top = S.base;

S.stacksize = MAX_VERTEX_NUM;

return 1;

}

//判空

Status StackEmpty(SqStack S){

return S.base==S.top;

}

//入栈

Status Push(SqStack &S,SElemType e){

*S.top++ = e;

return 1;

}

//出栈

Status Pop(SqStack &S,SElemType &i){

if(S.base==S.top){

printf("空栈！n");

return 0;

}

i = *--S.top;

return 1;

}

Status CreatDN(ALGraph &G){

int IncInfo;

printf("请输入顶点数 边数 边上是否有相关信息(是1否0)n");

scanf("%d%d%d",&IncInfo);//顶点个数 边数

//先构造顶点向量

fflush(stdin);

printf("请输入顶点集:n");

for(int i=0;i

scanf(" %c",&G.vertices[i].data);

G.vertices[i].firstarc = NulL;//初始化指针为空

}

printf("请输入弧头 弧尾 ");

if(IncInfo) printf("边上的关系:n");

for(int i=0;i

char head,taillo;//边的权值 弧头弧尾在顶点向量中的位置

ArcNode *pnew;

fflush(stdin);

pnew = (ArcNode*)malloc(sizeof(ArcNode));

if(!pnew) exit(0);

scanf(" %c %c",&tail);

if(IncInfo)

scanf("%d",&(pnew->info));

headlo = LocateVex(G,head);

pnew->adjvex = LocateVex(G,tail);

pnew->next = G.vertices[headlo].firstarc;

G.vertices[headlo].firstarc = pnew;//头插法插入表结点

}

}

//构造一个空的循环队列

Status InitQueue(SqQue &q){

q.base = (QElemType *)malloc(MAXSIZE*sizeof(QElemType));

if(!q.base) exit(0);

q.front = q.rear = 0;//空队列 两指针均指向下表为0的位置

return 1;

}

//出队列

Status DeQueue(SqQue &q,int &e){

if(q.rear==q.front) return 0;

e = q.base[q.front];

q.front = (q.front+1)%MAXSIZE;

return 1;

}

//入队列

Status EnQueue(SqQue &q,int e){

if((q.rear+1)%MAXSIZE==q.front){

printf("队列已满！n");

return 0;

}

q.base[q.rear] = e;

q.rear = (q.rear+1)%MAXSIZE;

return 1;

}

Status BFSTraverse(ALGraph G,Status (*Visit)(VertexType c)){//深度优先遍历算法

for(int i=0;i

SqQue q;

int u;//保存出队列元素

InitQueue(q);

for(int i=0;i

if(!visited[i]){

visited[i] = 1;

Visit(G.vertices[i].data);

EnQueue(q,i);//将下标入队列 而不是元素值

while(q.rear!=q.front){

DeQueue(q,u);

for(int j=FirstAdjVex(G,u);j>=0;j=NextAdjVex(G,u,j)){

if(!visited[j]){

visited[j] = 1;

Visit(G.vertices[j].data);

EnQueue(q,j);

}

}

}

}

}

}

Status Findindegree(ALGraph G){

ArcNode *p;

for(int i=0;i

for(int i=0;i

for(p=G.vertices[i].firstarc;p;p=p->next)

indegree[p->adjvex]++;

}

Status topologicalSort(ALGraph G){

SqStack S;

int i,j,count;

ArcNode* p;

Findindegree(G);

InitStack(S);

for(i=0;i

if(!indegree[i]) Push(S,i);//将入度为0的顶点的下标入栈

count = 0;//对输出顶点进行计数

while(!StackEmpty(S)){

Pop(S,i);//将入度为0的顶点位置出栈

printf("%c",G.vertices[i].data);//输入出栈顶点的内容

count++;//计数器+1

for(p=G.vertices[i].firstarc;p;p=p->next){

j = p->adjvex;

if(!(--indegree[j])) Push(S,j);

}

}

if(count

}

Status topologicalOrder(ALGraph G){

int i,count=0;

ArcNode *p;

Findindegree(G);

InitStack(S);InitStack(T);

for(i=0;i

if(!indegree[i])

Push(S,i);//将入度为0的顶点的下标入栈

for(int i=0;i

while(!StackEmpty(S)){

Pop(S,i);

Push(T,i);

count++;//和拓扑排序里的大致一样

for(p=G.vertices[i].firstarc;p;p=p->next){

j = p->adjvex;

if((ve[i]+p->info)>ve[j]) ve[j] = ve[i] + p->info;//计算入度为0的顶点的邻接点的最早开始时间

indegree[j]--;

if(!indegree[j]){

Push(S,j);

}

}

}

if(count

return 1;

}

Status CriticalPath(ALGraph G){

int j,k,dut,ee,el;//ee是活动的最早开始时间 el是活动的最晚开始时间

ArcNode *p;

if(!topologicalOrder(G)) return 0;//如果该带权有向图存在环的话就有活动以自身为开始条件 出现错误

for(int i=0;i

while(!StackEmpty(T)){//求事件的最晚发生时间

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->next){

k = p->adjvex;

dut = p->info;//关键活动的时间

if(vl[k]-dut

}

}

printf("starteventtendeventtlasttimetstarttimen");

for(int j=0;j

for(p=G.vertices[j].firstarc;p;p=p->next){

k = p->adjvex;

dut = p->info;

ee = ve[j];

el = vl[k]-dut;

if(ee==el) printf(" %ct %ct %dt %dn",G.vertices[j].data,G.vertices[k].data,ee);

}

}

}

main(){

ALGraph G;

CreatDN(G);

printf("nn广度优先搜索:");

BFSTraverse(G,Visit);

printf("nn拓扑排序结果:");

topologicalSort(G);

printf("nn关键活动:n");

CriticalPath(G);

return 0;

}

总结

以上是内存溢出为你收集整理的数据结构--C语言--图的深度优先遍历，广度优先遍历，拓扑排序，用prime算法实现最小生成树，用迪杰斯特拉算法实现关键路径和关键活动的求解，最短路径全部内容，希望文章能够帮你解决数据结构--C语言--图的深度优先遍历，广度优先遍历，拓扑排序，用prime算法实现最小生成树，用迪杰斯特拉算法实现关键路径和关键活动的求解，最短路径所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1264747.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
电讯技术 电讯技术 一级用户组
0 0
上一篇 2022-06-08
下一篇 2022-06-08

发表评论

登录后才能评论

评论列表（0条）

保存