图论相关--邻接矩阵

什么是图，简单的来说，图就是由顶点集V和边集E构成，假设我们的顶点集有n个顶点，那么我们的边可以是从0到（n（n-1））/2这么多，如果还考虑方向的话，那么边的条数将达到nn，所以，我们根据边的特性，将图分为了有向图，有向网，无向图，无向网；我们根据边是否有向分类，同时，我们在根据边的信息的特征再细分下去，图的边是没有权值的，网的边的是带有权值的。下面两幅图，左边的有向网，右边的是有向图，从边是否带有权值就可以区分。

[gallery ids=”428,427” type=”rectangular” link=”file”]

接着，我们看右边的图，任意两个点之间是否存在路径使之相同呢？很显然，任意两个点是相同的，我们称这种图是强连通的，那么如果存在两个点之间没有相同路径的情况呢？这时，我们把这个图中的存在极大连通的子图称作该图的强连通分量。
有关图的知识点还有很多，今天我们先讲讲怎么把图有代码表示出来—-也就是有什么数据结构去表示。
看了这篇文章，应该很快就清楚了我们这篇文章中表示图的方式，没错，就是用静态数组。用几维的呢？我们观察图可知，图的边（弧）两端连接着两个顶点，那么，我们自然会想到用二维的数组去表示，第一维的下表我们可以表示边的一端（弧的弧头），第二维表示边的另一端（弧尾），而存储的值呢？如果是无向图，那么我们就用0,1表示这条边是否存在，如果是有向图，我们可以用-1,0，1去表示弧存不存在，其中1和-1是代表了弧的方向；如果是有向网和无向网呢？那么边是否存在就由原来的0，1转变为了权值的大小，我们可以设权值无限大代表改变不存在。图的存储结构是解决了，那么图的信息和管理呢？我们可以创建一个结构体，结构体中存储着该图的顶点个数，边（弧）数以及图的类型（图的类型我们可以用一个枚举数据类型去实现），现在，我给出代码：

#define INFINTY INT32_MAX
#define MAX_VERTEX_NUM 20
#define MAX_NAME 3
#define MAX_INFO 20
typedef char VertexType[MAX_NAME];
typedef char InfoType;

enum GraphKind
{
    DG,
    DN,
    UDG,
    UDN
};
int IncInfo;

