DHU数据结构 图-邻接矩阵OJ

 针对邻接矩阵实现的图的部分操作

#include

#define MAXVEX 10
#define INFINITY 65656
using namespace std;
typedef int EdgeType;
typedef int VertexType;
int visited[MAXVEX];

typedef struct
{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    EdgeType weight[MAXVEX];
    int numNodes;
    int numEdges;
    int flag;
} MGraph;

//无权图

//有向有权图
void CreateDGraph(MGraph *Gp)
{
    int i,j,k;
    cin>>Gp->numNodes;
    for(i=0; inumNodes; i++) //输入顶点
        cin>> Gp->vexs[i];
    cin>>Gp->flag;
    for(i=0; inumNodes; i++) //初始化邻接矩阵
    {
        for(j=0; jnumNodes; j++)
        {
            if(i==j)
                Gp->arc[i][j]=Gp->flag;//顶点没有到自己的边
            else
                Gp->arc[i][j]=Gp->flag;//初始化边为无穷
        }
    }
    cin>>Gp->numEdges;
    for(k=0; knumEdges; k++)
    {
        cin>>i>>j;
        Gp->arc[i][j]=1;
    }
    for(k=0;knumEdges; k++)
    {
        cin>>Gp->weight[k];
    }
    k=0;
    for(i=0; inumNodes; i++) //邻接矩阵赋予权值
    {
        for(j=0; jnumNodes; j++)
        {
            if(Gp->arc[i][j]==1)
            {
                Gp->arc[i][j]=Gp->weight[k];
                ++k;
            }
        }
    }
}
//无向有权图
void CreateUDGraph(MGraph *Gp)
{
    int i,j,k;
    cin>>Gp->numNodes;
    for(i=0; inumNodes; i++) //输入顶点
        cin>> Gp->vexs[i];
    cin>>Gp->flag;
    for(i=0; inumNodes; i++) //初始化邻接矩阵
    {
        for(j=0; jnumNodes; j++)
        {
            if(i==j)
                Gp->arc[i][j]=Gp->flag;//顶点没有到自己的边
            else
                Gp->arc[i][j]=Gp->flag;//初始化边为无穷
        }
    }
    cin>>Gp->numEdges;
    for(k=0; knumEdges; k++)
    {
        cin>>i>>j;
        Gp->arc[i][j]=1;
        Gp->arc[j][i]=1;
    }
    for(k=0;knumEdges; k++)
    {
        cin>>Gp->weight[k];
    }
    k=0;
    for(i=0; inumNodes; i++) //邻接矩阵赋予权值
    {
        for(j=0; jnumNodes; j++)
        {
            if(Gp->arc[i][j]==1)
            {
                Gp->arc[i][j]=Gp->weight[k];
                Gp->arc[j][i]=Gp->weight[k];
                ++k;
            }
        }
    }
}

//输出邻接矩阵
void print_arc(MGraph *Gp)
{
    for(int i=0; inumNodes; i++)
    {
        for(int j=0; jnumNodes; j++)
        {
            cout<arc[i][j]<<" ";
            if(j==Gp->numNodes-1&&i!=Gp->numNodes-1)
            {
                cout<numNodes; i++)
    {
        if(i==Gp->numNodes-1)
        {
            cout<vexs[i]<vexs[i]<<" ";
        }
    }
}

int main()
{
    MGraph MG;
    string s;
    cin>>s;
    if(s=="DG"||s=="DN")
    {
        CreateDGraph(&MG);
        cout<