【图】图学习

0 回顾数据结构逻辑

1 图的定义和基本术语

必须有顶点，可以没有边。

Cn2和2*Cn2（数学上的，n个顶点取2个顶点）

概念有些多。。。。。。

2 图的定义

3 图的存储结构

无向图的邻接矩阵

有向图的邻接矩阵

网（有权图）的邻接矩阵

邻接矩阵

邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵

#define MaxInt 32767             // 表示极大值，即∞
#define MVNum 100                // 最大顶点数
typedef char VerTexType;         // 设顶点的数据类型为字符型
typedef int ArcType;             // 假设边的权值类型为整型


typedef struct {
    VerTexIype vexs[MVNum];          // 顶点表
    ArcType arcs[MVNum][MVNum];      // 邻接矩阵
    int vexnum, arcnum;              // 图的当前点数和边数
} AMGraph; 
// Adjacency Matrix Graph

2、采用邻接矩阵表示法创建无向网

【算法思想】

(1)输入总顶点数和总边数；

(2)依次输入点的信息存入顶点表中；

(3)初始化邻接矩阵，使每个权值初始化为极大值；

(4)构造邻接矩阵。

创建无向网

void CreatUDN(AMGraph &G)
{
    // 第一步：输入无向图的顶点数目
    cout << "input num" << endl;
    cin >> G.arcnum >> G.arcnum; // 输入总顶点数和总边数
    // 第二步：输入结点的名称，保存在一维数组中
    cout << "input vexs" << endl;
    for (int i = 0; i < G.vexnum; ++i)
    {
        cin >> G.vexs[i];
    }
    // 第三步：将邻接矩阵的元素值置为无穷大
    for (int i = 0; i < G.arcnum; ++i)
    {
        for (int j = 0; j < G.arcnum; ++j)
        {
            G.arcs[i][j] = INT32_MAX;
        }
    }
    // 第四步：输入顶点相互关系以及权重
    for (int k = 0; k < G.arcnum; ++k)
    {
        int i, j, weight;
        char a, b;
        cin >> a >> b >> weight;
        // 由输入的顶点a和b查找到对应的下标i,j
        i = LocateVex(G, a);
        j = LocateVex(G, b);
        G.arcs[i][j] = G.arcs[j][i] = weight;
    }
}

邻接矩阵的LocateVex函数

int LocateVex(AMGraph &G, const char &e)
{
    for (int i = 0; i < G.vexnum; ++i)
    {
        if(G.vexs[i] == e)
            return i;
    }
    return -1;
}