注册 登录
编程论坛 数据结构与算法

关于邻接表求某点的入度,算法怎么弄,我只会出度算法

玉垒浮云 发布于 2013-06-10 12:08, 1142 次点击
#include<iostream>
#include<windows.h>
using namespace std;
const int maxsize=10;
template<class T>
struct arcNode
{
    int adjvex;
    arcNode<T>* next;
};
template<class T>
struct vertexNode
{
    T vertex;
    arcNode<T>* firstedge;
};
template<class T>
class alraph
{
    public:
        alraph(T a[],int n,int e);
        ~alraph(){}
        void DFSTraverse(int v);
        void BFSTraverse(int v);
        void chudu(int v);
    private:
        vertexNode<T> adjlist[maxsize];
        int vertexnum,arcnum;
        T visited[maxsize];
        T Q[maxsize];
};
template<class T>
alraph<T>::alraph(T a[],int n,int e)//构造函数
{
    int i,j;
    vertexnum=n;arcnum=e;
    for(i=0;i<vertexnum;++i)
    {
        adjlist[i].vertex=a[i];
        adjlist[i].firstedge=NULL;
    }
    for(int k=0;k<arcnum;++k)
    {
        cout<<"请输入i,j"<<endl;
        cin>>i>>j;
        arcNode<T>* s;
        s=new arcNode<T>;s->adjvex=j;
        s->next=adjlist[i].firstedge;
        adjlist[i].firstedge=s;
    }
    for( i=0;i<vertexnum;++i)
        visited[i]=0;
}
template<class T>
void alraph<T>::DFSTraverse(int v)//深度遍历
{
    int j;
    cout<<adjlist[v].vertex;visited[v]=1;
    arcNode<T>* p;
    p=adjlist[v].firstedge;
    while(p!=NULL)
    {
        j=p->adjvex;
        if(visited[j]==0)DFSTraverse(j);
        p=p->next;
    }
}
template<class T>
void alraph<T>::BFSTraverse(int v)//广度遍历
{
    int i;
    for(i=0;i<vertexnum;++i)
        visited[i]=0;
    int front=-1;int rear=-1;int j;
    cout<<adjlist[v].vertex;
    visited[v]=1;
    Q[++rear]=v;
    arcNode<T>* p;
    while(front!=rear)
    {
        v=Q[++front];
        p=adjlist[v].firstedge;
        while(p!=NULL)
        {
            j=p->adjvex;
            if(visited[j]==0)
            {
                cout<<adjlist[j].vertex;visited[j]=1;Q[++rear]=j;
            }
            p=p->next;
        }
    }
}
template<class T>
void alraph<T>::chudu(int v)//出度函数
{
    int i=0;
    arcNode<T>* p;
    p=adjlist[v].firstedge;
    while(p!=NULL)
    {
        ++i;
        p=p->next;
        
    }
    cout<<"出度为"<<i<<endl;
}

void main()
{
    system("color 70");
    char a[]="abcd";
    alraph<char>b(a,4,4);   

    cout<<"深度遍历:";
    b.DFSTraverse(0);
    cout<<endl;
    cout<<"广度遍历:";
    b.BFSTraverse(0);
    cout<<endl;
    b.chudu(0);
    cout<<endl;
 
}邻接表的深度遍历广度遍历,求某点的求出度算法已做好,现在不会做求入度算法,求大神指点
输入数据为:
0 1
0 2
2 3
3 0
起大神帮帮忙!


1 回复
#2
玉垒浮云2013-06-12 10:13
大神在哪
1