graphrect.h

本源码配合数据结构（C++版 ）严蔚敏

//图的邻接矩阵表示法(数组存储)//图的十字链表存储
//
#include"stdio.h"
#include "stdlib.h"
//#include"iomanip.h"//setw(10)
  #define TRUE 1
  #define FALSE 0
  #define OK   1
  #define ERROR  0 
  #define INFEASIBLE -1
  #define OVERFLOW -2
  #define NULL 0
  typedef int Status;//函数的类型，其值是函数结果状态代码
  
#define MAX_VERTEX_NUM 20//最大顶点数
#define INFINITY 32768//无穷大

typedef int  GraphKind;//有向图，有向网，无向图，无向网
typedef char VertexType;
typedef int VRType;
typedef int InforType;
//typedef bool final ;//当其为TRUE时 表明已求得最短路径
//typedef int **PathMatrix;//顶点的最短路径数组
//typedef int *ShortPathTable;//顶点的最短路径的带权长度数组
typedef struct ArcCell{
	VRType adj;//VRType是顶点关系类型，对无权图，用1或0表示相邻否；对带权图，则为权值类型
	InforType *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,char v){
	for(int i=0;v!=G.vexs[i]&&i<G.vexnum;++i);
	if(i>=G.vexnum)return -1;
	return i;
}
Status CreateUDN(MGraph &G){
	//采用数组（邻接矩阵）表示法，构造无向网
	int IncInfo=0;
	printf("请输入图的种类(有向1,无向0)\n");
	scanf("%d",&G.kind);
	printf("请输入顶点数vexnum，弧数arcnum和各弧的其他信息IncInfo(默认值0)\n");
	scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其它信息
	printf("构造顶点向量\n");
	for (int i1=0;i1<G.vexnum;++i1)
		scanf("%s",&G.vexs[i1]);//构造顶点向量
	for(int i=0;i<G.vexnum;++i)
		for(int j=0;j<G.vexnum;++j){
			G.arcs[i][j].adj=INFINITY;//{adj,info}
			G.arcs[i][j].info=NULL;
		}
		char v1,v2;
		int w;
		for(int k=0;k<G.arcnum;++k){//构造邻接矩阵
			printf("输入一条边依附的顶点和权值v1 v2 w :\n");
			scanf("%s%s%d",&v1,&v2,&w);//输入一条边依附的顶点和权值
			int i=LocateVex(G,v1);
			int j=LocateVex(G,v2);//确定v1和v2在G中的位置
			G.arcs[i][j].adj=w;//弧的权值
			if(IncInfo)scanf("%d",&G.arcs[i][j].info);//若弧含有相关信息，则输入
			if(!G.kind)G.arcs[j][i].adj=G.arcs[i][j].adj;//值<v1,v2>的对称弧<v2,v1>
		}
		return OK;
}//CreateUDN
Status PrintfMGraph(MGraph G){
	printf("输出邻接矩阵\n");
	for(int i=0;i<G.vexnum;++i){
		printf("%d  %c ||  ",i,G.vexs[i]);
		for(int j=0;j<G.vexnum;++j){
			printf("%5d  ",G.arcs[i][j].adj);
		}
		j=0;
		printf("\n");
	}
	printf("----------32768代表无穷大----------\n");
	return OK;
}

Status ShortestPath_DIJ(MGraph G,VertexType vv,int P[][100],int D[]){
	//用Dijkstra算法求G的v0到其余顶点v的最短路径及其带权长度D[v]
	//若P[v][w]为TRUE，则w是从v0到w的当前最短路径的顶点
	//当final[v]为TRUE时 表明已求得最短路径
	int v0=LocateVex(G,vv);
	int final[10];
	for(int v=0;v<G.vexnum;++v){
		final[v]=FALSE;			//当其为TRUE时 表明已求得最短路径
		D[v]=G.arcs[v0][v].adj;
		for(int w=0;w<G.vexnum;++w) P[v][w]=FALSE;//设空路径
		if(D[v]<INFINITY){
			P[v][v0]= TRUE;
			P[v][v]=TRUE;
		}
	}//for
	D[v0]=0;final[v0]=1;		//初始化，v0顶点属于S集
	printf("%c到 v顶点的最短距离及途经顶点\n",vv);
	int min=0;					//开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集
	for(int i=1;i<G.vexnum;++i){	///其余G.vexnum－1各顶点//循环n-1次结束
		min=INFINITY;			//当前离所知的顶点v0的最近距离
		for(int w1=0;w1<G.vexnum;++w1)
			if(!final[w1])		//w顶点在V－S中
				if(D[w1]<min){
					v=w1;
					min=D[w1];	//w1离顶点v0最近
				}
		final[v]=TRUE;			//离v0点最近的v加入S集
		printf("\n    %c%8d",G.vexs[v],min);//输出函数部分
		printf("        ");
		for(int j=0;j<G.vexnum;++j)
			if(P[v][j])printf("%c",G.vexs[j]);//输出最短路径上的所有顶点
		for(int w2=0;w2<G.vexnum;++w2)	//更新当前最段路径机距离
			if(!final[w2]&&(min+G.arcs[v][w2].adj<D[w2])){//修改D[w2]和P[w2]
				D[w2]=min+G.arcs[v][w2].adj;
				for(int s=0;s<G.vexnum;++s)
				P[w2][s]=P[v][s];
				P[w2][w2]=TRUE;		//P[w2]=P[v]+P[w2]
			}//if
	}//for
	printf("\n");
	return OK;
}