typedef struct
{
    //图节点（如果是图，则代表边是否存在，如果是网，则是权值信息）
    int adj;
    InfoType *info;
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

struct MGraph
{
    //顶点集向量
    VertexType vexs[MAX_VERTEX_NUM];
    //边集
    AdjMatrix arcs;
    //顶点的个数以及边的条数
    int vexnum, arcnum;
    //图的类型
    GraphKind kind;
};

/**
 * 创建有向图
 * @param G
 * @return
 */
bool CreateDG(MGraph &G)
{
    int i, j, k, l;
    char s[MAX_INFO], *info;
    VertexType va, vb;
    cout << "请输入有向图G的顶点数，弧数，弧是否含其他信息（是：1，否：0）" << endl;
    cin >> G.vexnum >> G.arcnum >> IncInfo;
    cout << endl
         << "请输入" << G.vexnum << "个顶点的值（小于" << MAX_NAME << "个字符）：" << endl;
    for (i = 0; i < G.vexnum; i++)
        // scanf("%s", G.vexs[i]);
        cin >> G.vexs[i];
    for (i = 0; i < G.vexnum; i++)
    {
        for (j = 0; j < G.vexnum; j++)
        {
            G.arcs[i][j].adj = 0;
            G.arcs[i][j].info = NULL;
        }
    }
    cout << endl
         << "请输入" << G.arcnum << "条的弧尾，弧头（以空格作为间隔符）" << endl;
    for (k = 0; k < G.arcnum; k++)
    {
        // scanf("%s %s", &va, &vb);
        i = LocateVex(G, va);
        cin >> va >> vb;
        j = LocateVex(G, vb);
        G.arcs[i][j].adj = 1;
        if (IncInfo)
        {
            cout << "请输入该弧的相关信息（小于" << MAX_INFO << "个字符：" << endl;
            scanf("%s", &s);
            l = strlen(s);
            if (l)
            {
                info = new char[l + 1];
                strcpy(info, s);
                G.arcs[i][j].info = info;
            }
        }
    }
    G.kind = DG;
    return true;
}

/**
 * 创建有向网
 * @param G
 * @return
 */
bool CreateDN(MGraph &G)
{
    int i, j, k, w, IncInfo;
    char s[MAX_INFO], *info;
    VertexType va, vb;
    cout << "请输入有向网G的顶点数，弧数，弧是否含其他信息（是：1，否：0）" << endl;
    cin >> G.vexnum >> G.arcnum >> IncInfo;
    cout << endl
         << "请输入" << G.vexnum << "个顶点的值（小于" << MAX_NAME << "个字符）：" << endl;
    for (i = 0; i < G.vexnum; i++)
        // scanf("%s", G.vexs[i]);
        cin >> G.vexs[i];
    for (i = 0; i < G.vexnum; i++)
    {
        for (j = 0; j < G.vexnum; j++)
        {
            G.arcs[i][j].adj = INFINTY;
            G.arcs[i][j].info = NULL;
        }
    }
    cout << endl
         << "请输入" << G.arcnum << "条的弧尾，弧头，权值（以空格作为间隔符）" << endl;
    for (k = 0; k < G.arcnum; k++)
    {
        // scanf("%s %s %d", &va, &vb, &w);
        cin >> va >> vb >> w;
        i = LocateVex(G, va);
        j = LocateVex(G, vb);
        G.arcs[i][j].adj = w;
        if (IncInfo)
        {
            cout << "请输入该弧的相关信息（小于" << MAX_INFO << "个字符：" << endl;
            scanf("%s", &s);
            w = strlen(s);
            if (w)
            {
                info = new char[w + 1];
                strcpy(info, s);
                G.arcs[i][j].info = info;
            }
        }
    }
    G.kind = DN;
    return true;
}

/**
 * 创建无向图
 * @param G
 * @return
 */
bool CreateUDG(MGraph &G)
{
    int i, j, k, l, IncInfo;
    char s[MAX_INFO], *info;
    VertexType va, vb;
    cout << "请输入无向图G的顶点数，边数，边是否含其他信息（是：1，否：0）" << endl;
    cin >> G.vexnum >> G.arcnum >> IncInfo;
    cout << endl
         << "请输入" << G.vexnum << "个顶点的值（小于" << MAX_NAME << "个字符）：" << endl;
    for (i = 0; i < G.vexnum; i++)
        // scanf("%s", G.vexs[i]);
        cin >> G.vexs[i];
    for (i = 0; i < G.vexnum; i++)
    {
        for (j = 0; j < G.vexnum; j++)
        {
            G.arcs[i][j].adj = 0;
            G.arcs[i][j].info = NULL;
        }
    }
    cout << endl
         << "请输入" << G.arcnum << "条边（以空格作为间隔符）" << endl;
    for (k = 0; k < G.arcnum; k++)
    {
        // scanf("%s %s", &va, &vb);
        cin >> va >> vb;
        i = LocateVex(G, va);
        j = LocateVex(G, vb);
        G.arcs[i][j].adj = G.arcs[j][i].adj = 1;
        if (IncInfo)
        {
            cout << "请输入该边的相关信息（小于" << MAX_INFO << "个字符：" << endl;
            scanf("%s", &s);
            l = strlen(s);
            if (l)
            {
                info = new char[l + 1];
                strcpy(info, s);
                G.arcs[i][j].info = G.arcs[j][i].info = info;
            }
        }
    }
    G.kind = DN;
    return true;
}

/**
 * 创建无向网
 * @param G
 * @return
 */
bool CreateUDN(MGraph &G)
{
    int i, j, k, w, IncInfo;
    char s[MAX_INFO], *info;
    VertexType va, vb;
    cout << "请输入无向网G的顶点数，边数，边是否含其他信息（是：1，否：0）" << endl;
    cin >> G.vexnum >> G.arcnum >> IncInfo;
    cout << endl
         << "请输入" << G.vexnum << "个顶点的值（小于" << MAX_NAME << "个字符）：" << endl;
    //构造顶点集向量
    for (i = 0; i < G.vexnum; i++)
        // scanf("%s", G.vexs[i]);
        cin >> G.vexs[i];
    //初始化所有边的信息
    for (i = 0; i < G.vexnum; i++)
    {
        for (j = 0; j < G.vexnum; j++)
        {
            G.arcs[i][j].adj = INFINTY;
            G.arcs[i][j].info = NULL;
        }
    }
    cout << endl
         << "请输入" << G.arcnum << "条边及权值（以空格作为间隔符）" << endl;
    for (k = 0; k < G.arcnum; k++)
    {
        //输入边的两个顶点找到这个边
        // scanf("%s %s %d", &va, &vb, &w);
        cin >> va >> vb >> w;
        //找到顶点Va的位置
        i = LocateVex(G, va);
        //找到顶点Vb的位置
        j = LocateVex(G, vb);
        G.arcs[i][j].adj = G.arcs[j][i].adj = w;
        if (IncInfo)
        {
            cout << "请输入该边的相关信息（小于" << MAX_INFO << "个字符：" << endl;
            scanf("%s", &s);
            w = strlen(s);
            if (w)
            {
                info = new char[w + 1];
                strcpy(info, s);
                G.arcs[i][j].info = G.arcs[j][i].info = info;
            }
        }
    }
    G.kind = DN;
    return true;
}