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

图建立问题

咔叽 发布于 2011-06-12 23:48, 551 次点击
建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。
2 回复
#2
咔叽2011-06-17 23:27
#3
星翼凌空2011-06-18 11:58
程序代码:
void CreateDG_AM(MGraph * G)
{
    int i, j, k;                       /*循环变量*/
    VertexType v1,v2;                      /*临时变量*/
    cout<<"请输入图的顶点数,边数(空格隔开,下面也是):";
    cin>>G->vexNum>>G->arcNum;
    cout<<"输入这"<<(G->vexNum)<<"顶点的值:";
    /*创建一个一维数组存放各顶点*/
    for(i = 0; i < G->vexNum; i++)     
    {
        cin>>G->vexs[i];
    }
    /*初始化邻接矩阵*/
    for(i = 0; i < G->vexNum; i++)   
        for(j = 0; j < G->vexNum; j++)
        {
            G->arcs[i][j].adj = INFINITY;
            G->arcs[i][j].info = NULL;
        }
    /*创建邻接矩阵*/
    cout<<"请输入弧尾和弧头:"<<endl;
    for(k = 0; k < G->arcNum; k++)
    {
        cin>>v1;
        cin>>v2;
        /*确定顶点在一维数组中的索引*/
        i = LocateVertex1(*G,v1);   
        j = LocateVertex1(*G,v2);
        G->arcs[i][j].adj = 1;
        /*与弧相关的信息*/
        if(G->arcs[i][j].info != NULL)
        {
            //......
        }
    }
    /*图的类型*/
    G->kind = UDG;
}

void DisplayDG_AM(MGraph G)
{
    int i,j;
    cout<<"有向图G具有:"<<G.vexNum<<"个顶点"<<G.arcNum<<"条弧"<<endl;
    cout<<"顶点依次是:";
    for(i = 0; i < G.vexNum; i++)
    {
        cout<<G.vexs[i]<<" ";
    }
    cout<<endl<<"序号i=";
    for(i = 0; i < G.vexNum; i++)
    {
        cout<<setw(8)<<i;
    }
    cout<<endl;
    for(i = 0; i < G.vexNum; i++)
    {
        cout<<setw(8)<<i;
        for(j = 0; j < G.vexNum; j++)
        {
            cout<<setw(8)<<G.arcs[i][j].adj;
        }
        cout<<endl;
    }
}
1