网站网络推广教程,网站建设毕业设计选题,淘宝网网页,搭建平台的另一种说法图的遍历(Travering Graph):从图的某一顶点出发#xff0c;访遍图中的其余顶点#xff0c;且每个顶点仅被访问一次#xff0c;图的遍历算法是各种图的操作的基础。 复杂性:图的任意顶点可能和其余的顶点相邻接#xff0c;可能在访问了某个顶点后#xff0c;沿某条路径搜索…图的遍历(Travering Graph):从图的某一顶点出发访遍图中的其余顶点且每个顶点仅被访问一次图的遍历算法是各种图的操作的基础。 复杂性:图的任意顶点可能和其余的顶点相邻接可能在访问了某个顶点后沿某条路径搜索后又回到原顶点。 解决办法:在遍历过程中记下已被访问过的顶点。设置一个辅助向量 Visited[1…nl(n为顶点数)其初值为0一旦访问了顶点v后使Visited[li]为1或为访问的次序号。
深度优先搜索Depth First Search – DFS
深度优先搜索Depth-First SearchDFS 是一种遍历或搜索树或图的算法。其基本思想是从起始节点出发沿着每一条路径一直走下去直到无法继续为止再回溯到最近的分叉点继续沿着另一条路径走。这样递归地进行直到所有节点都被访问到。
DFS 适用于树和图这两种数据结构。DFS 的搜索方式“深度优先”即尽量深入每一条路径直到没有更多节点可以访问再回溯并继续遍历其他路径。
DFS 工作流程 1.从起始节点开始选择一个未被访问的节点作为起始节点。 2.访问当前节点首先标记该节点为已访问并处理该节点例如打印或执行其他操作。 3.递归访问邻居节点然后继续访问该节点的一个未被访问的邻居节点递归进行深度优先搜索。 4.回溯当所有邻居节点都已经访问过时回溯到上一个节点继续探索其他未访问的邻居节点。 5.结束条件直到所有节点都被访问过为止DFS 完成。 深度优先搜索的特征 1.递归DFS 最自然的实现方式是递归。 2.回溯DFS 通过回溯的方式重新返回到上一个节点继续探索。 3.栈结构DFS 也可以通过显式栈来实现栈结构符合 DFS 中的“后进先出”LIFO特性。 4.图的遍历DFS 可以遍历图中的所有节点和边适用于查找图的连通性、寻找环等问题。
DFS遍历下图C语言示例 0/ \1 2/ \
3 4 #include stdio.h
#include stdbool.h#define MAX_VERTICES 5 // 最大顶点数本例中为 5// 图的邻接矩阵表示
int graph[MAX_VERTICES][MAX_VERTICES];// visited 数组用于记录顶点是否被访问过
bool visited[MAX_VERTICES];// 深度优先搜索函数
void dfs(int vertex, int n) {// 标记当前顶点为已访问visited[vertex] true;printf(%d , vertex);// 遍历所有相邻的顶点for (int i 0; i n; i) {if (graph[vertex][i] 1 !visited[i]) {dfs(i, n); // 递归访问相邻的未访问顶点}}
}int main() {int n 5; // 顶点数int m 4; // 边数// 初始化图的邻接矩阵和 visited 数组for (int i 0; i n; i) {for (int j 0; j n; j) {graph[i][j] 0;}visited[i] false;}// 输入图的边无向图graph[0][1] 1; graph[1][0] 1; // 0-1graph[0][2] 1; graph[2][0] 1; // 0-2graph[1][3] 1; graph[3][1] 1; // 1-3graph[1][4] 1; graph[4][1] 1; // 1-4// 从顶点 0 开始进行 DFSprintf(深度优先搜索的结果:\n);dfs(0, n);return 0;
}
广度优先搜索Breadth First Search – BFS
广度优先搜索Breadth-First SearchBFS 是一种图遍历算法它从图的起始节点开始首先访问该节点的所有邻居然后访问这些邻居的邻居依此类推直到所有节点都被访问。
与**深度优先搜索DFS**不同BFS 的搜索顺序是“广度优先”的即先访问离起始节点较近的节点然后逐渐向远离起始节点的地方扩展。
BFS 的核心思想是 1.从起始节点开始先访问当前节点的所有邻居。 2.将这些邻居节点按顺序加入一个队列。 3.然后从队列中取出下一个节点访问该节点的所有未被访问过的邻居。 4.将这些邻居节点加入队列中继续重复该过程直到所有节点都被访问过为止。
BFS 的工作流程 1.初始化首先将起始节点加入队列并标记为已访问。 2.队列操作从队列中取出一个节点访问它并将该节点的所有未被访问的邻居加入队列。 3.重复操作重复步骤 2直到队列为空为止。 BFS 关键点 1.队列QueueBFS 使用队列来存储待访问的节点队列保证了“先进先出”FIFO的顺序。 2.层次遍历BFS 会按层次逐级访问图中的节点层与层之间是按距离起始节点的远近来定义的。 3.适用于无权图的最短路径BFS 能在无权图中找到从起始节点到目标节点的最短路径。 示例BFS遍历下图 0/ \1 2/ \
3 4 #include stdio.h
#include stdbool.h
#include stdlib.h#define MAX_VERTICES 5 // 最大顶点数本例中为 5
#define MAX_QUEUE_SIZE 100 // 队列的最大大小// 图的邻接矩阵表示
int graph[MAX_VERTICES][MAX_VERTICES];// visited 数组用于记录顶点是否被访问过
bool visited[MAX_VERTICES];// 队列结构
typedef struct {int items[MAX_QUEUE_SIZE];int front;int rear;
} Queue;// 初始化队列
void initQueue(Queue* q) {q-front -1;q-rear -1;
}// 判断队列是否为空
int isEmpty(Queue* q) {return q-front -1;
}// 队列入队
void enqueue(Queue* q, int value) {if (q-rear MAX_QUEUE_SIZE - 1) {printf(队列已满\n);return;}if (q-front -1) {q-front 0;}q-rear;q-items[q-rear] value;
}// 队列出队
int dequeue(Queue* q) {if (isEmpty(q)) {printf(队列为空\n);return -1;}int value q-items[q-front];q-front;if (q-front q-rear) {q-front q-rear -1; // 队列为空}return value;
}// 广度优先搜索BFS函数
void bfs(int startVertex, int n) {Queue q;initQueue(q);// 将起始顶点入队并标记为已访问visited[startVertex] true;enqueue(q, startVertex);while (!isEmpty(q)) {int currentVertex dequeue(q);printf(%d , currentVertex);// 遍历当前顶点的所有相邻顶点for (int i 0; i n; i) {if (graph[currentVertex][i] 1 !visited[i]) {visited[i] true; // 标记相邻顶点为已访问enqueue(q, i); // 将未访问的相邻顶点入队}}}
}int main() {int n 5; // 顶点数int m 4; // 边数// 初始化图的邻接矩阵和 visited 数组for (int i 0; i n; i) {for (int j 0; j n; j) {graph[i][j] 0;}visited[i] false;}// 输入图的边无向图graph[0][1] 1; graph[1][0] 1; // 0-1graph[0][2] 1; graph[2][0] 1; // 0-2graph[1][3] 1; graph[3][1] 1; // 1-3graph[1][4] 1; graph[4][1] 1; // 1-4// 从顶点 0 开始进行 BFSprintf(广度优先搜索的结果:\n);bfs(0, n);return 0;
}BFS 与 DFS 的区别 DFS深度优先搜索 是“深度优先”BFS 是“广度优先”。 DFS 会一直沿着一条路径走下去直到没有未访问的邻居之后才会回溯BFS 则是逐层访问保证了先访问起始节点的所有邻居再访问下一层。 BFS 在无权图中可以保证找到最短路径而 DFS 不一定。 在图论中**最小生成树Minimum Spanning TreeMST **是一个无向连通加权图的生成树其边的权重之和最小。生成树是图的一部分它包含图中所有的节点并且是一个树结构无环连通图。 最小生成树边与点的关系最小生成树的顶点数n与边数e之间的关系ne1
普里姆算法Prim算法
Prim 算法 是一种贪心算法用来求解图的最小生成树。它从一个节点出发逐步选择最小权重的边直到图中的所有节点都被包含在内。与 Kruskal 算法 相比Prim 算法更适用于稠密图。
Prim 算法的基本思想 1.从图的任意一个节点开始加入最小生成树的集合。 2.在已加入的节点集合所相连的边中选择一条最小权重的边将其相邻的节点加入集合。 3.重复步骤 2直到所有节点都被加入最小生成树中。 #include stdio.h
#include limits.h // 包含 INT_MAX#define MAX_VERTICES 5 // 图中的顶点数// 图的邻接矩阵表示用 -1 表示没有边
int graph[MAX_VERTICES][MAX_VERTICES] {{0, 2, 3, 4, -1},{2, 0, -1, 5, -1},{3, -1, 0, 1, -1},{4, 5, 1, 0, -1},{-1, -1, -1, -1, 0}
};// Prim 算法函数
void prim(int n) {int parent[MAX_VERTICES]; // 存储最小生成树的父节点int key[MAX_VERTICES]; // 存储每个顶点到生成树的最小边权值int inMST[MAX_VERTICES]; // 判断顶点是否在最小生成树中// 初始化所有值for (int i 0; i n; i) {key[i] INT_MAX; // 关键值初始化为无穷大inMST[i] 0; // 所有顶点都不在最小生成树中parent[i] -1; // 没有父节点}key[0] 0; // 从顶点 0 开始for (int count 0; count n - 1; count) {// 选择一个最小权值的顶点int u -1;int min INT_MAX;for (int v 0; v n; v) {if (!inMST[v] key[v] min) {min key[v];u v;}}// 将选择的顶点 u 加入最小生成树inMST[u] 1;// 更新与 u 相邻的顶点的关键值for (int v 0; v n; v) {// graph[u][v] ! -1 表示 u 和 v 之间有边if (graph[u][v] ! -1 !inMST[v] graph[u][v] key[v]) {key[v] graph[u][v];parent[v] u;}}}// 输出最小生成树的边和权值printf(最小生成树的边和权值\n);for (int i 1; i n; i) {printf(%d - %d: %d\n, parent[i], i, graph[i][parent[i]]);}
}int main() {int n 5; // 图中的顶点数prim(n); // 调用 Prim 算法return 0;
}
克鲁斯卡尔(Kruskal)算法
Kruskal 算法 是求解最小生成树的另一种经典算法。它是一个贪心算法选择图中权重最小的边将它们逐步添加到生成树中确保每次添加的边不会形成环。Kruskal 算法非常适合用于稀疏图。 Kruskal 算法的基本思想 1.排序将图中的所有边按边的权重进行升序排序。 2.并查集使用并查集Union-Find数据结构来判断添加边后是否形成环。若添加的边连接了两个不同的连通分量则将这两个分量合并若它们已经在同一个连通分量中则跳过这条边。 3.构建最小生成树从排序后的边中依次选择若选择的边不形成环则将其添加到最小生成树中直到最小生成树中包含 V-1 条边V 是节点的数量。
#include stdio.h
#include stdlib.h#define MAX_VERTICES 5 // 顶点数// 边的结构体
typedef struct {int u, v, weight;
} Edge;// 并查集的数据结构
int parent[MAX_VERTICES];
int rank[MAX_VERTICES];// 初始化并查集
void initUnionFind(int n) {for (int i 0; i n; i) {parent[i] i; // 每个顶点的父节点初始化为自己rank[i] 0; // 初始秩为 0}
}// 查找操作带路径压缩
int find(int x) {if (parent[x] ! x) {parent[x] find(parent[x]); // 路径压缩}return parent[x];
}// 合并操作按秩合并
void unionSets(int x, int y) {int rootX find(x);int rootY find(y);if (rootX ! rootY) {// 按秩合并if (rank[rootX] rank[rootY]) {parent[rootY] rootX;} else if (rank[rootX] rank[rootY]) {parent[rootX] rootY;} else {parent[rootY] rootX;rank[rootX];}}
}// 比较函数用于按权值升序排序边
int compare(const void* a, const void* b) {return ((Edge*)a)-weight - ((Edge*)b)-weight;
}// 克鲁斯卡尔算法
void kruskal(Edge edges[], int n, int m) {// 初始化并查集initUnionFind(n);// 排序边qsort(edges, m, sizeof(Edge), compare);int mstWeight 0;printf(最小生成树的边和权值\n);// 遍历所有边选择不形成环的边for (int i 0; i m; i) {int u edges[i].u;int v edges[i].v;int weight edges[i].weight;if (find(u) ! find(v)) {unionSets(u, v);printf(%d - %d: %d\n, u, v, weight);mstWeight weight;}}printf(最小生成树的总权值%d\n, mstWeight);
}int main() {// 图的边每条边包含两个顶点和边的权值Edge edges[] {{0, 1, 2},{0, 2, 3},{0, 3, 4},{1, 3, 5},{2, 3, 1}};int n 5; // 顶点数int m 5; // 边数// 调用克鲁斯卡尔算法kruskal(edges, n, m);return 0;
}
迪杰斯特拉(Dijkstra)算法 #include stdio.h
#include limits.h // 包含 INT_MAX表示无穷大
#include stdbool.h#define MAX_VERTICES 6 // 顶点数// 图的邻接矩阵表示
int graph[MAX_VERTICES][MAX_VERTICES] {{0, 7, -1, 9, 9, -1},{7, 0, 5, 6, -1, -1},{-1, 5, 0, -1, -1, 8},{9, 6, -1, 0, 4, 1},{9, -1, -1, 4, 0, 3},{-1, -1, 8, 1, 3, 0}
};// 迪杰斯特拉算法
void dijkstra(int start, int n) {int dist[MAX_VERTICES]; // 存储起点到各个顶点的最短距离bool visited[MAX_VERTICES]; // 标记顶点是否已访问过// 初始化for (int i 0; i n; i) {dist[i] INT_MAX; // 设置初始距离为无穷大visited[i] false; // 标记所有顶点为未访问}dist[start] 0; // 起点到自身的距离为 0for (int count 0; count n - 1; count) {// 在未访问的顶点中找到最小的距离int u -1;int minDist INT_MAX;for (int v 0; v n; v) {if (!visited[v] dist[v] minDist) {minDist dist[v];u v;}}// 标记该顶点为已访问visited[u] true;// 更新与 u 相邻的顶点的距离for (int v 0; v n; v) {if (graph[u][v] ! -1 !visited[v] dist[u] graph[u][v] dist[v]) {dist[v] dist[u] graph[u][v]; // 更新最短距离}}}// 输出最短路径printf(从顶点 %d 到其他顶点的最短路径为\n, start);for (int i 0; i n; i) {if (dist[i] INT_MAX) {printf(%d 到 %d: 无路径\n, start, i);} else {printf(%d 到 %d: %d\n, start, i, dist[i]);}}
}int main() {int n 6; // 图中的顶点数int start 0; // 起点选择 0// 调用 Dijkstra 算法dijkstra(start, n);return 0;
} 我们一天天地活着并不是理所当然而是莫大的奇迹。归根结底连我们此刻的心脏搏动都是一种奇迹。 —星野道夫
