graph.cpp

数据结构经典课件(附带各章的经典算法) 具体代码是使用C语言编写的

#include <stdio.h>
#include <malloc.h>
#define INF 32767       /*INF表示∞*/

typedef int InfoType;
typedef char Vertex;
#define	MAXV 6				/*最大顶点个数*/
/*以下定义邻接矩阵类型*/

typedef struct  				/*图的定义*/
{  	InfoType edges[MAXV][MAXV]; 		/*邻接矩阵*/
   	int n,e;   					/*顶点数，弧数*/
	Vertex vexs[MAXV];		/*存放顶点信息*/
} MGraph;						/*图的邻接矩阵类型*/

/*以下定义邻接表类型*/
typedef struct ANode           	/*弧的结点结构类型*/
{	int adjvex;              	/*该弧的终点位置*/
   	struct ANode *nextarc; 		/*指向下一条弧的指针*/
   	InfoType info;           	/*该弧的相关信息,这里用于存放权值*/
} ArcNode;

typedef struct Vnode      		/*邻接表头结点的类型*/
{	Vertex data;            	/*顶点信息*/
    ArcNode *firstarc;     		/*指向第一条弧*/
} VNode;
typedef VNode AdjList[MAXV];	/*AdjList是邻接表类型*/
typedef struct 
{	AdjList adjlist;         	/*邻接表*/
    int n,e;                 	/*图中顶点数n和边数e*/
} ALGraph;                   	/*图的邻接表类型*/

typedef struct
	{  char vi,vj;
       int  info;
	}etype;

