数据结构——图的邻接表

#include 
   #include  
   #include 
   using namespace std;
   #define OK 1
   #define ERROR 0
   #define OVERFLOW -1
   typedef int Status;
   #define MVNum 20    			//最大顶点数
typedef char VertexType;		//顶点类型 
typedef int InfoType;           //权值类型 
typedef  struct ArcNode{
     int adjvex;                //该边所指向的顶点的位置 
     InfoType weight;           //权（和边相关的信息） 
     struct ArcNode *nextarc;   //指向下一条边的指针（递归结构体） 
}ArcNode;//边结点 

typedef struct VNode{
     VertexType  data;          //顶点值 
     ArcNode     *firstarc;     //一个指针，指向以该点为起始点的第一条边 
}VNode, AdjList[MVNum];  //表头结点 ，AdjList代表邻接表的类型 

typedef struct {
     int kind;		//图的类型
	 int  vexnum,arcnum;   //图的顶点数、边数 
	 VNode vertices[MVNum];   //顶点向量表（重点），每个元素是顶点结点 
}ALGraph; //图 

#define MAXQSIZE 100
typedef char QElemType;
typedef struct{
	QElemType *base;
	int front;
	int rear;
}SqQueue;
SqQueue Q;

//顶点查找函数，返回v在顶点数组中的下标 
int LovateVex(ALGraph G,VertexType v){
   int i;	
   for (i=0;i>G.vexnum>>G.arcnum;
    cout<>G.vertices[i].data;		//输入顶点信息 
		G.vertices[i].firstarc=NULL;	//初始化每个顶点的邻接表（为空） 
	}
	
    cout<>v1>>v2>>w;                    //输入一条边依附的两个结点 
			 i=LovateVex(G,v1);                 //确定v1，v2在图中的位置，即顶点在G.vertices中的编号 
			 j=LovateVex(G,v2); 
			 if (i==-1 ||j==-1) {
				cout<<"n顶点有误,程序退出！";
				return ERROR;	
			 }  
			 
			 p=new ArcNode;                //生成一个新的边结点*p
			 p->adjvex=j;                  //邻接点序号为j  
			 p->weight=w;                  //该边对应的权为w 
			 p->nextarc=G.vertices[i].firstarc;
             G.vertices[i].firstarc=p;      //用头插法将*p插入顶点v1的边表中 
             
			 q=new ArcNode;                  //成另一个对称新的边结点*q 
			 q->adjvex=i;                    //邻接点序号为j  
			 q->weight=w;
			 q->nextarc=G.vertices[j].firstarc; 
             G.vertices[j].firstarc=q;       //用头插法将*q插入顶点v2的边表中 
			
	}//for k
   return OK;
 }//CreateUDN
 
 //创建无向图 
Status CreateUDG(ALGraph &G){
		int i,j,k;
    VertexType v1,v2;
	ArcNode *p,*q;
	cout<>G.vexnum>>G.arcnum;
    cout<>G.vertices[i].data;		//输入顶点信息 
		G.vertices[i].firstarc=NULL;	//初始化每个顶点的邻接表（为空） 
	}
    cout<>v1>>v2;                    //输入一条边依附的两个结点 
			 i=LovateVex(G,v1);   //确定v1，v2在图中的位置，即顶点在G.vertices中的编号 
			 j=LovateVex(G,v2); 
			 if (i==-1 ||j==-1) {
				cout<<"n顶点有误,程序退出！";
				return ERROR;	
			 }  
			 p=new ArcNode;                //生成一个新的边结点*p
			 p->adjvex=j;                  //邻接点序号为j  
			 p->nextarc=G.vertices[i].firstarc;
             G.vertices[i].firstarc=p;      //用头插法将*p插入顶点v1的边表中 
             
			 q=new ArcNode;                  //成另一个对称新的边结点*q 
			 q->adjvex=i;                    //邻接点序号为j  
			 q->nextarc=G.vertices[j].firstarc; 
             G.vertices[j].firstarc=q;       //用头插法将*q插入顶点v2的边表中 
			
	}//for k
   return OK;
 }//CreateUDG

//创建有向图 
Status CreateDG(ALGraph &G){
	int i,j,k;
    VertexType v1,v2;
	ArcNode *p,*q;
	cout<>G.vexnum>>G.arcnum;
    cout<>G.vertices[i].data;		//输入顶点信息 
		G.vertices[i].firstarc=NULL;	//初始化每个顶点的邻接表 
	}
    cout<>v1>>v2;
			 i=LovateVex(G,v1);  
			 j=LovateVex(G,v2); 
			 if (i==-1 ||j==-1) {
				cout<<"n顶点有误,程序退出！";
				return ERROR;	
			 }  
			 p=new ArcNode; 
			 p->adjvex=j;
			 p->nextarc=G.vertices[i].firstarc;
             G.vertices[i].firstarc=p;
         }
   return OK;
 }//CreateDG

//创建有向网 
Status CreateDN(ALGraph &G)
{
	int i,j,k;
    VertexType v1,v2;
	InfoType w;
	ArcNode *p,*q;
	cout<>G.vexnum>>G.arcnum;
    cout<>G.vertices[i].data;		//输入顶点信息 
		G.vertices[i].firstarc=NULL;	//初始化每个顶点的邻接表 
	}
    cout<>v1>>v2>>w;
			 i=LovateVex(G,v1);  
			 j=LovateVex(G,v2); 
			 if (i==-1 ||j==-1) {
				cout<<"n顶点有误,程序退出！";
				return ERROR;	
			 }  
			 p=new ArcNode; 
			 p->adjvex=j;
			 p->weight=w;
			 p->nextarc=G.vertices[i].firstarc;
             G.vertices[i].firstarc=p;
         }
   return OK;
 }//CreateDN

Status CreateGraph(ALGraph &G){
   cout<>G.kind;
   switch (G.kind){
       	case  1	:return CreateDG(G);
       	case  2	:return CreateDN(G);
       	case  3	:return CreateUDG(G);
       	case  4	:return CreateUDN(G);
       	default :return ERROR;
   }
   return OK;
}//CreateGraph

void FindIndegree(ALGraph G,int indegree[]){
   //计算有向图（网）的入度 
   int num=0;
   ArcNode *p;
   p=new ArcNode;
   for (int i=0;inextarc)
   		indegree[p->adjvex]++;
   }
   for (int i=0;inextarc)
   			outdegree[i]++;
   }
   for (int i=0;inextarc){
			degree[i]++;
			degree[p->adjvex]++;
		}
	}
	for (int i=0;inextarc){
			j=p->adjvex;
		   	cout<adjvex;
		if (!visited[w])
			DFS(G,w);
		p=p->nextarc;
	}

}//DFS 

void DFSTraverse(ALGraph G){
 // 对图G进行深度优先搜索
   int v=0;
   for (v=0;vadjvex;
			cout<>choice;
		switch (choice){
			case 1: GraphDegree(G);				
					break;
			case 2: DFSTraverse(G);			
					break;
			case 3: BFSTraverse(G); 
					break;
			default:break;
		}
	cout<