无向图的遍历演示两种遍历方式

以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，以用户的意愿为主选择遍历的方式，以用户的意愿为主看是否要推出程序。

#define MAX_NAME 3 // 顶点字符串的最大长度+1
 #define MAX_VERTEX_NUM 50
 typedef char VertexType[MAX_NAME]; // 字符串类型
 typedef int QElemType; // 队列类型

#include
#include
#include 
#include 
#include 
#include 

using namespace std;

int visite[MAX_VERTEX_NUM]; // 访问标志数组（全局量）
enum VisitIf{unvisitedvisited};
 
 struct EBox
 {
   VisitIf mark; // 访问标记
   int ivexjvex; // 该边依附的两个顶点的位置
   EBox *ilink*jlink; // 分别指向依附这两个顶点的下一条边
    };
 struct VexBox
 {
   string data;
   EBox *firstedge; // 指向第一条依附该顶点的边
 };
 struct AMLGraph
 {
   VexBox adjmulist[MAX_VERTEX_NUM];
   int vexnumedgenum; // 无向图的当前顶点数和边数
 };
 typedef struct QNode
 {
   QElemType data;
   QNode *next;
 }*QueuePtr;

 struct linkQueue
 {
   QueuePtr frontrear; // 队头、队尾指针
 };


int  CreateGraph（AMLGraph &G）;
int  LocateVex（AMLGraph Gstring u）;
void Display（AMLGraph G）;
void MarkUnvizited（AMLGraph G）;
void DFS（AMLGraph Gint v）;
int visit（string v）;
void BFSTraverse（AMLGraph Gint（*Visit）（string）int v）;
int InitQueue（linkQueue &Q）;
int DeQueue（linkQueue &QQElemType &e）;
int QueueEmpty（linkQueue Q）;
int EnQueue（linkQueue &QQElemType e）;
int NextAdjVex（AMLGraph Gstring vstring w）;
int FirstAdjVex（AMLGraph Gstring v）;
string GetVex（AMLGraph Gint v）;


int  CreateGraph（AMLGraph &G）
 { 
   int ijk;
   string vavb;
   EBox *p;
   printf（“请输入无向图G的顶点数边数（以逗号作为间隔）: “）;
   scanf（“%d%d“&G.vexnum&G.edgenum）;
   getchar（）;
   printf（“请输入%d个顶点的值:\n“G.vexnum）;
   for（i=0;i   {
     cin>>G.adjmulist[i].data;
	 G.adjmulist[i].firstedge=NULL;
   }
   
   printf（“请顺序输入每条边的两个端点（以空格作为间隔）:\n“）;
   for（k=0;k   {
    cin>>va>>vb; 
     i=LocateVex（Gva）; // 一端
     j=LocateVex（Gvb）; // 另一端
     p=（EBox*）malloc（sizeof（EBox））;
     p->mark=unvisited; // 设初值
     p->ivex=i;
     p->jvex=j;
     p->ilink=G.adjmulist[i].firstedge; // 插在表头
     G.adjmulist[i].firstedge=p;
     p->jlink=G.adjmulist[j].firstedge; // 插在表头
     G.adjmulist[j].firstedge=p; 
   }
   return 1;
 }

int LocateVex（AMLGraph Gstring u）
 { // 初始条件: 无向图G存在u和G中顶点有相同特征
   // 操作结果: 若G中存在顶点u则返回该顶点在无向图中位置;否则返回-1
   int i;
   for（i=0;i     if（u==G.adjmulist[i].data）
       return i;
   return -1;
 }

void Display（AMLGraph G）
 { // 输出无向图的邻接多重表G
   int i;
   EBox *p;
   MarkUnvizited（G）; // 置边的访问标记为未被访问
   printf（“%d个顶点：\n“G.vexnum）;
   for（i=0;i     cout<   printf（“\n%d条边:\n“G.edgenum）;
   for（i=0;i   {
     p=G.adjmulist[i].firstedge;
     while（p）
       {
         if（p->ivex==i） // 边的i端与该顶点有关
		{
         if（!p->mark） // 只输出一次
         {
           cout<jvex].data;
           p->mark=visited;
           printf（“\n“）;
          }
         p=p->ilink;
        
       }
        else   // 边的j端与该顶点有关
   

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        514  2009-09-08 18:42  tu8\tu8.dsw

     文件      41984  2009-09-15 22:37  tu8\tu8.ncb

     文件      74752  2009-09-15 22:36  tu8\Debug\vc60.idb

     文件     110592  2009-09-15 22:36  tu8\Debug\vc60.pdb

     文件     186928  2009-09-08 18:48  tu8\Debug\tu8.pch

     文件     532537  2009-09-15 22:36  tu8\Debug\tu8.exe

     文件    1106944  2009-09-15 22:36  tu8\Debug\tu8.pdb

     文件     150289  2009-09-15 22:36  tu8\Debug\8.obj

     文件     778116  2009-09-15 22:36  tu8\Debug\tu8.ilk

     文件        872  2009-09-15 22:36  tu8\tu8.plg

     文件       4246  2009-09-08 20:25  tu8\tu8.dsp

     文件       8725  2009-09-08 21:28  tu8\8.cpp

     文件      48640  2009-09-15 22:37  tu8\tu8.opt

     目录          0  2009-09-08 18:42  tu8\Debug

     目录          0  2009-09-08 18:42  tu8

----------- ---------  ---------- -----  ----

              3045139                    15