实现图的基本操作

问题描述:建立图(邻接矩阵、邻近表任选其一)的存储结构、实现图的深度优先遍历和广度优先遍历。

深度优先遍历:

  1. 在访问图中某一起始顶点 v 后,由 v 出发,访问它的一邻接顶点 w1;
  2. 从 w1 出发,访问与 w1邻接但还未被访问过的顶点 w2;然后再从 w2 出发,如此进行下去,直至到达所有的邻接顶点都被访问过为止。
  3. 接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。

广度优先遍历:

  1. 在访问了起始点v之后,依次访问 v的邻接点;
  2. 然后再依次访问这些顶点中未被访问过的邻接点;
  3. 直到所有顶点都被访问过为止。

代码如下:

#include <iostream>
using namespace std;
#include <stdlib.h>
class Queue{//队列的类定义
    int rear,front;
    char *elements;
    int maxSize;
public:
    Queue(int sz=100);//构造函数
    ~Queue(){delete[] elements;}//析构函数
    void EnQueue(int loc);//顶点入队
    void DeQueue(int &loc);//顶点出队
    bool IsEmpty();
};
Queue::Queue(int sz)
{
    front=0;
    rear=0;
    maxSize=sz;
    elements=new char(maxSize);
}
void Queue::EnQueue(int loc)
{
    elements[rear]=loc;
    rear=(rear+1)%maxSize;
}
void Queue::DeQueue(int &loc)
{
    front=(front+1)%maxSize;
}
bool Queue::IsEmpty()
{
    return rear==front;
}
class Graphmtx{//图的类定义
private:
    char *VerticesList;//顶点表
    int **Edge;//邻接矩阵
    int numVertices;//当前顶点个数
    int maxVertices;
    int numEdges;
    int maxWeight;
    int getVertexPos(char vertex){//给出顶点vertex在VerticesList中的下标
        for(int i=0;i<numVertices;i++)
        {
            if(VerticesList[i]==vertex)
                return i;
        }
    }
public:
       Graphmtx(int sz=100);//构造函数
       ~Graphmtx(){delete[]VerticesList;delete []Edge;}
        int getWeight(int v1,int v2){//取边(v1,v2)上的权值
            return (v1>-1&&v2>-1)?Edge[v1][v2]:0;
        }
        char getValue(int v)
        {
            return VerticesList[v];
        }
        friend istream&operator>>(istream &in,Graphmtx &G);//输入
        friend void DFS(Graphmtx &G);
        friend void DFS(Graphmtx &G, int v); //递归实现算法
        friend void BFS (Graphmtx& G);
        void outEdges();
        int getFirstNeighbor(int v);
        int getNextNeighbor(int v ,int w);
};
Graphmtx::Graphmtx(int sz)//构造函数
{
    maxVertices=sz;
    numVertices=0;
    numEdges=0;
    int i,j;
    VerticesList=new char[maxVertices];//创建顶点表
    Edge=new int *[maxVertices];
    for(i=0;i<maxVertices;i++)
        Edge[i]=new int[maxVertices];//邻接矩阵
    for(i=0;i<maxVertices;i++)//矩阵初始化
        for(j=0;j<maxVertices;j++)
        Edge[i][j]=0;
}

istream& operator>>(istream &in,Graphmtx &G)//创建图
{
    int n;
    in>>n;
    G.numVertices=n;
    int i,j,k;
    for(i=0;i<n;i++)
    {
        char c;
        in>>c;
        G.VerticesList[i]=c;
    }
    int q;
    in>>n;
    for(k=0;k<n;k++)
    {
        in>>i>>j>>q;
        G.Edge[i][j]=q;
    }
}
void Graphmtx::outEdges()
{
    cout<<"edges are:"<<endl;
    for(int i=0;i<numVertices;i++)
        for(int j=0;j<numVertices;j++)
    {
        if(Edge[i][j]!=0)
        {
            cout<<VerticesList[i]<<'-'<         }
    }
}
int visited[100];

void DFS(Graphmtx &G,int i)
{
       int j;
       cout<<G.getValue(i)<<" ";
       visited[i]=1;
       for(j=0;j<G.numVertices;j++)
       {
              if((G.Edge[i][j])==1&&(visited[j])==0)
                     DFS(G,j);
       }
}

void DFS(Graphmtx &G)
{
       int i;
       cout<<"DFS:";
       for(i=0;i<G.numVertices;i++)
       {
              visited[i]=0;
       }
       for(i=0;i<G.numVertices;i++)
       {
              if(!visited[i])
                DFS(G,i);
       }
       cout<<endl;
}

void BFS (Graphmtx& G) {
    int i, w, n = G.numVertices;     //图中顶点个数
    bool *visited = new bool[n];
    for (i = 0; i < n; i++)
        visited[i] = false;
    int loc = 0;        //取顶点号
    Queue  Q(n);
    cout<<"BFS:";
    for(int i=0;i<n;i++)
    {
        if(!visited[i])
        {
            visited[i]=true;
            cout<<G.getValue(i)<<' ';
            Q.EnQueue(i);
            while(!Q.IsEmpty())
            {
                Q.DeQueue(i);
                for(int j=0;j<n;j++)
                {
                    if(G.Edge[i][j]!=0&&!visited[j])
                    {
                        visited[j]=true;
                        cout<<G.getValue(j)<<' ';
                        Q.DeQueue(j);
                    }
                }
            }
        }
    }
    delete [] visited;
    cout<<endl;
}
int main()
{
    Graphmtx G;
    cin>>G;
    DFS(G);
    BFS(G);
    G.outEdges();
    return 0;
}


You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注