写出1个广度优先拓扑序列

假设有以下图：

    A -- B -- C
    |    |    |
    D -- E -- F

其中，字母表示节点，连线表示边。则一个广度优先拓扑序列可以是：A, B, D, E, C, F。

相关问题

4、对下列的有向无权图，要求： （1）写出它三种可能的拓扑排序序列 （2）写出该图的广度优先遍历顺序，以 A 为起点 （3）画出该图的邻接表表示

为了回答你的问题，我需要先展示一下这个有向无权图的结构：

A -> B -> C
^    |    |
|    v    v
D -> E -> F

现在回答你的问题：

（1）三种可能的拓扑排序序列为：

- A, D, B, E, C, F
- A, D, B, C, E, F
- A, D, E, B, C, F

（2）该图的广度优先遍历顺序，以 A 为起点为：A, B, D, C, E, F

（3）该图的邻接表表示为：

A: B
B: C, E
C: F
D: B, E
E: C, F
F:

写出(1)键盘输入数据，建立一个有向图的邻接表 (2) 输出该邻接表。 (3)在有向图的邻接表的基础上计算各顶点的度，并输出 (4)以有向图的邻接表为基础实现输出它的拓扑排序序列。 (5)采用邻接表存储实现无向图的深度优先遍历。 (6)采用邻接表存储实现无向图的广度优先遍历。 (7)采用邻接矩阵存储实现无向图的最小生成树的 PRIM算法。 (8)采用邻接矩阵存储一个有向图，输出单源点到其它顶点的最短路径。 *(9)判断无向图任意两个顶点间是否有路径，若有输出路径上的顶点序列。 (10)在主函数中设计一个简单的菜单，分别调试上述算法

以下是C++语言的实现，供您参考：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x7fffffff/2
using namespace std;
const int MAXN = 1005;
int n,m,u,v,w,he[MAXN],ne[MAXN],idx=0,deg[MAXN],stk[MAXN],top;
struct Edge{
    int to,next;
}e[MAXN];
void add(int u,int v){
    e[++idx].to=v;
    e[idx].next=he[u];
    he[u]=idx;
}
void init(){//建立有向图的邻接表
    memset(he,-1,sizeof(he));
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        add(u,v);
        deg[v]++;//计算各顶点的入度
    }
}
void topo(){//拓扑排序，输出排序序列
    queue<int>q;
    for(int i=1;i<=n;i++)
        if(deg[i]==0)
            q.push(i);
    while(!q.empty()){
        int u=q.front();q.pop();
        stk[++top]=u;
        for(int i=he[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(--deg[v]==0)
                q.push(v);
        }
    }
    if(top==n){
        for(int i=1;i<=n;i++)
            cout<<stk[i]<<" ";
        cout<<endl;
    }
}
int vis[MAXN];
void dfs(int u){//无向图的深度优先遍历
    vis[u]=1;
    cout<<u<<" ";
    for(int i=he[u];i!=-1;i=e[i].next){
        int v=e[i].to;
        if(!vis[v])
            dfs(v);
    }
}
void bfs(int s){//无向图的广度优先遍历
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);
    vis[s]=1;
    while(!q.empty()){
        int u=q.front();q.pop();
        cout<<u<<" ";
        for(int i=he[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(!vis[v]){
                q.push(v);
                vis[v]=1;
            }
        }
    }
}
int d[MAXN],g[MAXN][MAXN];
struct node{
    int u,d;
    bool operator<(const node&rhs)const{
        return d>rhs.d;
    }
};
void prim(){//无向图的最小生成树的 PRIM算法
    priority_queue<node>q;
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    q.push((node){1,0});
    int ans=0;
    while(!q.empty()){
        node t=q.top();q.pop();
        int u=t.u;
        if(vis[u]) continue;
        vis[u]=1;
        ans+=t.d;
        for(int i=he[u];i!=-1;i=e[i].next){
            int v=e[i].to;
            if(d[v]>g[u][v]){
                d[v]=g[u][v];
                q.push((node){v,d[v]});
            }
        }
    }
    cout<<ans<<endl;
}
void dijkstra(int s){//单源点到其它顶点的最短路径
    priority_queue<node>q;
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    q.push((node){s,0});
    while(!q.empty()){
        node t=q.top();q.pop();
        int u=t.u;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=1;i<=n;i++){
            if(d[i]>d[u]+g[u][i]){
                d[i]=d[u]+g[u][i];
                if(!vis[i])
                    q.push((node){i,d[i]});
            }
        }
    }
    for(int i=1;i<=n;i++)
        cout<<d[i]<<" ";
    cout<<endl;
}
void dfs_path(int u,int v){//查找路径上的顶点序列
    vis[u]=1;
    if(u==v) return;
    for(int i=he[u];i!=-1;i=e[i].next){
        int x=e[i].to;
        if(!vis[x]){
            stk[++top]=x;
            dfs_path(x,v);
            if(stk[top]==v) return;
            top--;
        }
    }
}
int main(){
    init();
    topo();
    dfs(1);
    cout<<endl;
    bfs(1);
    memset(vis,0,sizeof(vis));
    prim();
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        g[u][v]=w;
    }
    dijkstra(1);
    memset(vis,0,sizeof(vis));
    top=1;
    dfs_path(1,4);
    for(int i=1;i<=top;i++)
        cout<<stk[i]<<" ";
    cout<<endl;
    return 0;
}