void MatToList(MGraph g,ALGraph *&G)
/*将邻接矩阵g转换成邻接表G*/
{
	int i,j,n=g.n;						
	ArcNode *p;
	G=(ALGraph *)malloc(sizeof(ALGraph));
	for (i=0;i<n;i++)					
	{
		G->adjlist[i].firstarc=NULL;
		G->adjlist[i].data=g.vexs[i];
	}

	for (i=0;i<n;i++)					
		for (j=n-1;j>=0;j--)
			if (g.edges[i][j]!=INF)				
			{   
			   	p=(ArcNode *)malloc(sizeof(ArcNode));	
				p->adjvex=j;
				p->info=g.edges[i][j];
				p->nextarc=G->adjlist[i].firstarc;		
				G->adjlist[i].firstarc=p;
			}
	G->n=n;G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
/*将邻接表G转换成邻接矩阵g*/
{
	int i,j,n=G->n;
	ArcNode *p;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			g.edges[i][j]=INF;
	for (i=0;i<n;i++) 
	{	g.vexs[i]=G->adjlist[i].data;
		p=G->adjlist[i].firstarc;
	    while (p!=NULL) 
		{	
			g.edges[i][p->adjvex]=p->info;
		    p=p->nextarc;
		}
	}
	g.n=n;g.e=G->e;
}
void DispMat(MGraph g)
/*输出邻接矩阵g*/
{
	int i,j;
	for (i=0;i<g.n;i++)
	{
		for (j=0;j<g.n;j++)
			if (g.edges[i][j]==INF)
				printf("%3s","∞");
			else
				printf("%3d",g.edges[i][j]);
		printf("\n");
	}
}
void DispAdj(ALGraph *G)//不改变G的指向(不进行修改)返回时G仍然指向原来的位置
/*输出邻接表G*/
{
	int i;
	ArcNode *p;
	for (i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
	    printf("\n%3d  %c  : ",i,G->adjlist[i].data );
		while (p!=NULL)
		{
			printf("-->%c(%d)",G->adjlist[p->adjvex].data,p->info);
			p=p->nextarc;
		}
		printf("\n");
	}
}

void creatmat(MGraph &g,char vex[],int n,etype edge[],int e)//无向图，改变G的指向(即进行修改)返回时G指向新的位置
//建立邻接矩阵
{	g.n=n;g.e=e;
    int k,i,j;
	for(k=0;k<n;k++)
	    g.vexs[k]=vex[k];
    for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			g.edges[i][j]=INF;
	for(k=0;k<e;k++)
	   {  i=0;
	      while(g.vexs[i]!=edge[k].vi)  
			  i++;
		  j=0;
		  while(g.vexs[j]!=edge[k].vj)
			  j++;
		  g.edges[i][j]=g.edges[j][i]=edge[k].info;
	}
}
void creatlink(ALGraph *&G,char vex[],int n,etype edge[],int e)//无向图，改变G的指向(即进行修改)返回时G指向新的位置
//建立邻接表
{	ArcNode *p;
	G=(ALGraph *)malloc(sizeof(ALGraph));
	G->n=n;G->e=e;
	int k,i,j;
	for (i=0;i<n;i++)					
	{
		G->adjlist[i].firstarc=NULL;
		G->adjlist[i].data=vex[i];
	}
	for(k=0;k<e;k++)
	   {  i=0;
	      while(G->adjlist[i].data !=edge[k].vi)  
			  i++;
		  j=0;
		  while(G->adjlist[j].data !=edge[k].vj)
			  j++;   
  	   	p=(ArcNode *)malloc(sizeof(ArcNode));	
		p->adjvex=j;
		p->info=edge[k].info;
		p->nextarc=G->adjlist[i].firstarc;		
		G->adjlist[i].firstarc=p;
  	   	p=(ArcNode *)malloc(sizeof(ArcNode));	
		p->adjvex=i;
		p->info=edge[k].info;
		p->nextarc=G->adjlist[j].firstarc;		
		G->adjlist[j].firstarc=p;
	}
}
char dfsv[10];
char bfsv[10];
int k;
int visited[10];
void DFS(ALGraph *G,int v)
{
   ArcNode *p;
   int w;
   dfsv[k]=G->adjlist[v].data;k++;
   visited[v]=1;
   p=G->adjlist[v].firstarc;
   while(p!=NULL)
     { w=p->adjvex;
       if(visited[w]==0)
	    DFS(G,w);
       p=p->nextarc;
     }
}
void BFS(ALGraph *G,int v)
{
  int q[MAXV],front,rear,i,w;
  ArcNode *p;
  front=rear=-1;
  k=0;
  bfsv[k++]=G->adjlist[v].data;
  visited[v]=1;
  rear++; q[rear]=v;
  while(front<rear)
     {  front++; i=q[front];
	    p=G->adjlist[i].firstarc;
        while(p!=NULL)
          { w=p->adjvex;
            if(visited[w]==0)
               {bfsv[k++]=G->adjlist[w].data;
                visited[w]=1;
                rear++;q[rear]=w;
               }
            p=p->nextarc;
          }
    }
}				
//以下主函数用作调试
void main()
{
	
	MGraph g,g1;
	char vex[]="abcdef";
    etype edge[]={{'a','b',4}, {'a','e',19}, {'a','f',8}, 
	{'b','c',2},{'b','d',6},{'c','d',3},{'d','e',10},{'d','f',7}};

	ALGraph *G,*G1;
	creatmat(g,vex,6,edge,8);
	printf("\n");
	printf(" 有向图G的邻接矩阵:\n");
	DispMat(g);

    creatlink(G,vex,6,edge,8);
	printf(" 图G的邻接矩阵转换成邻接表:\n");
	DispAdj(G);
 
	printf(" 图G的邻接矩阵转换成邻接表:\n");
	MatToList(g,G1);
	DispAdj(G1);

	printf(" 图G的邻接表转换成邻接邻阵:\n");
	ListToMat(G,g1);
	DispMat(g1);
	printf("\n");
	int i;
	for(i=0;i<MAXV;i++)
       visited[i]=0;
	DFS(G,0);
    for(i=0;i<MAXV;i++)
       visited[i]=0;
	BFS(G,0);

}