【C++】基于邻接矩阵的图的深度优先遍历

 写在前面:本博客为本人原创,严禁任何形式的转载!本博客只允许放在博客园(.cnblogs.com),如果您在其他网站看到这篇博文,请通过下面这个唯一的合法链接转到原文!

本博客全网唯一合法URL:https://www.cnblogs.com/acm-icpcer/p/10458956.html

 

算法思想使用的是殷人昆《数据结构(基于面向对象和C++)》第二版P364页的程序8.9

#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
const long M=1024;

class G
{
private:
    int map[M][M];
    int visited[M];
    int m;
public:
    G()
    {
        cin>>m;
        clean();
        build();
    }
    
    void clean()
    {
        memset(map,0,sizeof(map));
        memset(visited,0,sizeof(visited));
        cout<<"clean over"<<endl;
    }
    
    void build()
    {
        for(int i=0;i<m;i++)
            for(int j=0;j<m;j++)
                scanf("%d",&map[i][j]);
    }
    
    void display()
    {
        cout<<"dispalying:"<<endl;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<m;j++)
                cout<<map[i][j];
            cout<<endl;
        }
    }
    
    int getfirstedge(int v)
    {
        if(v>m||v<0)    return -1;
        int i=0;
        while(map[v][i]<=0&&i<m)    i++;
        if(i>m||i<0)    return -1;
        return i;
    }
    
    int getnextedge(int v,int w)
    {
        int i=w+1;
        if(v>m||v<0||i>m||i<0)    return -1;
        while(map[v][i]<=0&&i<m)    i++;
        if(i>m||i<0)    return -1;
        return i;
    }
    /*
    void dfs(int i,int j)
    {
        if(i>m||j>m||i<0||j<0||visited[i][j])
            return;
            
        ++visited[i][j];
            
        if(map[i][j]>0)
            cout<<"node->"<<i<<":"<<map[i][j];
        
        dfs(i-1,j);
        dfs(i,j-1);
        dfs(i+1,j);
        dfs(i,j+1);
    }
    */
    
    void dfs(int v)//v represents a node
    {
        cout<<v;
        visited[v]=1;
        int w=this->getfirstedge(v);
        while(w>=0&&w<m)
        {
            if(visited[w]!=1)
                dfs(w);
            w=this->getnextedge(v,w);
        }
    }
    
    
};

int main()
{
    G *obj1=new G();
    obj1->display();
    /*
    cout<<obj1->getfirstedge(1)<<endl;
    cout<<obj1->getnextedge(1,obj1->getfirstedge(1))<<endl;
    */
    cout<<"dfs:"<<endl;
    obj1->dfs(0);
    
    return 0;
}

 

代码运行说明:

【C++】基于邻接矩阵的图的深度优先遍历

 

 

tz@HZAU

2019/3/1

上一篇:基础知识总结(js篇)


下一篇:python文件查找