bianli.cpp

图的遍历

#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INFINITY INT_MAX  100              // 最大值∞
#define MAX_VERTEX_NUM 20             // 最大顶点个数
#define ERROR 0
#define OK 1
#define FALSE 0
#define TRUE 1
#define OVERFLOW 0
typedef int Status, QElemType;
int  visited[MAX_VERTEX_NUM]; // 访问标志数组
void (* VisitFunc)(int v);      // 函数变量
//typedef enum { DG,DNU,DN,UDN } GraphKind;
                            // { 有向图,有向网,无向图,无向网 }
typedef struct ArcCell
 {   int adj;         // VRType是顶点关系类型，对无权图，用1
                     //或0表示相邻否；对带权图，则为权值类型
     //int  *info;  // 该弧相关信息的指针
} ArcCell,AdjMatrix [MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct MGraph
{
    char vexs[MAX_VERTEX_NUM]; // 顶点向量
    AdjMatrix arcs;                // 邻接矩阵
    int vexnum;
    int arcnum;    // 图的当前顶点数和弧(边)数
   // char  kind;               // 图的种类标志
}MGraph;
typedef struct
{
    int *base;
    int front;
    int rear;
}SqQueue;
//--- 图的邻接矩阵 ---
int LocateVex(MGraph G, char v)
{
    int i;
    for(i=0; i<G.vexnum; i++)
        if(G.vexs[i]==v)  return i;
    return ERROR;
}
int CreateUDG (MGraph &G)     //创建无向网的邻接矩阵
{
    int i, j, k;
   // int w, IncInfo ;
    char  v1, v2, V;
    printf("input the number for vexnum and arcnum:  ");
    scanf("%d,%d", &G.vexnum, &G.arcnum);
    //IncInfo=0;       // IncInfo=0表示各弧不含其他信息
    V=getchar();     //为了滤掉前面输入的空格符，后面亦同此原因
    printf("input %d char for vexs \n",G.vexnum);
    for(i=0; i<G.vexnum; ++i)    //输入网中所有顶点
    {
        printf("%d:   ",i);
        G.vexs[i]=getchar();
        V=getchar();
    }
    for(i=0; i<G.vexnum; ++i)       //初始化邻接矩阵
    for(j=0; j<G.vexnum; ++j)
    {
        G.arcs[i][j].adj= 0;
//G.arcs[i][j].info = NULL;
    }
    printf("input %d arc(char,char)\n", G.arcnum);
    for(k=0; k<G.arcnum; ++k)
    {
        printf("%d:\n",k);
        printf("   ");
        scanf("%c,%c", &v1,&v2); //输入一条弧的两个顶点以及权
        V=getchar();
        V=V;
        i = LocateVex(G,v1);//确定v1 v2在G中的位置
        j = LocateVex(G,v2);
        if(i!=100 && j!=100)
        {
	      // if(IncInfo) scanf("%s" , G.arcs[i][j]);
            G.arcs[j][i].adj = G.arcs[i][j].adj=1 ;
	    } //if
     } //for
    return OK;
}
//--- 图的邻接矩阵 ---
//--- 图的深度优先算法 ---
//--- 下列算法使用两个的全局变量 ---
// FirstAdjVex(G, u)寻找u的第一个邻接点，并返回其下标位置
// NextAdjVex(G, u, w) w是u的一个邻接点，寻找u的所有邻接点中位于w后面的那一个，并返回其下标位置
int FirstAdjVex(MGraph G, int v)
{
    int i=0;
    while(i<G.vexnum)
    {
        if(G.arcs[v][i].adj==1)
            return(i);
        i++;
    }
    return -1;
}
int NextAdjVex(MGraph G,int v,int w)
{
    int i;
    i=w+1;
    while(i<G.vexnum)
    {
        if(G.arcs[v][i].adj==1)
            return(i);
         i++;
    }
    return -1;
}
void visit(MGraph G,int v)
{
    printf("%c-->",G.vexs[v]);
}
void DFS (MGraph G, int v)
{   // 从第v个顶点出发递归地深度优先遍历图G。
    int w;
    visited[v] = TRUE;
    visit(G,v); // 访问第v个顶点
    for (w=FirstAdjVex(G, v); w!=-1 ; w=NextAdjVex(G, v, w) )
    {
        if (!visited[w])
            DFS(G, w);
    }
// 对v的尚未访问的邻接顶点w递归调用DFS
}
void DFSTraverse(MGraph G)
{      // 对图G作深度优先遍历。
    int v;
    printf("深度优先遍历顺序：");
    for (v=0; v<G.vexnum; ++v)
        visited[v] = FALSE;           // 访问标志数组初始化
    for (v=0; v<G.vexnum; ++v)      //***寻找其它未访问过的树 ***
        if (!visited[v])
            DFS(G, v);   // 对尚未访问的顶点调用DFS
    printf("\b\b\b    ");
}
//--- 图的深度优先算法 ---
//--- 广度有限算法---
Status InitQueue(SqQueue &Q) //构造一个空队列Q
{
    Q.base=(QElemType*) malloc(MAX_VERTEX_NUM*sizeof(QElemType));
    if(!Q.base)exit(OVERFLOW);
    Q.front=Q.rear=0;
    return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)    //插入元素e为Q的新的队尾元素
{
    Q.base[Q.rear]=e;
    Q.rear=Q.rear+1;
    return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{
    if(Q.front==Q.rear)  return ERROR;
    e=Q.base[Q.front];
    Q.front=Q.front+1;
    return OK;
}
Status QueueEmpty(SqQueue Q)
{
    if(Q.front==Q.rear)
        return FALSE;
    return OK;
}
void BFSTraverse(MGraph G)
{  // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。
    SqQueue Q;
    int u,w;
    printf("广度优先遍历顺序：");
    for (u=0; u<G.vexnum; ++u)
        visited[u] = FALSE;
    InitQueue(Q);     // 置空的辅助队列Q
    for ( u=0; u<G.vexnum; ++u )   //***寻找其它未访问过的树 ***
        if (!visited[u])
        {
            EnQueue(Q, u);
            visited[u] = TRUE;
            visit( G,u)   ;
            while (!QueueEmpty(Q))
            {
                DeQueue(Q, u);
                for ( w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G, u, w) )
                    if ( ! visited[w])
                        EnQueue(Q, w);
            };  //while
        }  //if
    printf("\b\b\b    ");
} // BFSTraverse　
//--- 广度有限算法---
void main()
{
      MGraph G;
      CreateUDG (G) ;
      int i,j;
      for(i=0; i<G.vexnum; i++)
      {
        for(j=0; j<G.vexnum; j++)
            printf("%5d", G.arcs[i][j].adj);
         printf("\n");
      }
      DFSTraverse(G) ;
      printf("\n");
      BFSTraverse(G) ;
      printf("\n");
}