그림 의 관련 조작

1. 키보드 가 데 이 터 를 입력 하고 그림 에 대한 인접 표를 만 듭 니 다.
2. 이 인접 표를 출력 합 니 다.
3. 그림 의 인접 표를 바탕 으로 각 정점 의 도 를 계산 하고 출력 한다.
4. 그림 에 대한 인접 표를 바탕 으로 토폴로지 정렬 순 서 를 출력 합 니 다.
5. 인접 표 저장 소 를 이용 하여 무 방향 그림 의 깊이 를 우선 시 하고 재 귀적 으로 옮 겨 다 니 지 않 습 니 다.
6. 인접 표 저장 소 를 이용 하여 무방 향도 의 넓이 를 우선적으로 옮 겨 다 닌 다.
7. 주 함수 에서 간단 한 메뉴 를 설계 하여 상기 알고리즘 을 각각 디 버 깅 합 니 다.
#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <stack>
using namespace std;
const int N=1000;
struct tu1
{
    vector<int>tu[N];
    int n,m;
    int rd[N],cd[N]; ///     
    void input()
    {
        memset(rd,0,sizeof(rd));
        memset(cd,0,sizeof(cd));
        cout<<"   n  m      "<<endl;
        cout<<"   n"<<endl;
        cin>>n;
        cout<<"   m"<<endl;
        cin>>m;
        int x=m;
        while(x--)
        {
            int a,b;
            cin>>a>>b;
            tu[a].push_back(b);
            rd[b]++;
            cd[a]++;
        }
    }
    void bianli()///   
    {
        cout<<"       :"<<endl;
        for(int i=1; i<=n; i++)
        {
            int l=tu[i].size();
            for(int j=0; j<l; j++)
                cout<<i<<"->"<<tu[i][j]<<endl;
        }
    }
    void getdu()///       
    {
        for(int i=1; i<=n; i++)
            cout<<i<<"      "<<rd[i]<<"   "<<cd[i]<<endl;
    }

    void topu()///    
    {
        queue<int>q;
        for(int i=1; i<=n; i++)
            if(rd[i]==0)
                q.push(i);
        cout<<"       :"<<endl;
        while(!q.empty())
        {
            int t=q.front();
            cout<<t<<' ';
            q.pop();
            int l=tu[t].size();
            for(int i=0; i<l; i++)
            {
                int to=tu[t][i];
                rd[to]--;
                if(rd[to]==0)
                    q.push(to);
            }
        }
        cout<<endl;
    }
};
struct tu2
{
    vector<int>tu[N];
    int n,m;
    bool vis[N];
    void input()
    {
        cout<<"   n  m      "<<endl;
        cout<<"   n"<<endl;
        cin>>n;
        cout<<"   m"<<endl;
        cin>>m;
        int x=m;
        while(x--)
        {
            int a,b;
            cin>>a>>b;
            tu[a].push_back(b);
            tu[b].push_back(a);
        }
    }
    void dfs()///     
    {
        cout<<"        :"<<endl;
        memset(vis,0,sizeof(vis));
        stack<int>s;
        s.push(1);
        while(!s.empty())
        {
            int t=s.top();
            cout<<t<<' ';
            s.pop();
            vis[t]=1;
            int l=tu[t].size();
            for(int i=0; i<l; i++)
            {
                int to=tu[t][i];
                if(!vis[to])
                    vis[to]=1,s.push(to);
            }
        }
        cout<<endl;
    }
    void bfs()///  
    {
        cout<<"     :"<<endl;
        memset(vis,0,sizeof(vis));
        queue<int>q;
        q.push(1);
        while(!q.empty())
        {
            int t=q.front();
            cout<<t<<' ';
            q.pop();
            vis[t]=1;
            int l=tu[t].size();
            for(int i=0; i<l; i++)
            {
                int to=tu[t][i];
                if(!vis[to])
                    vis[to]=1,q.push(to);
            }
        }
        cout<<endl;
    }
};
int main()
{
    tu1 A;
    A.input();
    A.bianli();
    A.getdu();
    A.topu();
    tu2 B;
    B.input();
    B.dfs();
    B.bfs();
    return 0;
}

좋은 웹페이지 즐겨찾기