听风QAQ(〜 ̄▽ ̄)〜
2022-05-30 09:11
采纳率: 100%
浏览 104

图,最短路径,好难,求解

路径存在
对一个包含 N 个顶点的有向图 G(V, E) 用邻接表进行存储,其中顶点以数组保存。对于该有向图类 adjListGraph,
要求增加一个成员函数 existPath,对于图中的任两个顶点 i, j,检查它们之间是否有路径存在。如有,输出其中最小的一条路径。
如无,输出字符串 "false"。(40')

对于最小路径,首先判断长度,输出较小长度的路径,若存在多条长度相同的路径,则输出路径顺序中结点编号较小的路径。例如路径 6 1 5 4 和 6 2 3 4,应选择前者输出。

注:图中可能存在环。

要求:在文件头部说明新增成员函数的设计思路,并分析时间复杂度分析。(10')

输入描述
第1行输入顶点个数 N,N 为正整数。

第2行输入有向边信息,边的起点和终点分别为顶点的编号,编号间以逗号相隔,边之间以空格相隔。

第3行输入路径起点和终点的编号,以空格相隔。

输出描述
输出路径检查的结果。

输入举例
6
1,3 2,3 1,4 3,5 2,5 4,2 5,6 3,6
4 6
输出举例
4 2 3 6

#include<bits/stdc++.h>
using namespace std;
template<class elemType>
class linkQueue
{
    private:
        struct node
        {
            elemType data;
            node *next;
            node( elemType &x,node *N=NULL)
            {
                data=x;
                next=N;
            }
            node():next(NULL){}
            ~node(){}
        };
    node *front,*rear;
    public:
        linkQueue();
        ~linkQueue();
        bool isEmpty() ;
        elemType deQueue();
        void enQueue( elemType &x);
};

template<class elemType>
bool linkQueue<elemType>::isEmpty() 
{
    return front==NULL;
}
template<class elemType>
linkQueue<elemType>::linkQueue()
{
    front=rear=NULL;
}
template<class elemType>
linkQueue<elemType>::~linkQueue()
{
    node *tmp;
    while(front!=NULL)
    {
        tmp=front;
        front=front->next;
        delete tmp;
    }
}
template<class elemType>
void linkQueue<elemType>::enQueue(elemType &x)
{
    if(rear==NULL)
        front=rear=new node(x);
    else
        rear=rear->next=new node(x);
}
template<class elemType>
elemType linkQueue<elemType>::deQueue()
{
    node *tmp=front;
    elemType value=front->data;
    front=front->next;
    if(front==NULL)
        rear=NULL;
    delete tmp;
    return value;
}
template<class TypeOfVer,class TypeOfEdge>
class adjListGraph
{
    public:
        adjListGraph(int vSize);
        void insert(TypeOfVer x,TypeOfVer y,TypeOfEdge w);
        //void remove(TypeOfVer x,TypeOfVer y);
        //bool exist(TypeOfVer x,TypeOfVer y)const;
        bool checkRoute(int start,int end);
        //void existPath(int start,int end);
        //~adjListGraph();
        void unweightedShortDistance(TypeOfVer start,TypeOfVer end,TypeOfEdge noEdge);
    private:
        int Vers,Edges;
        struct edgeNode 
        {
            int end;
            TypeOfEdge weight;
            edgeNode *next;
            edgeNode(int e,TypeOfEdge w,edgeNode *n=NULL)
            {
                end=e;
                weight=w;
                next=n;
            }
        };
        struct verNode
        {
            TypeOfVer ver;
            edgeNode *head;
            verNode(edgeNode *h=NULL)
            {
                head=h;
            }
        };
        verNode *verList;
        int find(TypeOfVer v)const
        {
            for(int i=0;i<Vers;i++)
            {
                if(verList[i].ver==v)
                {
                    return i;
                }
            }
        }
        bool checkRoute(int start,int end,bool visited[]);
        //void existPath(int start,int end,bool visited[]);
        void printPath(int start,int end,int prev[]);
};
template<class TypeOfVer,class TypeOfEdge>
adjListGraph<TypeOfVer,TypeOfEdge>::adjListGraph(int vSize)
{
    Vers=vSize;
    Edges=0;
    verList=new verNode[vSize];
    for(int i=0;i<Vers;i++)
    {
        verList[i].ver=i+1;
    }
}
/*template<class TypeOfVer,class TypeOfEdge>
adjListGraph<TypeOfVer,TypeOfEdge>::~adjListGraph()
{
    int i;
    edgeNode *p;
    for(i=0;i<Vers;i++)
    {
        while((p=verList[i].head)!=NULL)
        {
            verList[i].head=p->next;
            delete p;
        }
    }
    delete []verList;
}*/
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::insert(TypeOfVer x,TypeOfVer y,TypeOfEdge w)
{
    int u=find(x);
    int v=find(y);
    verList[u].head=new edgeNode(v,w,verList[u].head);
    ++Edges;
}
template<class TypeOfVer,class TypeOfEdge>
bool adjListGraph<TypeOfVer,TypeOfEdge>::checkRoute(int start,int end)
{
    bool *visited=new bool[Vers];
    int startNo,endNo;
    for(int i=0;i<Vers;i++)
    {
        visited[i]=false;
    }
    for(startNo=0;startNo<Vers;startNo++)
    {
        if(verList[startNo].ver==start)break;
    }
    //if(startNo==Vers)return false;
    for(endNo=0;endNo<Vers;endNo++)
    {
        if(verList[endNo].ver==end)break;
    }
    //if(endNo==Vers)return false;
    return checkRoute(startNo,endNo,visited);
}
template<class TypeOfVer,class TypeOfEdge>
bool adjListGraph<TypeOfVer,TypeOfEdge>::checkRoute(int start,int end,bool visited[])
{
    edgeNode *p=verList[start].head;
    bool flag=0;
    visited[start]=true;
    while(p!=NULL)
    {
        if(p->end==end)return true;
        if(!visited[p->end])
        {
            flag=checkRoute(p->end,end,visited);
            if(flag)return true;
        }
        p=p->next;
    }
    //cout<<"okok";
    return false;
}
/*template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::existPath(int start,int end)
{
    bool *visited=new bool[Vers];
    for(int i=0;i<Vers;i++)
    {
        visited[i]=false;
    }
    existPath(start,end,visited);
}
static int L[100],o=0;
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::existPath(int start,int end,bool visited[])
{
    edgeNode *p=verList[start].head;
    L[o]=start;
    o++;
    //cout<<start;
    visited[start]=true;
    while(p!=NULL)
    {
        if(p->end==end)
        {
            L[o]=end;
            o++;
            //cout<<"okok";
            break;
        }
        else if(!visited[p->end]&&checkRoute(p->end,end))
        {
            existPath(p->end,end,visited);
        }
        p=p->next;
    }
}*/
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::unweightedShortDistance(TypeOfVer start,TypeOfVer end,TypeOfEdge noEdge)
{
    linkQueue<int> q;
    TypeOfEdge *distance=new TypeOfEdge[Vers];
    int *prev=new int[Vers];
    int u,sNo;
    edgeNode *p;
    for(int i=0;i<Vers;i++)
    {
        distance[i]=noEdge;
    }
    sNo=find(start);
    distance[sNo]=0;
    prev[sNo]=sNo;
    q.enQueue(sNo);
    while(!q.isEmpty())
    {
        u=q.deQueue();
        for(p=verList[u].head;p!=NULL;p=p->next)
        {
            if(distance[p->end]==noEdge)
            {
                distance[p->end]=distance[u]+1;
                prev[p->end]=u;
                q.enQueue(p->end);
            }
        }
    }
    //cout<<prev[6]<<endl; 
    printPath(sNo,end-1,prev);
}
template<class TypeOfVer,class TypeOfEdge>
void adjListGraph<TypeOfVer,TypeOfEdge>::printPath(int start,int end,int prev[])
{
    if(start==end)
    {
        cout<<verList[start].ver;
        return;
    }
    printPath(start,prev[end],prev);
    cout<<' '<<verList[end].ver;
}
//int **Arr;
int main()
{
    int n;
    cin>>n;
    string str;
    getline(cin,str);
    getline(cin,str);
    //cout<<str;
    int x,y;
    cin>>x>>y;
    //cout<<x<<y;
    adjListGraph<int,int> A(n);
    int k=0;
    for(int i=0;i<str.size();i++)
    {
        if(str[i]==',')
        {
            k++;
        }
    }
    //cout<<k;
    for(int i=0;i<k;i++)
    {
        int t1,t2,u,v;
        u=4*i;v=4*i+2;
        t1=str[u]-'0';
        t2=str[v]-'0';
        //cout<<t1<<" "<<t2<<endl;
        A.insert(t1,t2,0);
    }    
    bool flg=A.checkRoute(x,y);
    //cout<<flg;
    if(flg)
    {
        A.unweightedShortDistance(x,y,-1);
    }
    else
    {
        cout<<"false";
    }
}

这个是自己写的但是没有办法满足“若存在多条长度相同的路径,则输出路径顺序中结点编号较小的路径”

2条回答 默认 最新

相关推荐 更多相似问题