graph1.h

数据结构的应用

#include <iostream.h>
typedef int dataType;                  //抽象数据类型dataType定义为int
#include "Queue1.h"                    //顺序循环队列类

struct EdgeNode1                       //带权值的边
{
    int init;                          //边的起点
    int end;                           //边的终点
    int weight;                        //边的权值
};

class Graph1                           //邻接矩阵图类
{
  private:
    int visited[MaxSize];              //访问标记数组
    void unvisited();                  //设置未访问标记 
    void depthfs(int k);               //从结点k开始的深度优先遍历
    void breadthfs(int k);             //从结点k开始的广度优先遍历

  public:
    char vertex[MaxSize];              //图的结点集，MaxSize为最大结点数
    int mat[MaxSize][MaxSize];         //图的邻接矩阵
    int vertCount;                     //图的结点数
    int edgeCount;                     //图的边数

    Graph1();                          //初始化图的结点集和邻接矩阵
    ~Graph1(){}                        //析构函数为空

    void createGraph(int n,char vert[],int m,EdgeNode1 edge[]);
                                       //以结点集和边集构造一个图
    friend ostream& operator<<(ostream& out,Graph1 &g1);
                                       //输出图的结点集和邻接矩阵

    void depthFirstSearch();           //图的深度优先遍历
    void breadthFirstSearch();         //图的广度优先遍历


    void insertVertex(char vert);      //插入结点
    void insertEdge(EdgeNode1 e);      //插入边
    void insertEdge(int init,int end,int w);
                                       //插入边
    void removeVertex(char vert);      //删除结点
    void removeEdge(EdgeNode1 e);      //删除边
    void removeEdge(int init,int end); //删除边
};

Graph1::Graph1()                       //初始化图的结点集和邻接矩阵
{
    int i,j;
    for(i=0;i<MaxSize;i++)             //初始化图的结点集
        vertex[i]=' ';

    for(i=0;i<MaxSize;i++)             //初始化图的邻接矩阵
        for(j=0;j<MaxSize;j++)
            if(i==j)
                mat[i][j]=0;           //数据元素权值为0
            else
                mat[i][j]=MaxWeight;   //权值为无穷大
    vertCount=0;                       //当前结点数为0
    edgeCount=0;                       //当前边数为0
}

void Graph1::createGraph(int n,char vert[],int m,EdgeNode1 edge[])
{                                      //以结点集和边集构造一个图
    vertCount=n;                       //图的结点个数
    int i,j,k;
    for(i=0;i<n;i++)                   //初始结点加入结点集
        vertex[i]=vert[i];

    edgeCount=m;                       //图的边数
    for(k=0;k<m;k++)                   //初始边值加入邻接矩阵
    {
        i=edge[k].init;                //边的起点
        j=edge[k].end;                 //边的终点
        mat[i][j]=edge[k].weight;      //边的权值
    }
}

ostream& operator<<(ostream& out,Graph1 &g1)
{                                      //输出图的结点集和邻接矩阵
    cout<<"图的结点集为 {";
    int i,j;
    for(i=0;i<g1.vertCount-1;i++)
        cout<<g1.vertex[i]<<", ";
    cout<<g1.vertex[i]<<"}"<<endl;

    cout<<"图的邻接矩阵为"<<endl;
    for(i=0;i<g1.vertCount;i++)
    {
        for(j=0;j<g1.vertCount;j++)
            cout<<g1.mat[i][j]<<"\t  ";
        cout<<endl;
    }
    return out;
}

void Graph1::unvisited()               //设置未访问标记 
{
    for(int i=0;i<vertCount;i++)
        visited[i]=0;
}

void Graph1::depthfs(int k)            //从结点k开始的深度优先遍历
{
    int i=k,j=0;                       //i下标从0开始
    cout<<vertex[i]<<"  ";             //访问结点
    visited[i]=1;                      //设置访问标记
    while(j<vertCount)                 //查找与k相邻的其他结点
        if(i!=j && mat[i][j]>0 && mat[i][j]<MaxWeight && visited[j]==0)
            depthfs(j);                //递归
        else
            j++;
}

void Graph1::depthFirstSearch()        //图的深度优先遍历
{
    cout<<"深度优先遍历Depth first search:"<<endl;
    for(int k=0;k<vertCount;k++)       //k为结点下标
    {
        unvisited();                   //设置未访问标记 
        depthfs(k);
        cout<<endl;
    }
}
 
void Graph1::breadthfs(int k)          //从结点k开始的广度优先遍历
{                                      //k为起始结点下标
    Queue1 q1(vertCount);              //设置空队列
    int i=k;
    cout<<vertex[i]<<"  ";             //访问起始结点
    visited[i]=1;                      //设置访问标记
    q1.enQueue(i);                     //访问过的结点k入队
    while(!q1.isEmpty())               //队列不空时
    {
        i=q1.deQueue();                //出队,i是结点k的数组下标
        int j=0;
        while(j<vertCount)             //查找与k相邻的其他结点
           if(i!=j && mat[i][j]>0 && mat[i][j]<MaxWeight && visited[j]==0)
           {
                cout<<vertex[j]<<"  "; //访问结点
                visited[j]=1;
                q1.enQueue(j);         //入队
           }
           else
                j++;
    }
}

void Graph1::breadthFirstSearch()      //图的广度优先遍历
{                                      //k为起始结点下标
    cout<<"广度优先遍历Breadth first search:"<<endl;
    for(int k=0;k<vertCount;k++)
    {
        unvisited();
        breadthfs(k);
        cout<<endl;
    }
}