No testdata at current.

No submission language available for this problem.

数据结构——图论 I

一、图的简单概念

$G(V, E)$ 表示顶点与边的集合。表示数据多对多的关系。

如上图所示，$v_1, v_2，... v_5$ 表示顶点。$(v_1, v_2),(v_1,v_3),(v_2, v_3),(v_2, v_4),(v_3, v_4),(v_3, v_5),(v_4, v_5)。$ 表示边。表示无向无权图

如上图所示，表示无向有权图

如上图所示，表示有向无权图，<$v_i$,$v_j$> 表示一条弧边。表示弧尾指向弧头，即 <弧尾，弧头> 。如图中有一条弧 <$v_1$, $v_2$> ，$v_1$ 是弧尾，$v_2$ 是弧头。

如上图所示，表示有向有权图

当前阶段涉及的基本是简单图，即无重边和自环

一般图数据中若存在自环与重边，则会特殊表明。（提高级及以上有概率不提示）

其它图论相关概念如稀疏图，入度出度，度，稠密图，完全图等概念，这里不进行赘述。

---

二、图的简单存储

图存储的方式有多种，当前阶段主要运用三种：

1，邻接矩阵

2，邻接表

3，边集数组

构造有向图数据

5 7
1 2 4
1 3 6
2 4 9
3 2 19
4 3 1
5 4 3
5 3 6

1. 邻接矩阵

令 g[i][j] 表示 ($v_i$, $v_j$) 或 <$v_i$, $v_j$> 是否有边或权值是多少。

const int INF = 0x3f3f3f3f;

int n, m;
cin >> n >> m; // n 顶点 m 条边

// 由于有权值，因此需要对 g 初始化
memset(g, 0x3f, sizeof g);

for (int i = 1; i <= m; i ++) { // 输入 m 条边构建邻接矩阵
    int u, v, w;     // 起点，终点，权值
    cin >> u >> v >> w;
    g[u][v] = w;
    // g[v][u] = w; // 若是无向图，无向图是双向边，需要反向记录。 
    /*
    若有重边：
        有向边：g[u][v] = min{g[u][v], w}; 
        无向边：g[u][v] = g[v][u] = min{g[u][v], w};
    */
}

// 输出邻接矩阵查看存储结果
for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= n; j ++) {
        printf("%3d ", g[i][j]);
    }
    cout << endl;
}

2. 邻接表

令 vector<EdgeType> 类型的 g[i] 存储 i 的邻接点或邻接边信息。

// 带有边权，则要记录邻接边信息
struct Edge{
    int v, w;
};
vector<Edge> g[N];

int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i ++) {
    int u, v, w; 
    cin >> u >> v >> w;
    g[u].push_back(Edge{v, w});
    // g[v].push_back(Edge{u, w}); // 无向图是双向边，因此要双向存储记录。
}

for (int i = 1; i <= n; i ++) {
    cout << "顶点：" << i << endl;
    for (int j = 0; j < (int)g[i].size(); j ++) {
        printf("(邻接点: %d 权:%d)  ", g[i][j].v, g[i][j].w);
    }
    cout << endl;
}

3. 边集数组

直接记录顶点，邻接点与权的数据集合。链式前向星是边集数组的应用之一，Bellman-Ford 最短路算法也需要边集数组。

#include <bits/stdc++.h>
using namespace std;
struct Edge{
	int u, v, w;
};
Edge g[100];
int gi = 0;

int main() {	

	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[++ gi] = Edge{u, v, w}; 
		// g[++gi] = Edge{v, u, w}; // 若无向边，则还需要反向记录一条
	}

	for (int i = 1; i <= gi; i ++) {
		printf("No.%d, %d->%d: %d\n", i, g[i].u, g[i].v, g[i].w);
	}

    return 0;
}

链式前向星

链式前向星需要对链式结构有所了解，核心思路是一条<$v_i$, $v_j$> 的边，都会记录以 $v_i$ 为起点的下一条邻接边。

#include <bits/stdc++.h>
using namespace std;
struct Edge{
	int v, w, next;
};
Edge edge[100];   // 边集
int ei = 0;
int head[100]; // 顶点集
int n, m;     // 顶点数量 与 边数量

void add(int from, int to, int dis) {
	edge[++ ei].next = head[from]; // 以 from 为起点的下一条边的编号
	edge[ei].v = to; 
	edge[ei].w = dis;
	head[from] = ei; // 将顶点的起始边的编号更新
}

int main() {	


	cin >> n >> m;
	for (int i = 1; i <= m; i ++) {
		int u, v, w;
		cin >> u >> v >> w;
		add(u, v, w);
		// add(v, u, w); // 若无向边，需要反向再记录一次
	}

	// 遍历顶点
	for (int i = 1; i <= n; i ++) {
		printf("No. %d\n", i);
		for (int j = head[i]; j != 0; j = edge[j].next) {
			printf("(v%d, w%d)  ", edge[j].v, edge[j].w);
		}
		cout << endl;
	}


    return 0;
}

---

三、图的简单遍历

• 普通变量，直接使用该变量
• 一维数组，运用一重循环遍历
• 二维数组，运用二重循环遍历
• 树图结构，运用深度优先搜索和广度优先搜索遍历。

深度优先遍历（搜索）

广度优先遍历（搜索）

以上两种遍历方式，只是应用在图的存储基础之上，对某个顶点进行关联性遍历，即

• 深搜：顶点 $v_i$ 与顶点 $v_j$ 间有直连边，则可以从 $v_i$ 探寻 $v_j$
• 广搜：与顶点 $v_i$ 有直连边，且以之为起点的邻接顶点或邻接边，全入队列，准备下次扩散。