void MiniSpanTree_PRIM(MGraph G,VertexType u){
	struct {
		VertexType adjvex;
		VRType lowcost;
	}closedge[MAX_VERTEX_NUM];
	int k=LocateVex(G,u);
	for(int j=0;j<G.vexnum;++j)
		if(j!=k){
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j].adj;
		}
		closedge[k].lowcost=0;
		printf("Prim 算法输出最小生成树\n");
		for(int i=1;i<G.vexnum;++i){
			int min=INFINITY;
			int k1=0;
			for(int n=0;n<G.vexnum;++n){
				if(closedge[n].lowcost){
					if(closedge[n].lowcost<min){
						min=closedge[n].lowcost;
						k1=n;
					}
				}
			}
			printf("%c-->%c  ",closedge[k1].adjvex,G.vexs[k1]);
			closedge[k1].lowcost=0;
			for(int j1=0;j1<G.vexnum;++j1)
				if(G.arcs[k1][j1].adj<closedge[j1].lowcost){
					closedge[j1].lowcost=G.arcs[k1][j1].adj;
					closedge[j1].adjvex=G.vexs[k1];
				}
		}
		printf("\n");
}

//单链队列 ，队列的链式存储结构
typedef int QElemType;
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}
Status QueueEmpty(LinkQueue Q){
	if(Q.front==Q.rear)return OK;
	else return ERROR;
}
Status EnQueue(LinkQueue &Q,QElemType e){
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p)exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e){
	if(Q.front==Q.rear)return ERROR;
	QueuePtr p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)Q.rear=Q.front;
	free(p);
	return OK;
}
Status GetHead(LinkQueue &Q,QElemType &e){
	QueuePtr p;
	if(QueueEmpty(Q))return 0;
	else {
		p=Q.rear;
		return p->data;
	}
	return OK;
}
Status DestroyQueue(LinkQueue &Q){
	while(Q.front){
		Q.rear=Q.front->next;
		free(Q.front);
		Q.front=Q.rear;//从前向后依次删除队列中的结点
	}
	return OK;
}

//十字链表结构
//有向图无向图的十字链表存储表示
typedef struct ArcBox{
	VRType tailvex,headvex;//VRType是int类型，该弧的尾和头顶点的位置
	struct ArcBox *hlink,*tlink;//分别为弧头相同的弧和弧尾相同的弧的链域
	InforType *info;//改弧相关信息的指针
}ArcBox;
typedef struct VexNode{
	VertexType data;//VRType是顶点关系类型，对无权图，用1或0表示相邻否；对带权图，则为权值类型
	ArcBox *firstin,*firstout;//分别指向该顶点的第一个如入弧和出弧
}VexNode;
typedef struct {
	VexNode xlist[MAX_VERTEX_NUM];//顶点向量
	int vexnum ,arcnum;//图的当前顶点数和弧数
	GraphKind kind;//图的种类标志
}OLGraph;

int LocateVex(OLGraph G,char v){
	for(int i=0;v!=G.xlist[i].data&&i<G.vexnum;++i);
	if(i>=G.vexnum)return -1;
	return i;
}
Status CreateUDG(OLGraph &G){
	//采用十字链表表示法，构造无向网
	int IncInfo=0;
	printf("请输入图的种类(有向1,无向0)\n");
	scanf("%d",&G.kind);
	printf("请输入顶点数vexnum，弧数arcnum和各弧的其他信息IncInfo(默认值0)\n");
	scanf("%d%d%d",&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其它信息
	printf("构造顶点向量\n");
	for (int i1=0;i1<G.vexnum;++i1){
		scanf("%s",&G.xlist[i1].data);//构造顶点向量
		G.xlist[i1].firstin=NULL;//初始化指针
		G.xlist[i1].firstout=NULL;
		}
		char v1,v2;
		for(int k=0;k<G.arcnum;++k){//构造十字链表
			printf("输入一条边依附的顶点v1 v2 :\n");
			scanf("%s%s",&v1,&v2);//输入一条边依附的顶点
			int i=LocateVex(G,v1);
			int j=LocateVex(G,v2);//确定v1和v2在G中的位置
			ArcBox* p=(ArcBox*)malloc(sizeof(ArcBox));
			p->tailvex=i;
			p->headvex=j;
			p->hlink=G.xlist[j].firstin;
			p->tlink=G.xlist[i].firstout;
			p->info=NULL;
			G.xlist[j].firstin	= G.xlist[i].firstout=p;//完成入弧出弧连头的插入
			if(IncInfo)scanf("%d",&(p->info));//若弧含有相关信息，则输入
			if(!G.kind){//值<v1,v2>的对称弧<v2,v1>
				ArcBox* q=(ArcBox*)malloc(sizeof(ArcBox));
				q->tailvex=j;
				q->headvex=i;
				q->hlink=G.xlist[i].firstin;
				q->tlink=G.xlist[j].firstout;
				q->info=NULL;
				G.xlist[i].firstin = G.xlist[j].firstout=q;//完成入弧出弧连头的插入
				if(IncInfo)scanf("%d",&(q->info));//若弧含有相关信息，则输入
			}
		}
		return OK;
}//CreateUDG
void visit_OL(OLGraph G){
	//输出十字表
	int i;
	ArcBox *p;
	printf("%4s%6s%25s\n","No","data","adjvexs of arcs'tailvex");
	for(i=0;i<G.vexnum;i++){
		printf("%4d%5c  ",i,G.xlist[i].data);
		for(p=G.xlist[i].firstout;p;p=p->tlink)
			printf("%3d",p->headvex);//弧所指的顶点的位置
		printf("\n");
	}
}