【图】图学习

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,ji = 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;
}