当前位置： 移动技术网 > IT编程>开发语言>C/C++ > 关于C++图的遍历（代码）

关于C++图的遍历（代码）

2018年09月29日  | 移动技术网IT编程  | 我要评论

镗刀,西印度群岛位于哪里,柳青 创业史

关于c++图的遍历（代码）

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<cstring>
 
const int maxsize=100;
 
const int vertexnum=20;
typedef struct{
    int *qbase;
    int front,rear;
}sqqueue;
 
void initqueue(sqqueue &q){
    q.qbase = (int *)malloc(sizeof(int) *vertexnum);
 
    if(!q.qbase)
        return ;
 
    q.rear = q.front = -1;
}
 
void enqueue(sqqueue &q, int i){
    q.qbase[q.rear ++] = i;
}
 
void dequeue(sqqueue &q, int &i){
    i = q.qbase[q.front ++];
}
 
int queueempty(sqqueue q){
    if(q.front == q.rear)
        return 1;
 
    return 0;
}
 
template<class t>
class  mgraph
{
public:
    mgraph(t a[],int n,int e);
    ~mgraph(){}
    void dfstraverse();
    void bfstraverse(int v);
    void deeptra(int v[],int n);
private:
    t   vertex[maxsize];             //节点数组
    int  arc[maxsize][maxsize];      //矩阵
    int vertexnum,arcnum;            //节点数与边数
    int visited[maxsize];            //访问记录
};
 
template<class t>
mgraph<t>::mgraph(t a[],int n,int e)
{
    int i,j;
    vertexnum=n;
    arcnum=e;
    for(i=0;i<vertexnum;i++)
    {
        vertex[i]=a[i];
    }
 
    for(i=0;i<vertexnum;i++)
        for(j=0;j<vertexnum;j++)
    {
        arc[i][j]=0;
    }
 
    for(int k=0;k<arcnum;k++)
    {
        std::cout<<"输入第"<<k+1<<"条边："<<std::endl;
        std::cin>>i>>j;
        arc[i][j]=1;
        arc[j][i]=1;
    }
}
 
template<class t>
void  mgraph<t>::dfstraverse()
{
    int i;
    for(i=0;i<vertexnum;i++)
    {
        visited[i]=0;
    }
    std::cout<<"深度优先遍历:"<<std::endl;
    for(i=0;i<vertexnum;i++)
    {
        if(visited[i]==0)
            deeptra(visited,0);
    }
}
 
template<class t>
void mgraph<t>::deeptra(int v[],int n)
{
    int i;
    visited[n]=1;
    std::cout<<vertex[n];
    for(i=0;i<vertexnum;i++)
    {
        if(arc[n][i]!=0&&visited[i]==0)
        {
            deeptra(visited,i);
        }
    }
}
 
template<class t>
void mgraph<t>::bfstraverse(int v)
{
    sqqueue q;
    q.front=q.rear=-1;
    int i;
    for(i=0;i<vertexnum;i++)
    {
        visited[i]=0;
    }
    std::cout<<std::endl;
    std::cout<<"广度优先遍历："<<std::endl;
    std::cout<<vertex[v];
    visited[v]=1;
    initqueue(q);
    enqueue(q,v);
    while(!queueempty(q))
    {
        dequeue(q,v);
        for(int i=0;i<vertexnum;i++)
            if(arc[v][i]==1&&visited[i]==0)
        {
            std::cout<<vertex[i];
            visited[i]=1;
            enqueue(q,i);
        }
    }
}
int main()
{
 
    int e,n;
    std::cout<<"点的个数："<<"  ";
    std::cin>>e;
 
    std::cout<<"边的个数："<<"  ";
    std::cin>>n;
 
    char  s[e];
    for(int i=0;i<e;i++)
    {
        std::cout<<"输入第"<<i+1<<"个点：";
        std::cin>>s[i];
    }
    mgraph<char> m(s,e,n);
    m.dfstraverse();
    m.bfstraverse(0);
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网