adjmulist.h

用标准C++完成对图的深/广度优先搜索,使用邻接多重表的存储结构

#ifndef ADJMULIST_H
#define ADJMULIST_H
#include <iostream>
#include <string>
using std::string;

/* 无向图的邻接多重表存储表示 */
 #define MAX_VERTEX_NUM 20
// #define MAX_NAME 5
 typedef char InfoType;
 typedef string VertexType;
 typedef enum{unvisited,visited}VisitIf;
 typedef struct EBox
 {
   VisitIf mark; /* 访问标记 */
   int ivex,jvex; /* 该边依附的两个顶点的位置 */
   struct EBox *ilink,*jlink; /* 分别指向依附这两个顶点的下一条边 */
   InfoType* info; /* 该边信息指针，可指向权值或其他信息 */
 }EBox;
 typedef struct
 {
   VertexType data;
   EBox *firstedge; /* 指向第一条依附该顶点的边 */
 }VexBox;
 typedef struct
 {
   VexBox adjmulist[MAX_VERTEX_NUM];
   int vexnum,edgenum; /* 无向图的当前顶点数和边数 */
 }AMLGraph;

 int LocateVex(AMLGraph& G,VertexType u);
 void CreateGraph(AMLGraph &G);
 VertexType& GetVex(AMLGraph G,int v);
 int PutVex(AMLGraph &G,VertexType v,VertexType value);
 int FirstAdjVex(AMLGraph& G,VertexType v);
 int NextAdjVex(AMLGraph& G,VertexType v,VertexType w);
 int InsertVex(AMLGraph& G,VertexType v);
 int DeleteArc(AMLGraph& G,VertexType v,VertexType w);
 int DeleteVex(AMLGraph& G,VertexType v);
 void DestroyGraph(AMLGraph& G);
 int InsertArc(AMLGraph& G,VertexType v,VertexType w);
 void DFS(AMLGraph& G,int v);
 void DFSTraverse(AMLGraph& G,void(*visit)(VertexType));
 void BFSTraverse(AMLGraph& G,void(*Visit)(VertexType));
 void MarkUnvizited(AMLGraph& G);
 void Display(AMLGraph& G);

#endif