本文主要是介绍实验4 附加，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*扩展实现源代码*/
# include <stdio.h>
# include <stdlib.h>
# include <conio.h>
# define True 1
# define False 0
# define OK 1
# define ERROR 0
# define OVERFLOW -2
# define NULL 0
# define MAXLEN 10
# define LARGE 999
typedef int Status;
typedef struct
{
int a[MAXLEN],b[MAXLEN],h[MAXLEN];/*第K边的起点,终点,权值*/
char vexs[MAXLEN];/*顶点信息集合*/
int vexnum,arcnum;/*顶点数和边数*/
int kind;/*图的类型*/
int arcs[MAXLEN][MAXLEN];/*邻接矩阵*/
}Graph;
typedef struct node/*表结点结构*/
{
int Adjvex;/*存放与头结点相邻接的顶点在数组中的序号*/
int info;/*权值*/
struct node *next;/*指向与头结点相邻接下一个顶点的表结点*/
}EdgeNode;
typedef struct/*头结点结构*/
{
int id;/*顶点入度*/
char data;/*顶点信息*/
EdgeNode *Link;/*指向头结点对应的单链表中的表结点*/
}Vexnode;
typedef struct/*邻接表结构*/
{
Vexnode Adjs[MAXLEN];/*邻接表的头结点集合*/
int vexnum,arcnum;/*顶点数,边数*/
int kind;
}AdjList;
typedef struct QNode/*队列存储结构*/
{
int data;
struct QNode
*next;
}LinkQList;
typedef struct
{
LinkQList *front;/*队头指针*/
LinkQList *rear;/*队尾指针*/
}LinkQueue;
typedef struct/*栈结构*/
{
int stack[MAXLEN];
int top;
}Stack;
int CNULL=-1;
Graph G;
AdjList Adjl;
Stack *t;/*拓扑序列顶点栈*/
Stack *s;/*零入度顶点栈*/
LinkQueue *q;
Graph Printf_Adjmatrix(Graph G)/*输出邻接矩阵*/
{
int i,j;
printf("邻接矩阵:/n");
printf("vertex/t");
for (i=0;i<G.vexnum;i++) printf("%4c",G.vexs[i]);
printf("/n");
for(i=0;i<G.vexnum;i++)
{ printf("% 4c /t",G.vexs[i]);
for(j=0;j<G.vexnum;j++) printf("%4d",G.arcs[i][j]);
printf("/n");
}
return G;
}
void Creat_1(Graph G)
{
int i,j,k,c=0;
for (i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=c;
for(k=0;k<G.arcnum;k++)
G.arcs[G.a[k]-1][G.b[k]-1]=1;
Printf_Adjmatrix(G);
}
void Creat_2(Graph G)
{
int i,j,k,c=0;
for (i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=c;
for(k=0;k<G.arcnum;k++)
{ G.arcs[G.a[k]-1][G.b[k]-1]=1;
G.arcs[G.b[k]-1][G.a[k]-1]=1;
}
Printf_Adjmatrix(G);
}
Graph Creat_3(Graph G)
{
int i,j,k,c=999;
for (i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=c;
for(k=0;k<G.arcnum;k++)
G.arcs[G.a[k]-1][G.b[k]-1]=G.h[k];
Printf_Adjmatrix(G);
return G;
}
Graph Creat_4(Graph G)
{
int i,j,k,c=999;
for (i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=c;
for (k=0;k<G.arcnum;k++)
{ G.arcs[G.a[k]-1][G.b[k]-1]=G.h[k];
G.arcs[G.b[k]-1][G.a[k]-1]=G.h[k];
}
Printf_Adjmatrix(G);
return G;
}
void CreatGraph(Graph G)/*邻接矩阵*/
{
switch(G.kind)
{
case 1:Creat_1(G);break;
case 2:Creat_2(G);break;
case 3:Creat_3(G);break;
case 4:Creat_4(G);break;
default:printf("ERROR/n");
}
}
AdjList CreatList (Graph G ,AdjList Adjl)/*邻接表*/
{
int i;
EdgeNode *p;
if(G.kind==1||G.kind==3)
{ for(i=0;i<Adjl.arcnum;i++)
{ p=(EdgeNode*)malloc(sizeof(EdgeNode));
p->Adjvex=G.b[i];
p->info=G.h[i];
p->next=Adjl.Adjs[G.a[i]-1].Link;
Adjl.Adjs[G.a[i]-1].Link=p;
}
}
if(G.kind==2||G.kind==4)
{ for(i=0;i<Adjl.arcnum;i++)
{ p=(EdgeNode*)malloc(sizeof(EdgeNode));
p->info=G.h[i];
p->Adjvex=G.b[i];
p->next=Adjl.Adjs[G.a[i]-1].Link;
Adjl.Adjs[G.a[i]-1].Link=p;
p=(EdgeNode*)malloc(sizeof(EdgeNode));
p->info=G.h[i];
p->Adjvex=G.a[i];
p->next=Adjl.Adjs[G.b[i]-1].Link;
Adjl.Adjs[G.b[i]-1].Link=p;
}
}
printf("邻接表为:/n");
for(i=0;i<G.vexnum;i++)
{ printf("[%d,%c]=>",i+1,Adjl.Adjs[i].data);
p=Adjl.Adjs[i].Link;
while(p!=CNULL)
{printf("[%c,%d]-->",Adjl.Adjs[(p->Adjvex)-1].data,p->info);
p=p->next;
}
printf("^/n");
}
return Adjl;
}
void InitQueue(LinkQueue *p)
{ p->front=(LinkQList *)malloc(sizeof(LinkQList));
p->rear=p->front;
(p->front)->next=NULL;
}
Status Empty(LinkQueue *q)
{
int v;
if(q->front==q->rear) v=True;
else v=False;
return v;
}
Status AddQueue(LinkQueue *q,int e)/*入队列*/
{
q->rear->next=(LinkQList *)malloc(sizeof(LinkQList));
q->rear=q->rear->next;
if(!q->rear) return -1;
q->rear->data=e;
q->rear->next=NULL;
return OK;
}
Status DelQueue(LinkQueue *q)/*出队列*/
{
LinkQList *p;
int e;
if (q->front==q->rear)
printf("the LinkList is OVERFLOW");
else p=(q->front)->next;
(q->front)->next=p->next;
e=p->data;
if(q->rear==p)
q->rear=q->front;
free(p);/*释放P所指的内存区*/
return(e);
}
void DFS(int i, AdjList Adjl)/*深度优先搜索*/
{
EdgeNode *p;
int j;
int visited[MAXLEN];/*访问标志数组,访问过为1,未访问过为0*/
for(j=0;j<Adjl.vexnum;j++) visited[j]=0;/*初始化,所有点都未访问*/
printf("%4c->",Adjl.Adjs[i-1].data);
visited[i-1]=1;
p=Adjl.Adjs[i-1].Link;
while(p!=CNULL)
{if (visited[(p->Adjvex)-1]!=1) DFS((p->Adjvex),Adjl);
p=p->next;
}
}
void BFS(int i,AdjList Adjl)/*广度优先搜索*/
{
EdgeNode *p;
int j;
int visited[MAXLEN];
for (j=0;j<Adjl.vexnum;j++) visited[j]=0;/*初始化所有点*/
InitQueue(q);
printf("%4c->",Adjl.Adjs[i-1].data);
visited[i-1]=1;
AddQueue(q,i);
while(!Empty(q))
{i=DelQueue(q);
p=Adjl.Adjs[i-1].Link;
while(p!=CNULL)
{if (visited[(p->Adjvex)-1]==0)
{printf("%4c->",Adjl.Adjs[p->Adjvex-1].data);
visited[(p->Adjvex)-1]=1;
AddQueue(q,p->Adjvex);
p=p->next;
}
}
}
}
Status Initstack(Stack *s)/*构造空栈*/
{
s->top=0;
return OK;
}
Status Push(Stack *s,int x)/*入栈*/
{
if (s->top==MAXLEN){
printf("the stack is OVERFLOW!/n");exit(0);}
else{ s->top=s->top+1;
s->stack[s->top]=x;
}
return OK;
}
Status Pop(Stack *s)
{
int y;
if(s->top==0)printf("the stack is Empty!/n");
else {y=s->stack[s->top];
s->top=s->top-1;
}
return y;
}
Status StackEmpty(Stack *s)
{
if (s->top==MAXLEN) return (True);
else return (False);
}
Status TopSort(AdjList Adjl)/*拓扑排序*/
{
int i,k,count;
EdgeNode *p;
printf("拓扑排序序列为:/n");
Initstack(s);
for(i=0;i<Adjl.vexnum;i++)
if(Adjl.Adjs[i].id==0) Push(s,Adjl.Adjs[i].data);
count=0;
while(!StackEmpty(s))
{ i=Pop(s);
printf("%4c->",Adjl.Adjs[i].data);
++count;
for(p=Adjl.Adjs[i].Link;p;p=p->next)
{ k=p->Adjvex;
if(!(--Adjl.Adjs[k-1].id)) Push(s,k-1);
}
}
if(count<Adjl.vexnum)
{ printf("/n网中有环!/n"); /*拓扑排序输出的顶点数<图中的顶点数*/
return ERROR;
}
else return OK;
}
void Prim(Graph G)/*最小生成树*/
{
int i,j,k,min;
int lowcost[MAXLEN];/*权值*/
int closet[MAXLEN];/*最小生成树结点*/
printf("最小生成树的边为:/n");
for(i=1;i<G.vexnum;i++)
{
lowcost[i]=G.arcs[0][i];
closet[i]=1;
}
closet[1]=0;
j=1;
for(i=1;i<G.vexnum;i++)
{
min=lowcost[j];
k=i;
for(j=1;j<G.vexnum;j++)
if(lowcost[j]<min&&closet[j]!=0)
{
min=lowcost[j];
k=j;
}
printf("(%c,%c),",G.vexs[k-1],G.vexs[closet[k-1]]);
closet[k]=0;
for(j=1;j<G.vexnum;j++)
if(G.arcs[k][j]<lowcost[j]&&closet[j]!=0)
{
lowcost[j]=G.arcs[k][j];
closet[j]=k;
}
}
}
int ve[MAXLEN];/*最早发生时间*/
int vl[MAXLEN];/*最迟发生时间*/
Status TopOrder(AdjList Adjl,Stack *t)/*求各顶点事件的最早发生时间ve*/
{
int i,j,count,k;
EdgeNode *p;
Initstack(s);
Initstack(t);
for(i=0;i<Adjl.vexnum;i++)
if(Adjl.Adjs[i].id==0) Push(s,i);
count=0;
for(i=0;i<Adjl.vexnum;i++) ve[i]=0;
while(!StackEmpty(s))
{ j=Pop(s);Push(t,j);++count;
for(p=Adjl.Adjs[j].Link;p;p=p->next)
{ k=p->Adjvex;
if(--Adjl.Adjs[k-1].id==0) Push(s,k-1);
if(ve[j]+(p->info)>ve[k-1]) ve[k-1]=ve[j]+(p->info);
}
}
if(count<Adjl.vexnum) return ERROR;
else return OK;
}
Status CriticalPath(AdjList Adjl)/*关键路径*/
{
int i,j,k,dut,ee,el;
EdgeNode *p;
if(!TopOrder(Adjl,t)) return ERROR;
for(i=0;i<Adjl.vexnum;i++) vl[i]=ve[i-1];/*初始化顶点事件的最迟发生时间*/
printf("关键路径为:/n");
while(!StackEmpty(t))/*按拓扑排序的逆序求各顶点的最迟发生时间ve值*/
for(j=Pop(t), p=Adjl.Adjs[j].Link;p;p=p->next)
{ k=p->Adjvex; dut=(p->info);
if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut;
}
for(j=0;j<Adjl.vexnum;++j)/*求ee,el和关键活动*/
for(p=Adjl.Adjs[j].Link;p;p=p->next)
{ k=p->Adjvex;dut=p->info;
ee=ve[j];el=vl[k-1]-dut;
if(ee==el) printf("(%c,%c)->",Adjl.Adjs[j].data,Adjl.Adjs[k-1].data);
}
return OK;
}
void ShortPath_Dijkstra(Graph G)
{
int cost[MAXLEN][MAXLEN];
int dist[MAXLEN];/*某源点到各顶点的最短路径长度*/
int path[MAXLEN];/*某源点到终点经过的顶点集合的数组*/
int s[MAXLEN];/*最短路径的终点集合*/
int i,j,v0,min,u;/*U存放最短路径的终点*/
printf("/n请输入起点的编号:");
scanf("%d",&v0);
v0--;
for(i=0;i<G.vexnum;i++)
{for(j=0;j<G.vexnum;j++)
cost[i][j]=G.arcs[i][j];
}
for(i=0;i<G.vexnum;i++)
{ dist[i]=cost[v0][i];
if(dist[i]<LARGE&&dist[i]>0) path[i]=v0;
s[i]=0;
}
s[v0]=1;
for(i=0;i<G.vexnum;i++)
{ min=LARGE;
u=v0;
for(j=0;j<G.vexnum;j++)
if(s[j]==0&&dist[j]<min)
{min=dist[j];u=j;}
s[u]=1; /*U顶点是求得最短路径的顶点编号*/
for(j=0;j<G.vexnum;j++)
if(s[j]==0&&dist[u]+cost[u][j]<dist[j])
{ dist[j]=dist[u]+cost[u][j];
path[j]=u;
}
}
printf("/n顶点%d到各顶点的最短路径长度为:/n",v0);
for(i=0;i<G.vexnum;i++)/*输入结果*/
if(s[i]==1)
{ u=i;
while(u!=v0)
{ printf("%4c<-",G.vexs[u]);
u=path[u];
}
printf("%4c",G.vexs[u]);
printf(":%d/n",path[i]);
}
else printf("%4c<-%4c:无路径/n",G.vexs[i],G.vexs[v0]);
}
void ShortPath_Floyd(Graph G)
{ int path[MAXLEN][MAXLEN];
int short3[MAXLEN][MAXLEN];/*权值*/
int i,j,k;
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{ short3[i][j]=G.arcs[i][j];
path[i][j]=0;
}
printf("/n各顶点间的最短路径为:/n");
for(k=0;k<G.vexnum;k++)
for(i=0;i<G.vexnum;i++)
{ if(short3[i][j]>(short3[i][k]+short3[k][j]))
{ short3[i][j]=short3[i][k]+short3[k][j];
path[i][j]=k;
}
printf("(%4c->%4c):%d",G.vexs[i-1],G.vexs[j-1],short3[i][j]);
}
}
int menu()
{
int a;
printf("/n请选择图的实现:/n");
printf("1__邻接矩阵/n");
printf("2__邻接表/n");
printf("3__深度优先搜索/n");
printf("4__广度优先搜索/n");
printf("5__最小生成树/n");
printf("6__拓扑排序/n");
printf("7__关键路径/n");
printf("8__从某个源点到其余各顶点的最短路径/n");
printf("9__每一对顶点之间的最短路径/n");
printf("10__退出....../n");
scanf("%d",&a);
return a;
}
void chushihuachuli()
{
int i,j,k,h;
printf("/n请输入图的类型(1:有向图 2:无向图 3:有向网 4:无向网):");
scanf("%d",&i);
{
G.kind=i;
Adjl.kind=i;
}
printf("请输入顶点数,边数(逗号隔开):");
scanf("%d,%d",&i,&j);
G.vexnum=i;Adjl.vexnum=i;
G.arcnum=j;Adjl.arcnum=j;
for (i=0;i<G.vexnum;i++)
{
printf("第%d个顶点的信息:/n",i+1);
scanf("%s",&G.vexs[i]);
Adjl.Adjs[i].data=G.vexs[i];
Adjl.Adjs[i].Link=CNULL;
Adjl.Adjs[i].id=0;
}
for (k=1;k<=G.arcnum;k++)
{
if (G.kind==1||G.kind==3)
printf("第%d条边的起点编号,终点编号:(逗号隔开)",k);
else
printf("第%d条边的两个顶点的编号:(逗号隔开)",k);
scanf("%d,%d",&i,&j);
G.a[k-1]=i;G.b[k-1]=j;
if(i<1||i>G.vexnum||j<1||j>G.vexnum)
{printf(" 编号超出范围,重新输入");continue;}
if (G.kind==3||G.kind==4)
{
printf("/t该边的权值:");
scanf("%d",&h);
G.h[k-1]=h;
}
else G.h[k-1]=NULL;
Adjl.Adjs[i].id++;
}
}
void main()
{
int quit=0,k;
chushihuachuli();
while(!quit)
switch(menu())
{
case 1:CreatGraph(G);break;
case 2:CreatList(G,Adjl);break;
case 3:printf("请输入出发点编号:");
scanf("%d",&k);
CreatList(G,Adjl);
printf("/n从第%d点出发深度优先搜索遍历序列:",k);
DFS(k,Adjl);break;
case 4:printf("请输入出发点编号:");
scanf("%d",&k);
CreatList( G,Adjl);
printf("/n从第%d点出发广度优先搜索遍历序列:",k);
BFS( k,Adjl);
break;
case 5:if (G.kind==4)
{Creat_4(G); Prim(G);}
else{printf("/t不能构造最小生成树,请重新选择:/n");}
break;
case 6:if (G.kind==1||G.kind==3)
{CreatList(G,Adjl); TopSort(Adjl);}
else{printf("/t不能拓扑排序,请重新选择:/n");}
break;
case 7:if (G.kind==3)
{CreatList(G,Adjl);
CriticalPath( Adjl);
}
else{printf("/t没有关键路径,请重新选择:/n");}
break;
case 8:if (G.kind==3)
{Creat_3(G); ShortPath_Dijkstra(G);}
else{printf("/t没有最短路径,请重新选择:/n");}
break;
case 9:if (G.kind==3)
{Creat_3(G); ShortPath_Floyd(G);}
else{printf("/t没有最短路径,请重新选择:/n");}
break;
case 10:quit=1;
default:{printf(" /n/t*** wronG ***/n");}
}/*switch*//*while*/
}/*main()*/
这篇关于实验4 附加的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
