图的邻接矩阵表示法

1．图的邻接矩阵表示法

　在图的邻接矩阵表示法中：

　① 用邻接矩阵表示顶点间的相邻关系

　② 用一个顺序表来存储顶点信息

2．图的邻接矩阵(Adacency Matrix)

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：

【例】下图中无向图G5和有向图G6的邻接矩阵分别为Al和A2。

　若G是网络，则邻接矩阵可定义为：

 3．网络的邻接矩阵

其中：

wij表示边上的权值；

∞表示一个计算机允许的、大于所有边上权值的数。

【例】下面带权图的两种邻接矩阵分别为A3和A4。

C程

#define mvnum 100//最大定点数

#define maxint 9999

typedef char vertextype;

typedef int adjmatrix;

struct mgraph

{

vertextype vexs[mvnum];//顶点数组，假定为 char型

adjmatrix arcs[mvnum][mvnum];//临街矩阵，假定为int型

};

int d[mvnum][mvnum],p[mvnum][mvnum];

void createmgraph(mgraph *G)

{//采用邻接矩阵表示法构造无向图G

    int i,j,k,w;

    ifstream graphlist("map.txt",ios::in);//定义一个流对象，并且和文件关联

    for(i=1;i<=25;i++)

        G->vexs[i]=(char)i;

    for(i=1;i<=25;i++)

        for(j=1;j<=25;j++)

            G->arcs[i][j]=maxint;//初始化邻接矩阵    

        for(k=1;k<=30;k++)

        {

            //从磁盘文件接受数据构造网

         graphlist>>i;

            graphlist>>j;

            graphlist>>w;        

            G->arcs[i][j]=w;

            G->arcs[j][i]=G->arcs[i][j];//构造无向网

        }

        graphlist.close();//关闭文件

}

void floyd(mgraph *G)

{

    int i,j,k;

    for(i=1;i<=25;i++)//设置路径长度D和路径初值

        for(j=1;j<=25;j++)

        {

            if(G->arcs[i][j]!=maxint)

                p[i][j]=j;

            else

                p[i][j]=0;

            d[i][j]=G->arcs[i][j];

        }

        for(k=1;k<=25;k++)

        {

            for(i=1;i<=25;i++)

                for(j=1;j<=25;j++)

                {

                    if (d[i][k]+d[k][j]<d[i][j])

                    {

                        d[i][j]=d[i][k]+d[k][j];

                        p[i][j]=p[i][k];

                    }

                }

        }

}

void main()

{

mgraph *G;

int v,w,k;

int xz=1;

G=(mgraph *)malloc(sizeof(mgraph));

cout<<"欢迎进入铁路交通网查询系统."<<endl;

createmgraph(G);

while(xz!=0)

{

cout<<"*******求城市之间最短路径*******"<<endl;

cout<<"================================"<<endl;

     cout<<"请选择：1 查询 0 结束"<<endl;

     cout<<"================================"<<endl;

     cin>>xz;

     cout<<endl;

     if(xz)

     {

floyd(G);

         cout<<"城市名称及编号如下"<<endl;

         cout<<" 1 乌鲁木齐 2 哈尔滨 3 呼和浩特 4 长春 5 北京"<<endl;

         cout<<" 6 沈阳 7 西宁 8 天津 9 大连 10 兰州"<<endl;

         cout<<" 11 西安 12 郑州 13 徐州 14 成都 15 武汉"<<endl;

         cout<<" 16 上海 17 昆明 18 贵阳 19 株洲 20 南昌"<<endl;

         cout<<" 21 福州 22 南宁 23 柳州 24 广州 25 深圳"<<endl;

         cout<<"请输入源点和终点: "<<endl;

     cin>>v>>w;

         k=p[v][w];//k为起点i的后继顶点

         if(k==0)

             cout<<"无路径！"<<endl;

         else

         {

             cout<<"所求最短路径为："<<endl;

             cout<<v;

             while(k!=w)

             {

                 cout<<"->"<<k;

                 k=p[k][w];

             }

             cout<<"->"<<w;

             cout<<"路径长度为："<<d[v][w]<<"公里"<<endl;

         }

cout<<endl;

     }

     else

         cout<<"谢谢使用，祝您旅途愉快！"<<endl;

}

}