松北区建设局网站,yy直播能赚钱吗,sem培训班,廊坊百度快速排名图#xff08;Graph#xff09;是一种非常灵活且强大的数据结构#xff0c;用于表示实体之间的复杂关系。在图结构中#xff0c;数据由一组节点#xff08;或称为顶点#xff09;和连接这些节点的边组成。图可以用于表示社交网络、交通网络、网络路由等场景。
1. 基本概… 图Graph是一种非常灵活且强大的数据结构用于表示实体之间的复杂关系。在图结构中数据由一组节点或称为顶点和连接这些节点的边组成。图可以用于表示社交网络、交通网络、网络路由等场景。
1. 基本概念 节点Vertex图中的一个点代表一个对象或实体。 边Edge连接两个节点的线代表节点之间的关系。 邻接Adjacency如果两个节点之间有边相连则称这两个节点是邻接的。 路径Path一系列相连的边从一个节点开始经过若干个中间节点到达另一个节点。 环Cycle起点和终点是同一个节点的路径。 连通图Connected Graph图中任意两个节点之间都存在路径。 强连通图Strongly Connected Graph有向图中任意两个节点之间都存在有向路径。 树Tree一种特殊的图没有环且任意两个节点之间只有一条路径。 2. 表示方法
2.1 邻接矩阵Adjacency Matrix 使用一个二维数组来表示图数组的行和列代表节点元素值表示节点之间是否有边。 适用于稠密图即边的数量接近节点数量平方的图。
2.2 邻接表Adjacency List 使用一个链表数组来表示图每个链表包含与该节点相连的所有节点。 适用于稀疏图即边的数量远小于节点数量平方的图。 3. 遍历算法
3.1 深度优先搜索Depth-First Search, DFS 类似于树的前序遍历使用栈递归或显式栈来实现。 从任意节点开始尽可能深地搜索图的分支。 public class GraphDFS {private int V; // 节点数private LinkedListInteger adj[]; // 邻接表// 构造函数SuppressWarnings(unchecked)public GraphDFS(int v) {V v;adj new LinkedList[v];for (int i 0; i v; i)adj[i] new LinkedList();}// 添加边public void addEdge(int v, int w) {adj[v].add(w); // 添加w到v的邻接表}// DFS算法public void DFS(int v) {boolean visited[] new boolean[V];// 调用递归的DFS函数DFSUtil(v, visited);}// 递归的DFS函数void DFSUtil(int v, boolean visited[]) {// 标记当前节点为已访问visited[v] true;System.out.print(v );// 递归访问所有未访问的邻接节点for (int i 0; i adj[v].size(); i) {int n adj[v].get(i);if (!visited[n])DFSUtil(n, visited);}}// 测试DFS算法public static void main(String[] args) {GraphDFS g new GraphDFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println(DFS starting from vertex 2 : );g.DFS(2);}
} 3.2 广度优先搜索Breadth-First Search, BFS 类似于树的层序遍历使用队列来实现。 从任意节点开始逐层遍历图中的节点。 import java.util.*;public class GraphBFS {private int V; // 节点数private LinkedListInteger adj[]; // 邻接表// 构造函数SuppressWarnings(unchecked)public GraphBFS(int v) {V v;adj new LinkedList[v];for (int i 0; i v; i)adj[i] new LinkedList();}// 添加边public void addEdge(int v, int w) {adj[v].add(w); // 添加w到v的邻接表}// BFS算法public void BFS(int s) {boolean visited[] new boolean[V];// 创建一个队列用于BFSQueueInteger queue new LinkedList();// 标记起始节点为已访问并入队visited[s] true;queue.add(s);while (queue.size() ! 0) {// 出队一个节点s queue.poll();System.out.print(s );// 访问其所有未访问的邻接节点for (int i 0; i adj[s].size(); i) {int n adj[s].get(i);if (!visited[n]) {visited[n] true;queue.add(n);}}}}// 测试BFS算法public static void main(String[] args) {GraphBFS g new GraphBFS(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.addEdge(3, 3);System.out.println(BFS starting from vertex 2 : );g.BFS(2);}
} 4. 算法应用 最短路径问题 Dijkstra算法适用于带有非负权重的图。 Bellman-Ford算法适用于带有负权重的图。 Floyd-Warshall算法计算图中所有节点对的最短路径。 最小生成树问题 Kruskal算法贪心算法适用于边的集合是无序的。 Prim算法贪心算法适用于节点的集合是无序的。 网络流问题 Ford-Fulkerson方法计算网络中的最大流。 Edmonds-Karp算法使用BFS来实现Ford-Fulkerson方法。
