本文共 2727 字，大约阅读时间需要 9 分钟。

图的存储结构

1.1 邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

[ A = (a_{ij}) ]

其中，( a_{ij} ) 表示顶点 ( v_i ) 与顶点 ( v_j ) 之间的权值。无穷大表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。

从矩阵中，很容易知道图中的信息：

（1）要判断任意两顶点是否有边无边很容易了；

（2）要知道某个顶点的度，其实就是这个顶点 ( v_i ) 在邻接矩阵中第i行或（第i列）的元素之和；

（3）求顶点 ( v_i ) 的所有邻接点就是将矩阵中第i行元素扫描一遍，( arc[i][j] ) 为1就是邻接点；

而有向图讲究入度和出度，顶点 ( v_i ) 的入度为1，正好是第i列各数之和。顶点 ( v_i ) 的出度为2，即第i行的各数之和。

邻接矩阵是如何实现图的创建的呢？代码如下：

#include 
   
    #define MAXVERTEX 10#define INFINITY 255#define DEBUGtypedef char VertexType;typedef int MatrixValue;typedef struct tagGraph {    VertexType vexs[MAXVERTEX]; // 顶点数组    MatrixValue arc[MAXVERTEX][MAXVERTEX]; // 邻接矩阵    int numVertexes; // 顶点数    int numEdges; // 边数} Graph;int locate(Graph *g, VertexType ch) {    for(int i = 0; i < g->numVertexes; ++i) {        if(g->vexs[i] == ch)            return i;    }    return -1;}bool CreateGraph(Graph *g) {    std::cout << "Please input the number of Vertexes and the edges:" << std::endl;    std::cin >> g->numVertexes >> g->numEdges;        std::cout << "Please input the name of the vertexes (standard as char type):" << std::endl;    for(int i = 0; i < g->numVertexes; i++) {        g->vexs[i] = getchar();        while(g->vexs[i] == '\n') {            g->vexs[i] = getchar();        }    }        // 初始化边矩阵    for(int i = 0; i < g->numEdges; i++) {        for(int j = 0; j < g->numEdges; j++)            g->arc[i][j] = INFINITY;    }        // 读取边信息    for(int i = 0; i < g->numEdges; i++) {        VertexType p, q;        std::cout << "Please input the No." << i+1                   << " edge (vi, vj), and the value of the edge" << std::endl;        p = getchar();        while(p == '\n') {            p = getchar();        }        q = getchar();        while(q == '\n') {            q = getchar();        }        int value = 0;        std::cin >> value;        int m = locate(g, p);        int n = locate(g, q);        if(n == -1 || m == -1) {            std::cout << " there is no this vertex." << std::endl;            return false;        }        g->arc[m][n] = value;        g->arc[n][m] = g->arc[m][n];    }    return true;}void printGraph(const Graph *g) {    std::cout << "The structure of the graph is\n\t";    for(int i = 0; i < g->numVertexes; i++)        std::cout << g->vexs[i] << "\t";    std::cout << std::endl;        for(int i = 0; i < g->numVertexes; i++) {        std::cout << g->vexs[i] << "\t";        for(int j = 0; j < g->numVertexes; j++)            std::cout << g->arc[i][j] << "\t";        std::cout << std::endl;    }}int main() {    Graph g;    CreateGraph(&g);    printGraph(&g);    return 0;}
   

运行结果如下：

从代码中可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为O(n + n² + e)，其中对邻接矩阵Grc的初始化耗费了O(n²)的时间。