图的基本操作及应用

#include
#include
#include
#define ERROR 0
#define OK 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 21
#define STACK_INIT_SIZE 100
#define STACKINCREAMENT 10
typedef enum{DG,DN,UDG}GraphKind;
typedef struct ArcCell{
int sdj;
//infotype *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
char vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphKind kind;
}MGraph; //邻接矩阵
typedef struct ArcNode{
int adjvex;
int quan;
struct ArcNode *nextrarc;
}ArcNode,*AList;
typedef struct VNode{
char data;
AList firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnnum,arcnum;
GraphKind kind;
}ALGraph; //邻接表
typedef struct QNode{
char data;
struct QNode *next;
}QNode,*QueuePre;
typedef struct {
QueuePre front;
QueuePre rear;
}LinkQueue; //队列
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack; //栈
typedef struct{
char adjvex;
int lowcast;
}closedge[MAX_VERTEX_NUM]; //求最小生成树中的辅助数组
int option;
int visited[MAX_VERTEX_NUM]; //顶点访问标记数组
int indegree[MAX_VERTEX_NUM]; //顶点入度记录数组
int ve[MAX_VERTEX_NUM]; //顶点权值记录数组
int SetGraphKind(MGraph&G,int option){
switch(option){
case 1:G.kind=DG;break;
case 2:G.kind=DN;break;
case 3:G.kind=UDG;break;
case 4:G.kind=UDN;break;
default:return ERROR;
}
return OK;
} //邻接矩阵类型设置
int SetGraphKind(ALGraph&G,int option){
switch(option){
case 1:G.kind=DG;break;
case 2:G.kind=DN;break;
case 3:G.kind=UDG;break;
case 4:G.kind=UDN;break;
default:return ERROR;
}
return OK;
} //邻接表类型设置
int LocateVex(MGraph G,char v)[
int m;
for(m=1;m<=G.vexnum;m++){
if( G.vexs[m]==v) return m;
}
return ERROR;
} //邻接矩阵顶点定位
int Locate Vex(ALGraph G,char v){
intm;
for(m=1;m>=G.vexnum;m++){
if( G.vertices[m].data==v) return m;
}
printf("你输入的顶点不存在");
return ERROR;
} //邻接表顶点定位
int LnitQueue(LinkQueue&Q){
Q.front=Q.rear=(QueuePre)malloc(sizeof(QNode));
if(!Q.front) return ERROR;
Q.front->next=NULL;
return OK;
} //队列创建
int EnQueue(LinkQueue&Q,int e){
QueuePre p;
p=(QueuePre)malloc(sizeof(QNode));
if(!p) return OK;
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
} //元素入队列
int DeQueue(LinkQueue&Q,int&e){
QueuePre p;
if(Q.front==Q.rear)return ERROR;
P=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
return OK;
} //元素出队列
int QueueEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return OK;
return ERROR;
} //判断队列是否为空
int LnitStack(SqStack&S){
S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));

if(!S.base)return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
} //栈创建


