邻接表.txt

用邻接表实现个图的存储

#include<stdio.h>
#include<iostream.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>

#define MAX_VERTEX_NUM  20
#define MAXQSIZE 100

#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char Status;
typedef char VertexType;

typedef struct ArcNode{
	int            adjvex;
	struct ArcNode *nextarc;
	int             info;
}ArcNode;
typedef struct VNode{
	VertexType  data;
	ArcNode   *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
	AdjList  vertices;
	int       vexnum,arcnum;
}ALGraph;
typedef int QElemType;
typedef struct{
	QElemType  *base;
	int         front,rear;
}SqQueue;
Status InitQueue_Sq(SqQueue &Q){
	Q.base =(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)exit(OVERFLOW);
Q.front =Q.rear =0;
return OK;
}
Status LocateVex(ALGraph G,char u)
    {
	int i;
	for (i=0;i<G.vexnum;i++)
           { if(u==G.vertices[i].data) return i; }
	if (i==G.vexnum) {printf("Error u!\n");exit(1);}
	return 0;
	return OK;
    }

Status CreatALGraph_adjlist(ALGraph  &G)    //建立图的邻接表
{int i,j,k,w; char v1,v2;
ArcNode *p;
printf("InPut vexnum & arcnum:");
scanf("%d,%d",&G.vexnum,&G.arcnum );
printf("InPut vertices:");
for(i=0;i<G.vexnum;i++)
{scanf("%c",&G.vertices [i].data );
G.vertices[i].firstarc =NULL;
}
printf("InPut Arcs(v1,v2&w):\n");
for(k=0;k<G.arcnum;k++)
{scanf("%c%c%d",&v1,&v2,&w);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info=w;
p->nextarc =G.vertices [i].firstarc ;
G.vertices [i].firstarc =p;
}
	return OK;
}
int visited[MAX_VERTEX_NUM];
Status DFS(ALGraph G, int v)
{ ArcNode *p;
   printf("%c",G.vertices[v].data);
   visited[v]=1;
    p=G.vertices[v].firstarc;
    while (p)
        {if (!visited[p->adjvex]) DFS(G,p->adjvex);
	 p=p->nextarc;
	}
	return OK;
}		
Status DFSTraverse(ALGraph G)  //深度遍历邻接表
{for (int v=0;v<G.vexnum;++v)
		visited[v]=0;
	for (v=0;v<G.vexnum;++v)
		if (!visited[v]) DFS(G,v);
	return OK;
}
Status BFS(ALGraph G,int v)
  { ArcNode *p;	SqQueue Q;
    InitQueue_Sq(Q);
    printf("%c",G.vertices[v].data);
    visited[v]=1;
   Q.base[Q.rear]=v;
   Q.rear=(Q.rear+1)%MAXQSIZE;
   while (Q.front!=Q.rear)
       { v=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXQSIZE;
	p=G.vertices[v].firstarc;
while (p)
     {	if (!visited[p->adjvex])
           { printf("%c",G.vertices[p->adjvex].data);
	    visited[p->adjvex]=1;
	    Q.base[Q.rear]=p->adjvex;
	    Q.rear=(Q.rear+1)%MAXQSIZE;
	  }
     p=p->nextarc;
     }
   }
   return OK;
}
Status BFSTraverse(ALGraph G)  //广度遍历邻接表
{for (int v=0;v<G.vexnum;++v) 
		visited[v]=0;
	for (v=0;v<G.vexnum;++v)
		if (!visited[v]) BFS(G,v);
	return OK;
}
int scan()
{
 int d;
    printf("请选择所要进行的操作\n");
    printf("1.建立图的邻接表             2.  深度遍历邻接表 ");
    printf("3. 广度遍历邻接表     \n");
    printf("4.  退出\n"); 
   cin>>d;
  return d;
}
void main()
{ int quit=0;
  char ch;
  ALGraph G;
 cout<<("第一次操作需选择初始化\n")<<endl;
  while(!quit)
  switch(scan())
  {case 1:CreatALGraph_adjlist(G);break;
   case 2:DFSTraverse(G);break;
   case 3:BFSTraverse(G);break;
   case 0:quit=1;}