邻接矩阵

一，逻辑部分：

分为两部分：V和E集合。用一个一维数组存放所有顶点数据，用一个二维数组存放顶点间的关系数据，这个二维数组称为邻接矩阵。邻接矩阵分为有向图邻接矩阵和无向图邻接矩阵。

二，特点：

1),无向图的邻接矩阵一定是对称的，对于有n个顶点的无向图则只存上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1+2+.....+(n-1)=n*(n-1)/2个单元。

2），有向图的邻接矩阵不一定对称，表示图共需n^2个空间。

三，表示法：

1),用邻接矩阵表示顶点间的相邻关系

2)，用一个顺序表来存储顶点信息

图的矩阵

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

举例：

网络矩阵：

四，代码示例：

#include<iostream>using namespace std;#define MAXVEX 100/* 最大顶点数，应由用户定义 */#define INF 65535 /* 表示权值的无穷*///typedef int EdgeType;/* 边上的权值类型应由用户定义 *///typedef char VertexType;/* 顶点类型应由用户定义  */typedef struct{    char vexs[MAXVEX];/* 顶点表 */    int arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */    int numNodes, numEdges;/* 图中当前的顶点数和边数  */} MGraph;/* 建立无向网图的邻接矩阵表示 */void CreateMGraph(MGraph *Gp){    int i, j, k, w;    cout << "请输入顶点数和边数（空格分隔）：" << endl;    cin >> Gp->numNodes >> Gp->numEdges;    cout << "请输入顶点信息（空格分隔）：" << endl;    for (i = 0; i < Gp->numNodes; i++)        cin >> Gp->vexs[i];    for (i = 0; i < Gp->numNodes; i++)    {        for (j = 0; j < Gp->numNodes; j++)        {            if (i == j)                Gp->arc[i][j] = 0;/* 顶点没有到自己的边*/            else                Gp->arc[i][j] = INF;/* 邻接矩阵初始化 */        }    }    for (k = 0; k < Gp->numEdges; k++)    {        cout << "请输入边（vi, vj)的上标i，下标j和权值w（空格分隔）:" << endl;        cin >> i >> j >> w;        Gp->arc[i][j] = w;        Gp->arc[j][i] = Gp->arc[i][j];/* 因为是无向图，矩阵对称 */    }}int main(void){    MGraph MG;    CreateMGraph(&MG);    return 0;}