ch7.cpp

邻接表

#include<stdio.h>
#include<stdlib.h>
#define N 20
#define INFINITY 99999
typedef enum{DG,DN,UDG,UDN}Graphkind;
typedef struct
{//邻接矩阵的类型定义
	char vexs[N];
	int arcs[N][N];
	int vexnum,arcnum;
	int kind;
}MGraph;
typedef struct ArcNode
{//邻接表的类型定义
	int adjvex;
	struct ArcNode *next;
}ArcNode;
typedef struct VNode
{
	char data;
	ArcNode *firstarc;
}VNode,AdjList[N];
typedef struct 
{
	AdjList vertice;
	int vexnum,arcnum;
	int kind;
}ALGraph;
typedef struct node {
		char adjvex;
		int lowcost;
	}close[N];
typedef struct Qnode
{
	int  data;
	struct Qnode *next;
}Qnode,*Queueptr;
typedef struct
{
	Queueptr front;
	Queueptr rear;
}Linkqueue; 
int Initqueue(Linkqueue &Q)
{
	Q.front=Q.rear=(Queueptr)malloc(sizeof(Qnode));
	if(!Q.front)
		exit(-2);
	Q.front->next=NULL;
	return 1;
}
int Enqueue(Linkqueue &Q,int e)
{   Queueptr p;
	p=(Queueptr)malloc(sizeof(Qnode));
	if(!p)
		exit(-2);
	p->data=e;p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return 1;
}
int Dequeue(Linkqueue &Q,int &e)
{   Qnode *p;
	if(Q.rear==Q.front)
		return -1;
	p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p)
		Q.rear=Q.front;
	free(p);
	return 1;
} 
/*MGraph CreateUDN()
{
	int k;
    MGraph G;
	int i,j;
	int w;
	printf("输入顶点数和边数：");
	scanf("%d %d",&G.vexnum,&G.arcnum);
	printf("依次输入顶点信息：");getchar();
	for(i=0;i<G.vexnum;i++)
		G.vexs[i]=getchar();
	getchar();
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;i++)
			G.arcs[i][j]=INFINITY;
		for(k=0;k<G.arcnum;k++)
		{
			printf("输入边依附的顶点和权值：");
			scanf("%d %d %d",&i,&j,&w);
			G.arcs[i][j]=w;
			G.arcs[j][i]=w;
		}
		return(G);
}
ALGraph CreateAdjlist()
{	
	ArcNode *s;
	int i,j,k;
	ALGraph G;
	printf("输入顶点数和边数：");
	scanf("%d %d",&G.vexnum,&G.arcnum);
	printf("依次输入顶点信息：");
	for(i=0;i<G.vexnum;i++)
	{
		G.vertice[i].data=getchar();
		G.vertice[i].firstarc=NULL;
	}
	for(k=0;k<G.arcnum;k++)
	{
		printf("输入边依附的顶点：");
		scanf("%d %d",&i,&j);
		s=(ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex=j;
		s->next=G.vertice[i].firstarc;
		G.vertice[i].firstarc=s;
		s=(ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex=i;
		s->next=G.vertice[j].firstarc;
		G.vertice[j].firstarc=s;
	}
	return(G);
}*/
void Create_UDN_ADJLIST(MGraph &M,ALGraph &A)
{
	int i,j,k,w;
	ArcNode *s;
	printf("请输入图的顶点数和边数:");
	scanf("%d%d",&M.vexnum,&M.arcnum);
	A.vexnum=M.vexnum;
	A.arcnum=M.arcnum;
    M.kind=A.kind=UDN;
	for(i=0;i<M.vexnum;i++)
	{
		printf("请输入顶点名称:");
		getchar();
		M.vexs[i]=getchar();
		A.vertice[i].data=M.vexs[i];
		A.vertice[i].firstarc=NULL;
	}
	for(i=0;i<M.vexnum;i++)
	{
		for(j=0;j<M.vexnum;j++)
		{
			M.arcs[i][j]=INFINITY;
		}
	}
	for(k=0;k<M.arcnum;k++)
	{
		printf("输入邻接的两点的序号和相应的权值:");
		scanf("%d%d%d",&i,&j,&w);
		M.arcs[i][j]=w;
		M.arcs[j][i]=w;
		s=(ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex=j;
		s->next=A.vertice[i].firstarc;
		A.vertice[i].firstarc=s;
		s=(ArcNode*)malloc(sizeof(ArcNode));
		s->adjvex=i;
		s->next=A.vertice[j].firstarc;
		A.vertice[j].firstarc=s;
	}
}
void dfs(ALGraph A,int v0,int visited[])
{
	ArcNode *p;
	visited[v0]=1;
	printf("%c",A.vertice[v0].data);
	p=A.vertice[v0].firstarc;
	while(p)
	{
		if(!visited[p->adjvex])
		{
			dfs(A,p->adjvex,visited);
		}
		p=p->next;
	}
}
void dfstraverse(ALGraph A,int visited[])
{
	int i,v;
	for(i=0;i<A.vexnum;i++)
	{
		visited[i]=0;
	}
	for(v=0;v<A.vexnum;v++)
	{
		if(!visited[v])
			dfs(A,v,visited);
	}
}
int minimum(MGraph G,close closedge)
{
	int min=INFINITY;
	int i,k;
	for(i=0;i<G.vexnum;i++)
	{
		if(closedge[i].lowcost!=0&&closedge[i].lowcost<min)
		{
			k=i;
			min=closedge[i].lowcost;
		}
	}
	return k;
}

void MiniSpanTree_PRIM(MGraph G,char u)
{
	int k,i,j,l=0;
	close closedge;
	while(G.vexs[l]!=u&&l<G.vexnum)
	{
		l++;
	}
	k=l;
	for(j=0;j<G.vexnum;j++)
	{
		if(j!=k)
		{
			closedge[j].adjvex=u;
			closedge[j].lowcost=G.arcs[k][j];
		}
		closedge[k].lowcost=0;
	}
	for(i=1;i<G.vexnum;i++)
	{
		k=minimum(G,closedge);
		printf("%c  %c",closedge[k].adjvex,G.vexs[k]);
		printf("\n");
		closedge[k].lowcost=0;
		for(j=0;j<G.vexnum;j++)
		{
			if(G.arcs[k][j]<closedge[j].lowcost)
			{
				closedge[j].adjvex=G.vexs[i];
				closedge[j].lowcost=G.arcs[k][j];
			}
		}
	}
}
void shorttestPast_PIJ(MGraph G,int v0,char p[N][N],int D[N])
{
	int final[N];
	int v,x,i,w,min;
	for(v=0;v<G.vexnum;v++)
	{
		final[v]=0;
		D[v]=G.arcs[v0][v];
		for(w=0;w<G.vexnum;w++)
		{
			p[v][w]=0;
		}
		if(D[N]<INFINITY)
		{
			p[v][v0]=1;p[v][v]=1;
		}
	}
	D[v0]=0;
	final[v0]=1;
	for(i=1;i<G.vexnum;i++)
	{
		min=INFINITY;
		for(w=0;w<G.vexnum;w++)
		{
			if(!final[w])
			{
				if(D[w]<min)
				{
					v=w;
					min=D[w];
				}
			}
		}
		final[v]=1;
		for(w=0;w<G.vexnum;w++)
		{
			if(!final[w]&&min+G.arcs[v][w]<D[w])
			{
				D[w]=min+G.arcs[v][w];
				for(x=0;x<G.vexnum;x++)
				{
					p[w][x]=p[v][x];
				}
				p[w][w]=1;
			}
		}
	}
}
void bfs(ALGraph G)      
{ 
	int v,u,w;
	ArcNode *p;
    Linkqueue  Q;
    int visited[N];
	for ( v=0; v<G.vexnum; v++) 
		visited[v]=0;
	Initqueue(Q);
    for ( v=0; v<G.vexnum; v++)
	{
		if ( !visited[v]) 
		{
			visited[v]=1; 
			printf("%c",G.vertice[v].data );
			Enqueue(Q, v);
		}
	}
	while (Q.front!=Q.rear)
	{  
		Dequeue(Q, u);
		p= G.vertice[u].firstarc;
		while (p!=NULL)
		{  
			w=p->adjvex;
			if (!visited[w])
			{
				visited[w]=1; 
				printf("%c", G.vertice[w].data );
				Enqueue(Q, w);   
			}  //if
        p=p->next;
      }  //while
   }  //while
}  
void main()
{
	MGraph M;
	ALGraph A;
	char p[N][N];
	int D[N];
	int visited1[N];
	int i,j;
    Create_UDN_ADJLIST(M,A);
	printf("dfs序列:");
    dfstraverse(A,visited1);
	printf("\n");
	printf("bfs序列:");
	bfs(A);
	printf("\n");
	printf("minispantree:\n");
	MiniSpanTree_PRIM(M,M.vexs[0]);
	printf("\n");
	printf("shortpast:\n");
	shorttestPast_PIJ(M,2,p,D);
	for(i=0;i<M.vexnum;i++)
	{
		for(j=0;j<M.vexnum;j++)
		{
			if(p[i][j]==1)
				printf("%c",M.vexs[j]);
		}
		printf("\n%d\n",D[i]);
	}
}