数据结构：图实验

实验目标：

提示

（1）在图G的顶点数组中查找顶点V，返回顶点的下标

（2）采用邻接矩阵表示法，构造无向网G

（3）显示图G的邻接矩阵,即按行列输出二维数组

（4）求顶点v在图G中的第一个邻接点

（5）求顶点v在图G中邻接点w的下一个邻接点

（6）对图G进行深度优先遍历

（7）从v顶点出发对图G进行深度优先遍历的递归算法

（8）对图G进行广度优先遍历

---

实验代码

#include <bits/stdc++.h>
using namespace std;

#define INFINITY 0x7fffffff
#define MAX_VERTEX_NUM 20
#define MAXQSIZE 20
#define OK       1
#define ERROR    0
#define TRUE     1
#define FALSE    0

typedef char VertexType;
typedef enum {UDN} GraphKind;
bool visited[MAX_VERTEX_NUM];

typedef struct
{
    VertexType vexs[MAX_VERTEX_NUM];
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum, arcnum;
    GraphKind kind;
} MGraph;

typedef struct
{
    int *base;
    int front, rear;
} SqQueue;

int InitQueue ( SqQueue &Q )
{
    //构造一个空队列Q
    Q.base = new int[MAXQSIZE];
    if ( !Q.base ) exit ( 0 );
    Q.front = Q.rear = 0; 
    return OK;
}

int EnQueue ( SqQueue &Q, int e )
{
    //插入元素e为Q的新的队尾元素
    if ( ( Q.rear + 1 ) % MAXQSIZE == Q.front )
        return 0;
    Q.base[Q.rear] = e;
    Q.rear = ( Q.rear + 1 ) % MAXQSIZE;
    return OK;
}

int DeQueue ( SqQueue &Q, int &e )
{
    //删除Q的队头元素，用e返回其值
    if ( Q.front == Q.rear ) return 0;
    e = Q.base[Q.front];
    Q.front = ( Q.front + 1 ) % MAXQSIZE;
    return OK;

}

int QueueEmpty ( SqQueue &Q )
{
    if ( Q.front == Q.rear )   return true;
    else return 0;
}

int LocateVex ( MGraph G, VertexType v )// 在图 G 的顶点数组中查找顶点 V，返回顶点的下标
{
    for ( int i = 0; i < G.vexnum; ++i )
        if ( G.vexs[i] == v )
            return i;
    return -1;
}

bool CreateUDN ( MGraph &G )//采用邻接矩阵表示法，构造无向网 G
{
    int i, j, k;
    cout << "请输入总顶点数，总边数，以空格隔开：";
    cin >> G.vexnum >> G.arcnum;							
    cout << endl;

    cout << "输入点的名称，如a" << endl;

    for ( i = 0; i < G.vexnum; ++i ){
        cout << "请输入第" << ( i + 1 ) << "个点的名称:";
        cin >> G.vexs[i];                        			
    }

    cout << endl;

    for ( i = 0; i < G.vexnum; ++i )                			
        for ( j = 0; j < G.vexnum; ++j )
            G.arcs[i][j] = INFINITY;

    cout << "输入边依附的顶点及权值，如 a b 5" << endl;
    
    for ( k = 0; k < G.arcnum; ++k ) 
    {
        VertexType v1, v2;
        int w;
        cout << "请输入第" << ( k + 1 ) << "条边依附的顶点及权值:";
        cin >> v1 >> v2 >> w;
        i = LocateVex ( G, v1 );
        j = LocateVex ( G, v2 );
        G.arcs[i][j] = w;
        G.arcs[j][i] = G.arcs[i][j];
    }
    return OK;
}


void Display ( MGraph G )//显示图 G 的邻接矩阵,即按行列输出二维数组
{
    for ( int i = 0; i < G.vexnum; ++i )
    {
        for ( int j = 0; j < G.vexnum; ++j )
        {
            if ( G.arcs[i][j] != 0x7fffffff )
                cout <<setw(5)<< G.arcs[i][j];
            else
                cout <<setw(5)<< "0";
        }
        cout << endl;
    }
}


int FirstAdjVex ( MGraph G, int v )//求顶点 v 在图 G 中的第一个邻接点
{
    int i;
    for ( i = 0; i < G.vexnum; i++ )
    {
        if ( G.arcs[v][i] && visited[i] == false );
        return i;
    }

    if ( i == G.vexnum )
        return -1;
}

int NextAdjVex ( MGraph G, int v, int w )//求顶点 v 在图 G 中邻接点 w 的下一个邻接点
{
    int i;
    for ( i = w - 1; i < G.vexnum; i++ )
        if ( G.arcs[v][i] && visited[i] == false )
            return i;
    if ( i == G.vexnum )
        return -1;

}

void DFS ( MGraph G, int v )//从 v 顶点出发对图 G 进行深度优先遍历的递归算法
{
    cout << G.vexs[v] << " ";
    visited[v] = 1;
    for ( int w = 1; w <= G.vexnum; w++ )
        if ( ( G.arcs[v][w] != 0 ) && ( !visited[w] ) )
            DFS ( G, w );
}

void DFSTraverse ( MGraph G )// 对图 G 进行深度优先遍历
{
    int v;
    for ( v = 0; v < G.vexnum; ++v )
        visited[v] = 0;
    for ( v = 0; v < G.vexnum; ++v )
        if ( !visited[v] )
            DFS ( G, v ); 
}

void BFSTraverse ( MGraph G )//对图 G 进行广度优先遍历
{
    SqQueue Q;
    int v, u, w;
    for ( v = 0; v < G.vexnum; ++v )
        visited[v] = false;
    InitQueue ( Q );

    for ( v = 0; v < G.vexnum; ++v )
    {
        if ( !visited[v] )
        {
            visited[v] = true;
            cout << G.vexs[v] << " ";
            EnQueue ( Q, v );
            while ( !QueueEmpty ( Q ) )
            {
                DeQueue ( Q, u );
                for ( w = FirstAdjVex ( G, u ); w >= 0; w = NextAdjVex ( G, u, 1 ) )
                {
                    if ( !visited[w] )
                    {
                        visited[w] = true;
                        cout << G.vexs[w] << " ";
                        EnQueue ( Q, w );
                    }
                }
            }
        }
    }
}
int main ( void )
{
    MGraph G;
    int c = 0;
    while ( c != 5 )
    {
        cout << endl << "1. 采用邻接矩阵表示法，构造无向网G";
        cout << endl << "2. 显示图G的邻接矩阵,即按行列输出二维数组";
        cout << endl << "3. 对图G进行深度优先遍历";
        cout << endl << "4. 对图G进行广度优先遍历";
        cout << endl << "0. 退出";
        cout << endl << "请输入您的选择:";
        cin >> c;
        switch ( c )
        {
        case 1:
            CreateUDN ( G );
            break;
        case 2:
            Display ( G );
            break;
        case 3:
            DFSTraverse ( G );
            break;
        case 4:
            BFSTraverse ( G );
            break;
        case 0:
            exit(0);
        }
    }
}