图论基础及应用数据结构与算法

【图论基础及应用】
图论基础及应用

基础知识

图的表示方法

并查集
最小生成树

代码步骤
代码实现

最短路径 -- dijkstra算法

代码步骤
代码实现

基础知识图的表示方法图的表示方法有邻接矩阵和邻接链表

邻接矩阵：适用于稠密图（边数接近于完全图）
邻接链表：适用于稀疏图（边数远远少于完全图）

并查集最小生成树代码步骤

定义边集
并查集部分
kruskal算法部分：1）初始化并查集 2）按照边权递增的顺序对边进行排序 3）遍历边

代码实现

//图 #include #include using namespace std; const int MAXV = 1010; const int MAXE = 1010; //边集定义部分 struct edge { int u, v; int cost; }E[MAXE]; bool cmp(edge a, edge b) { return a.cost < b.cost; }//并查集部分 int Tree[MAXV]; int findRoot(int x) { if (Tree[x] == -1) return x; else { int temp = findRoot(Tree[x]); Tree[x] = temp; return temp; } }//kruskal部分 int kruskal(int n, int m) { //n:顶点数，m：边数 int ans = 0; int Num_Edge = 0; for (int i = 1; i <= n; i++) Tree[i] = -1; sort(E + 1, E + m + 1, cmp); for (int i = 1; i <= m; i++) { int a = findRoot(E[i].u); int b = findRoot(E[i].v); if (a != b) { Tree[a] = b; ans = ans + E[i].cost; Num_Edge++; } if (Num_Edge == n - 1) break; } if (Num_Edge == n - 1) return ans; else return -1; }int main() { int n; while (scanf("%d", &n) != EOF && n != 0) { int m = n * (n - 1) / 2; for (int i = 1; i <= m; i++) scanf("%d %d %d", &E[i].u, &E[i].v, &E[i].cost); cout << kruskal(n, m) << endl; } system("pause"); return 0; }

最短路径 – dijkstra算法求解连通图中的单源最短路径，得到起点s到其他点的最短路径。
第二标尺：当存在多条最短路径时，以第二标尺作为衡量指标，例如：边权（花费最小）、点权(求最大)、最短距离的条数
代码步骤 1.初始化

最短距离
d[u] : d[s] = 0 其他的 d[u] = INF
边权
c[u]：c[s] = 0 其他的 c[u] = INF
点权
w[u]：w[s] = weight[s] 其他 w[u] = 0
最短距离的条数
num[u]：num[s] = 1 其他num[u] = 0

(以下步骤循环n次，直到n个节点都访问过)
2.在未访问的集合中，寻找使 d[u] 最小的结点u
3.访问结点u，即把结点u放进已经访问过的集合S中
4.优化d[v]: 更新所有以u作为中间节点的d[v]
代码实现

//开始玩转Dijkstra //Dijkstra模板 //模板思路：1）在未访问的点的集合中寻找使d[u]最小的u 2）在未访问的结点中，更新所有以u为中间结点的d[v]#include using namespace std; const int MAXV = 1100; const int INF = 1e9; int G[MAXV][MAXV]; //存放图，以邻接矩阵的形式 int d[MAXV]; //当前最短路径：起点到达各个终点的最短路径长度d[u]：源结点s到结点u的最短路径 bool visit[MAXV] = {false}; //用来判断当前节点是否已经被访问void dijkstra(int n, int s) { //n为顶点数，s为起始节点 //数组d[MAXV]的初始化 fill(d + 1, d + n + 1, INF); d[s] = 0; for (int i = 1; i <= n; i++) { //寻找最小的d[u]的标号u int temp = INF; int u; for (int j = 1; j <= n; j++) { if (visit[j] == false && d[j] < temp) { temp = d[j]; u = j; } } visit[u] = true; for (int v = 1; v <= n; v++) { if (visit[v] == false && G[u][v] != INF && G[u][v] + d[u] < d[v]) d[v] = G[u][v] + d[u]; } }}int main() { int n, m,s; int u, v, cost; scanf("%d %d %d", &n, &m, &s); fill(G[0], G[0] + MAXV * MAXV, INF); for (int i = 1; i <= m; i++) { scanf("%d %d %d", &u, &v, &cost); G[u][v] = cost; } dijkstra(n, s); for (int i = 1; i <= n; i++) cout << d[i] << " "; system("pause"); return 0; }