int Push(SqStack&S,int e){
if(S.top-S.base>=S.stacksize){
S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int));
if(!S.base) return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREAMENT;
}
*S.top++=e;
return OK;
} //元素入栈
int Pop(SqStack &S,int &e){
if(S.top==S.base)return ERROR;
e=*--S.top;
return OK;
} //元素出栈
int StackEmpty（SqStack S){
if(S.top==S.base)return OK;
return ERROR;
} //判断栈是否为空
int CreatGraph(MGraph&G){
int i,j,k,w;char x,y;
if(!SetGraphKind(G,option)) {printf("对图类型的设置失败");return ERROR;}
printf("邻接矩阵：请输入定点的个数、弧的个数：");
scanf("%d%d",&G.vexnum,&G.arcnum);
if(G.vexnum>20){
printf("您输入的定点个数超过最大值");
return ERROR;
}
printf("请输入%d个顶点\n",G.vexnum);
for(i=1;i<=G.vexnum;++i){fflush(stdin);scanf("%c",&G.vexs[i]);}
if(G.kind==DG|G.kind==UDG){
for(i=1;i<=G.vexnum;i++)
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j].sdj=0;
if(G.kind==DG){
printf("请输入有向图的两个相邻的顶点(如果互相邻接则也要输入）:\n");
for(k=1;k<=G.arcnum;k++){fflush(stdin);
scanf("%c%c",&x,&y);
i=LocateVex(G,x);j=LocateVex(G,y);
G.arcs[i][j].adj=1;
}
}
else{
printf("请输入无向图的两个相邻的顶点(x,y):\n");
for(k=1;k<=G.arcnum;k++){fflush(stdin);
scanf("%c%c",&x,&y);
i=LocateVex(G,x);j=LocateVex(G,y);
G.arcs[i][j].adj=1;G.arcs[i][j].adj=G[i][j].adj;
}
}
}
else{
for(i=1;i<=G.vexnum;i++)
for(j=1lj<=G.vexnum;j++)
G.arcs[i][j].adj=INT_MAX;
if(G.kind==DN){
printf("请输入有向网的两个相邻的顶点以及相应的权值w（如果互相邻接则也要输入）：\n");
for(k=1;k<=G.arcnum;k++){fflush(stdin);
scanf("%c%c%d",&x,&y,&w);
i=LocateVex(G,x);j=LocateVex(G,y);
G.arcs[i][j].adj=w;
}
}
else{
printf("请输入无向网的两个相邻的顶点（x,y)以及相应的权值\n");
for(k=1;k<=G.arcnum;k++){fflush(stdin);
scanf("%c%c%d",&x,&y,&w);
i=LocateVex(G,x);j=LocateVex(G,y);
G.arcs[i][j].adj=w;G.arcs[i][j].adj=G.arcs[i][j].adj;
}
}
}
return OK;
} //创建邻接矩阵
int i,j,m,n,key[MAX_VERTEX_NUM];char x,y,w;AList p,q;
SetGraphKind(G,option);
printf("邻接表：请输入顶点个数和弧的个数：");
scanf("%d%d",&G.vexnum,&G.arcnum);
if(G.vexnum>20){
printf("你输入的顶点个数超过最大值");
return ERROR;
}
printf("请输入个顶点：\n");
for(i=1;i<=G.vexnum;i++){
fflush(stadin);
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
key[i]=0
}
if(G.kind==DG){
printf("请输入弧（如AB，其中AB与BA是不同的弧）：\n");
for(j=1lj<=G.arcnum;j++){
fflush(stadin);

scanf("%c%c",&x,&y);
m=LocateVex(G,x);
n=LocateVex(G,y);
p=G.vertices[m].firstarc;
q=(AList)malloc(sizeof(ArcNode));
if(!q) return ERROR;
Q->nextarc=NULL;
q->quan=w;
q->adjvex=n;
while(key[m]&&p->nextarc){
p=p->nextarc;
key[m]++;
}
if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}
else p->nextarc=q;
}
}
return OK;
} //创建邻接表
int FristAdjVex(ALGraph G,int v){
if(G.vertices[v].firstarc)
return G.vertices[v].firstarc->adjvex;
return 0;
}
int NextAdjVex(ALGraph G,int v ,int w){
AList s;
s=G.vertices[v].firstarc;
while(s->adjvex!=w)
s=s->nextarc;
if(s->nextarc)
return s->nextarc->adjvex;
return 0;
}
void DFS(ALGraph G,int v){
int w;
visited[v]=1;printf("%c",G.vertices[v]);
for(w=FirstAdjVex(G,v);w>=1;w=NextAdjVex(G,v,w)){
if(!visited[w]) DFS(G,w);
}
}
void DFSTraverse(ALGraph G){
int v;
visited[0]=1;
for(v=1;v<=G.vexnum;v++)visited[v]=0;
for(v=1;v<=G.vexnum;v++)
if(!visited[v])DFS(G,v);
} //图的深度遍历
void BFSTraverse(ALGraph G){
int v,w,u;LinkQueue Q;
for(v=1;v<=G.vexnum;v++)visited[v]=0;
visited[0]=1;
InitQueue(Q);
for(v=1;v<=G.vexnum;v++)
if(!visited[v]){
visited[v]=1;
printf("%c",G.vertices[v]);
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w)){
if(!visited[w]){
visited[w]=1;
printf("%c",G.vertices[w]);
EnQueue(Q,w);
}
else break;
}
}
}
} //图的广度遍历
void FindlnDegree(ALGraph G,int in[]){
int i,j,k;AList p;
for(k=1;k<=G.vexnum;k++)in[k]=0;
for(i=1;i<=G.vexnum;i++){
p=G.vertices[i].firstarc;
while(p){
j=p->adjvex;
in[j]++;
p=p->nextarc;
}
}
} //计算各顶点的入度
int TopologicalSort(ALGraph G){
int i,kcount;AList p;SqStack S;
FindlnDegree(G,indegree);
InitStack(S);
for)i=1;i<=G.vexnum;i++)
if(!indegree[i]Push(S,i);
count=0;
if(StackEmpty(S)printf("此有向图不符合条件！");
while(!StackEmpty(S)){
Pop(S,i);
printf("%d ",i);
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc){
k=p->adjvex;
if(!--indegree[k]))Push(S,k);
}
}
if(count<=G.vexnum)return ERROR;
else return OK;
} //拓扑排序
int Minimum(MGraph G,closedges m){
int i,j,min=INFINITY;
for(i=1;i<=G.vexnum;i++){
if(m[i].lowcost){
if(m[i].lowcostmin=m[i].lowcost;
j=i;
}
}
return j;
}
void MinSpanTree_PRIM(MGraph G,char u){
int i,j,k;closedges closedge;
k=LocateVex(G,u);
for(j=1;j<=G.vexnum;j++)
if(j!=k){
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].adj;
}
closedge[k].lowcost=0;
for(i=2;i<=g.vexnum;i++){
k=Mininum(G,closedge);
printf("%c%c",closedge[k].adjvex,G.vexs[k]);
close

dge[k].lowcost=0;
for(j=1;j<=G.vexnum;j++)
if(G.arcs[k][j].adjclosedge[j].adjvex=G.vexs[k];
closedge[j].lowcost=G.arcs[k][j].adj;
}
}
}// 求最小生成树
int TopologicalOrder(ALGraph G,SqStack&T){
int i,j,k,count; SqStack S; AList p;
FindInDegree(G,indegree);
InitStack(S);
for(i=1;i<=G.vexnum;i++);
if(!indegree[i]) Push(S,i);
InitStack(T);count=1;for(i=1;i<=G.vexnum;i++) ve[i]=0;
while(!StackEmpty(S)){
Pop(S,j);Push(T,j);++count;
for(p=G.vertices[j].firstarc;p;p=->nextarc){
k=p->adjvex;
if(--indegree[k]==0)Push(S,k);
if(ve[j]+p->quan>ve[k]) ve[k]=ve[j]+p->quan;
}
}
if(count<=G.vexnum)return ERROR;
else return OK;
}
int CriticalPath(ALGraph G){
int i,j,k,ee,el,dut,v1[MAX_VERTEX_NUM]; SqStack T;AList p;char tag;
if(!TopologicalOrder(G,T)) return ERROR;
for(i=1;i<=G.vexnum;i++){
v1[i]=ve[G.vexnum];
}
while(!StackEmpty(T))
for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;dut=p->quan;
if(v1[k]-dut}
for(j=1;j<=G.vexnum;j++)
for(p=G.vertices[j].firstarc;p;p=p->nextarc){
k=p->adjvex;dut=p->quan;
ee=ve[j];el=v1[k]-dut;
tag=(ee==el)?"*":"";
printf("%d%d%d%d%d%d%c\n",j,k,dut,ee,el,tag);
}
return OK;
} //求关键路径
void DG_(MGraph G1,ALGraph G2){
int i,j,k,m,key;AList s;
for(k=0;;){
key=0;
printf("**************************\n");
printf("请选择对有向图进行的操作：\n1 创建邻接矩阵\n2创建邻接表\n3拓扑结构\n4退出\n");
printf("*************************\n");
printf("请选择：");
scanf("%d",&m);
switch(m){
case 1:CreatGraph(G1);printf("有向图的邻接矩阵：\n");
for(i=1;i<=G1.vexnum;i++){
for(j=1;j<=G1.vexnum;j++){
printf("%d",G1.arcs[i][j].adj);
}
printf("\n");
}
break;
case 2:CreatAList(G2);printf("有向图的邻接表：\n");
for(i=1li<=G2.vexnum;i++){
printf("%c:",G2.vertices[[i]);
s=G2.vertices[i].firstarc;
while(s){
j=s->adjvex;fflush(stdin);
printf("<%c",G2.vertices[i]);
printf("%c>",G2.vertices[j]);
s=s->nextarc;
}
printf("\n");
}break;
case 3:printf("有向图的拓扑排序:\n");TopologicalSort(G2);break;
case 4:key=1; break;
}printf("\n");
if(key) break;
}
printf("\n\n");
} //DG
void DN_(MGraph G1,ALGraph G2){
int i,j,k,m,key;AList s;
for(k=0;;){
key=0;
printf("**************************\n");
print("请选择对有向图网进行的操作：\n1 创建邻接矩阵\n2 创建邻接表\n关键路径\n退出\n");
printf"(**************************\n");
printf("请选择：");
scanf("%d",&m);
switch(m){
case 1:CreatGraph(G1);printf("有向网的邻接矩阵：\n");
for(i=1;i<=G1.vexnum;i++){
for(j=1;j<=G1.vexnum;j++){

if(G1.arcs[i][j].adj==INT_MAX)printf("#");
else printf{"%d",G1.arcs[i][j].adj);
}
printf("\n");
}
break;
case 2:CreatAList(G2);printf("有向网的邻接表：\n");
for(i=1;i<=G2.vexnum;i++){
printf("%c",G2.vertices[i]);
s=G2.vertices[i].firstarc;
while(s){
j=s->adjvex;fflush(stadin);
printf("<%c",G2.vertices[i]);
printf("%C>",G2.vertices[j]);
printf(" %d",s->quan);
s=s->nextarc;
}
printf("\n");
}
break;
case 3:printf("有向网关键路径：\n");CriticalPath(G2);break;
case 4:key=1;break;
}
printf("\n");
if(key)break;
}
printf("\n\n");
} //DN
void UDG_(MGraph G1,ALGraph G2){
int i,j,k,m,key;AList s;
for(k=0;;){
key=0
printf("**************************\n");
printf("请选择对无向图进行的操作：\n1 创建邻接矩阵\n2创建邻接表\n3深度遍历\n广度遍历\n退出\n");
printf("*************************\n");
printf("请选择：");
scanf("%d",&m);
switch(m){
case 1:CreatGraph(G1);
printf("无向图的邻接矩阵：\n");
for(i=1;i<=G1.vexnum;i++){
for(j=1;j<=G1.vexnum;j++){
printf("%d",G1.arcs[i][j].adj);
}
printf("\n");
}
break;
case 2:CreatAList(G2);
print("无向图的邻接表：\n");
for(i=1;i<=G2.vexnum;i++){
orintf("%c:",G2.vertices[i]);
s=G2.vertices[i]).firstarc;
j=s->adjvex;fflush(stdin);
printf("%c",G2.vertices[i]);
printf("%c)",G2.vertices[j]);
s=s->nextarc;
}
printf("\n");
}
break;
case 3:printf("无向图的深度优先遍历：\n");
DFSTraverse(G2);printf("\n");break;
case 4:printf("无向图的广度优先遍历：\n");
BFSTraverse(G2);break;
case 5:key=1;break;
}
printf("\n");
if(key)break;
}
printf("\n\n");
} //UDG
void UDG_(MGraph G1,ALGraph G2){
int i,j,m,k,keylAList s;char u;
for(k=0;;){
key=0;
printf("**************************\n");
printf("请选择对无向图进行的操作：\n1 创建邻接矩阵\n2创建邻接表\n3最小生成树\n退出\n");
printf("请选择：");
scanf("%d",&m);
switch(m){
case 1:CreatGraph(G1);printf("无向网的邻接矩阵：\n");
for(i=1;i<=G1.vexnum;i++){
for(j=1;j<=G1.vexnum;j++){
if(G1.arcs[i][j].adj==INT_MAX)printf("#");
else printf("%d",G1.arsc[i][j].adj);
print("\n");
}
break;
case 2:CreatAList(G2); printf("无向网的邻接表:\n");
for(i=1;i<=G2.vexnum;i++){
printf("%c:",G2.vertices[i]);
s=G2.vertices[i].firstarc;
while(s){
j=s->adjvex;fflush(stdin);
printf("(%c",G2.vertices[i]);
printf("%c)",G2.vertices[j]);
printf("%d",s->quan);
s=s->nextarc;
}
printf("\n");
}
break;
case 3:printf("请输入第一个顶点：")fflush(s

tadin);scanf("%c",&u);
printf("无向网的最小生成树：\n")
MinSpanTree_PRIM(G1,u);break;
case 4:key=1;break;
}printf("\n");
if(key)break:
}
printf("\n\n");
} //UDN
void main(){
MGraph G1;
ALGraph G2;
int i,n;
for(i=0;;){
n=0;
printf("**************************\n");
printf("请输入你要进行的图的类型的编码\n1:有向图\n2：有向图网\n3: 无向图\n4: 无向网\n5: 退出\n");
printf("**************************\n");
peintf("请选择：");
scanf("%d",&option);
printf("\n\n");
switch(option){
case 1:DG_(G1,G2);break;
case 2:DN_(G!,G2);break;
case 3:UDG_(G1,G2);break;
case 4:UDN_(G1,G2);brwak;
case 5:n=1;break;
default:printf("你输入的编码有误！");break;
}
if(n)break;
printf("\n\n");
}
}