graphexample.cpp

所有关于图的算法

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <stdlib.h>
#define ElemType char //数据元素类型
#define VertexNum 7 //最大顶点数
int Vn,En; //实际顶点数，边或弧数

// 邻接表存储结构
typedef struct ANode
{
	int AdjV; //邻接点在顺序表中的位置
	int Wn; //权值(用于网. 图可省略)
	struct ANode *next; //指向下一个邻接点
} *AdjLink;

// 表头指针结构
typedef struct
{
	ElemType data;
	AdjLink HAdjV; //邻接点链表头指针
} VNode;

// 图的邻接表存储结构及初始化
VNode AdjL[VertexNum];
void GraphAdjLInit(ElemType *vs)
{
	En=0;
	Vn=strlen(vs);
	if (Vn>VertexNum) Vn=VertexNum;
	for (int k=0; k<VertexNum; ++k)
	{
		if (k<Vn) AdjL[k].data=vs[k];
		else AdjL[k].data='\0';
		AdjL[k].HAdjV=NULL;
	}
} //GraphAdjLInit

// 求顶点v在图G中的位置(下标)
int LocationV(ElemType v)
{
	for (int k=0; k<Vn; ++k)
		if (AdjL[k].data==v) return k;
	if (k>=VertexNum) return -1;
	AdjL[k].data=v;
	Vn=k+1;
	AdjL[Vn].data='\0';
	return k;
} //LocationV

// 通过输入“边”建立图的邻接表存储结构
void GraphAdjCreate()
{
	//ElemType v1,v2;
	int j1=0,j2=0,w0=0;
	AdjLink p,q;
//	printf("\nInput Tail, Head, Weight：\n");
	while (Vn<VertexNum)
	{
//		scanf("%d,%d,%d",&j1,&j2,&w0);
		if (j1==j2 || j1<0 || j2<0) break;
		//j1=LocationV(v1); if (j1==-1) return;
		//j2=LocationV(v2); if (j2==-1) return;
		++En;
		p=(AdjLink) malloc(sizeof(VNode));
		p->AdjV=j2;
		p->Wn=w0;
		p->next=NULL;
		if (!AdjL[j1].HAdjV) AdjL[j1].HAdjV=p;
		else
		{
			q=AdjL[j1].HAdjV;
			while (q->next) q=q->next;
			q->next=p;
		}
	}
} //GraphAdjCreate

// 显示图的邻接表存储结构
void GraphAdjLPrint()
{
	for(int k=0; k<Vn; ++k)
	{
		printf("%d [%c",k,AdjL[k].data);
		AdjLink p=AdjL[k].HAdjV;
		while(p)
		{
			printf(",*]→[%d,%d",p->AdjV,p->Wn);
			p=p->next;
		}
		printf(",^]\n");
	}
}//GraphAdjLPrint


// 图的十字链表--弧结点链表存储结构
typedef struct ONode
{
	int tailV; //弧尾顶点位置
	int headV; //弧头顶点位置
	int Wn; //权值(用于网. 图可省略)
	struct ONode *tnext; //相同弧尾链域
	struct ONode *hnext; //相同弧头链域
} ONode, *OLink;

// 表头指针结构
typedef struct
{
	ElemType data; //顶点数据元素
	OLink HtailV; //弧尾链表头指针
	OLink HheadV; //弧头链表头指针
} V_Node;

// 图的十字链表存储结构及初始化
V_Node OList[VertexNum];
void GraphOListInit(ElemType *vs)
{
	En=0;
	Vn=strlen(vs);
	if (Vn>VertexNum) Vn=VertexNum;
	for (int k=0; k<VertexNum; ++k)
	{
		if (k<Vn) OList[k].data=vs[k];
		else OList[k].data='\0';
		OList[k].HtailV=OList[k].HheadV=NULL;
	}
} //GraphOListInit

// 通过输入“弧”建立图的十字链表存储结构
void GraphOListCreate()
{
	//ElemType v1,v2;
	int j1,j2,w0;
	OLink p,q;
	printf("\nInput Tail, Head, Weight：\n");
	while (En<VertexNum)
	{
		//scanf("%d,%d,%d",&j1,&j2,&w0);
		j1=5*rand()%6;
		j2=(j1*rand()%6+1)%6;
		w0=2*j2*rand()%11+10;
		printf("\n%d  %d  %d",j1,j2,w0);
		if (j1==j2 || j1<0 || j2<0) break;
		++En;
		p=(OLink) malloc(sizeof(V_Node));
		p->tailV=j1;
		p->headV=j2;
		p->Wn=w0;
		p->tnext=NULL;
		p->hnext=NULL;
		if (!OList[j1].HtailV) OList[j1].HtailV=p;
		else
		{
			q=OList[j1].HtailV;
			while (q->tnext) q=q->tnext;
			q->tnext=p;
		}
		if (!OList[j2].HheadV) OList[j2].HheadV=p;
		else
		{
			q=OList[j2].HheadV;
			while (q->hnext) q=q->hnext;
			q->hnext=p;
		}
	}
} //GraphOListCreate

// 输出图的十字链表存储结构
void GraphOListPrint()
{
	printf("Arc Tail List:\n");
	for(int k=0; k<Vn; ++k)
	{
		printf("%d [%c",k,OList[k].data);
		OLink p=OList[k].HtailV;
		while(p)
		{
			printf(",*]→[%d,%d,%d",p->tailV,p->headV,p->Wn);
			p=p->tnext;
		}
		printf(",^]\n");
	}
	printf("Arc Head List:\n");
	for(k=0; k<Vn; ++k)
	{
		printf("%d [%c",k,OList[k].data);
		OLink p=OList[k].HheadV;
		while(p)
		{
			printf(",*]→[%d,%d,%d",p->tailV,p->headV,p->Wn);
			p=p->hnext;
		}
		printf(",^]\n");
	}
} //GraphOListPrint

// 删除十字链表中的一条弧<v1，v2>
void GraphOListDelete(int v1,int v2)
{
	if (v1==v2 || v1<0 || v2<0) return;
	if (!OList[v1].HtailV) return;
	OLink p,q=OList[v1].HtailV;
	while (q && q->headV!=v2)
	{
		p=q;
		q=q->tnext;
	}
	if (q)
	{
		if (q==OList[v1].HtailV) OList[v1].HtailV=NULL;
		else if (!q->tnext) p->tnext=NULL;
		else p->tnext=q;
	}
	if (!OList[v2].HheadV) return;
	p=q=OList[v2].HheadV;
	while (q && q->tailV!=v1)
	{
		p=q;
		q=q->hnext;
	}
	if (q)
	{
		if (q==OList[v2].HheadV) OList[v2].HheadV=NULL;
		else if (!q->hnext) p->hnext=NULL;
		else p->hnext=q;
	}
} //GraphOListDelete


void main()
{
	char Ve[VertexNum]="abcdef";
	GraphAdjLInit(Ve);
	GraphAdjLPrint();
	GraphAdjCreate(); 
	printf("\nAdjacency List: \n");
	GraphAdjLPrint();

	GraphOListInit(Ve);
	GraphOListPrint();
	GraphOListCreate(); 
	printf("\nOrthogonal List: \n");
	GraphOListPrint();

	GraphOListDelete(1,2);
	GraphOListPrint();
}