当前位置: 首页> 科技> 名企 > 网店运营包括哪些_多媒体展厅设计制作公司_排名优化价格_移动营销

网店运营包括哪些_多媒体展厅设计制作公司_排名优化价格_移动营销

时间:2025/7/11 0:44:50来源:https://blog.csdn.net/Triple_3/article/details/144969459 浏览次数:0次
网店运营包括哪些_多媒体展厅设计制作公司_排名优化价格_移动营销

拓扑排序精讲

题目讲解:代码随想录
重点:

  1. 给出一个有向图,把这个有向图转成线性的排序就叫拓扑排序。
  2. 拓扑排序也是图论中判断有向无环图的常用方法。
  3. 拓扑排序的过程,其实就两步:
    · 找到入度为0的节点,加入结果集。
    · 将该节点从图中移除(也就是减少影响的inDegree数组)。

思路:

  1. 把最开始入度为0的点推入队列, 作为拓扑排序的入口
Deque<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {if (inDegree[i] == 0) queue.offer(i);
}
  1. 遍历队列,把当前入度为0的节点加进result,然后更新inDegree数组。如果更新之后该节点也为0, 则推入队列。
while (!queue.isEmpty()) {int cur = queue.poll();result.add(cur);LinkedList<Integer> files = umap.get(cur);if (!files.isEmpty()) {for (Integer file : files) {inDegree[file]--;if (inDegree[file] == 0) queue.offer(file);}}
}
public class SoftwareConstruction {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// 初始化入度数组, 邻接表int[] inDegree = new int[n];List<LinkedList<Integer>> umap = new ArrayList<>(n);for (int i = 0; i < n; i++) umap.add(new LinkedList<>());for (int i = 0; i < m; i++) {int s = scanner.nextInt();int t = scanner.nextInt();inDegree[t]++;umap.get(s).add(t);}// 把最开始入度为0的点推入队列, 作为拓扑排序的入口Deque<Integer> queue = new LinkedList<>();for (int i = 0; i < n; i++) {if (inDegree[i] == 0) queue.offer(i);}List<Integer> result = new ArrayList<>();// 遍历队列, 把当前入度为0的节点加进result, 然后更新inDegree数组// 如果更新之后该节点也为0, 则推入队列while (!queue.isEmpty()) {int cur = queue.poll();result.add(cur);LinkedList<Integer> files = umap.get(cur);if (!files.isEmpty()) {for (Integer file : files) {inDegree[file]--;if (inDegree[file] == 0) queue.offer(file);}}}// 输出结果if (result.size() == n) {for (int i = 0; i < n - 1; i++) {System.out.print(result.get(i) + " ");}System.out.println(result.get(n - 1));} else {System.out.println(-1);}}
}

Dijkstra(朴素版)精讲

题目讲解:代码随想录
重点:

  1. Dijkstra三部曲:
    选源点到哪个节点近且该节点未被访问过
    该最近节点被标记访问过
    更新非访问节点到源点的距离(即更新minDist数组)
  2. 在有权图权值非负数中求从起点到其他节点的最短路径算法。
  3. prim和dijkstra很像,但是prim可以求有负数的有权图,因为prim只求最小生成树,求的不是路径。

思路:

  1. 初始化minDist, visited和parent
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
boolean[] visited = new boolean[n + 1];
int[] parent = new int[n + 1];
Arrays.fill(parent, -1);
  1. 根据minDist选距离源点最近的节点
for (int v = 1; v <= n; v++) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}
}
  1. 标记当前节点已访问
visited[cur] = true;
  1. 更新与当前节点相连的非访问节点的minDist和parent数组
for (int v = 1; v <= n; v++) {if (!visited[v] && graph[cur][v] != Integer.MAX_VALUE && minDist[cur] + graph[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + graph[cur][v];parent[v] = cur;}
}
public class AttendScienceConference {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] graph = new int[n + 1][n + 1];;for (int i = 0; i < n + 1; i++) {Arrays.fill(graph[i], Integer.MAX_VALUE);}for (int i = 0; i < m; i++) {int s = scanner.nextInt();int e = scanner.nextInt();int v = scanner.nextInt();graph[s][e] = v;}int start = 1;int end = n;// 初始化minDist, visited和parentint[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;boolean[] visited = new boolean[n + 1];int[] parent = new int[n + 1];Arrays.fill(parent, -1);// 最多遍历所有节点就可以获取到所有的最短路径for (int i = 1; i <= n; i++) {int minVal = Integer.MAX_VALUE;int cur = start;// 1. 根据minDist选距离源点最近的节点for (int v = 1; v <= n; v++) {if (!visited[v] && minDist[v] < minVal) {minVal = minDist[v];cur = v;}}// 2. 标记当前节点已访问visited[cur] = true;// 3. 更新与当前节点相连的非访问节点的minDist和parent数组for (int v = 1; v <= n; v++) {if (!visited[v] && graph[cur][v] != Integer.MAX_VALUE && minDist[cur] + graph[cur][v] < minDist[v]) {minDist[v] = minDist[cur] + graph[cur][v];parent[v] = cur;}}}// 输出结果if (minDist[end] == Integer.MAX_VALUE) System.out.println(-1);else System.out.println(minDist[end]);for (int i = 1; i <= n; i++) {System.out.println(parent[i] + "->" + i);}}
}

Dijkstra(堆优化版)精讲

题目讲解:代码随想录
重点:

  1. 稀疏图求最短路径用邻接表存储图,用优先队列取距源点最近的点。

思路:

  1. 初始化minDist, visited和PriorityQueue
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
boolean[] visited = new boolean[n + 1];
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.add(new Pair(start, 0));
  1. 选距离源点最近的节点(通过优先级队列来实现
Pair cur = pq.poll();
  1. 标记当前节点已访问
visited[cur.node] = true;
  1. 更新与当前节点相连的非访问节点的minDist并推入PriorityQueue
for (Edge edge : graph.get(cur.node)) {if (!visited[edge.to] && minDist[cur.node] + edge.val < minDist[edge.to]) {minDist[edge.to] = minDist[cur.node] + edge.val;pq.add(new Pair(edge.to, minDist[edge.to]));}
}
// 边的类
class Edge {int to;int val;Edge(int to, int val) {this.to = to;this.val = val;}
}
// PriorityQueue中存放的Pair
class Pair implements Comparable<Pair>{int node;int minDistVal;Pair(int node, int minDistVal) {this.node = node;this.minDistVal = minDistVal;}@Overridepublic int compareTo(Pair o) {return Integer.compare(this.minDistVal, o.minDistVal);}
}
public class AttendScienceConferenceHeap {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();// 背景是稀疏图, 所以用邻接表比较好, 链表存储的是Edge对象List<LinkedList<Edge>> graph = new ArrayList<>(n + 1);for (int i = 0; i < n + 1; i++) {graph.add(new LinkedList<>());}for (int i = 0; i < m; i++) {int s = scanner.nextInt();int e = scanner.nextInt();int v = scanner.nextInt();graph.get(s).add(new Edge(e, v));}int start = 1;int end = n;// 初始化minDist, visited和PriorityQueueint[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] = 0;boolean[] visited = new boolean[n + 1];PriorityQueue<Pair> pq = new PriorityQueue<>();pq.add(new Pair(start, 0));// 遍历PriorityQueuewhile (!pq.isEmpty()) {// 1. 选距离源点最近的节点(通过优先级队列来实现)Pair cur = pq.poll();if (visited[cur.node]) continue;// 2. 标记当前节点已访问visited[cur.node] = true;// 3. 更新与当前节点相连的非访问节点的minDist并推入PriorityQueuefor (Edge edge : graph.get(cur.node)) {if (!visited[edge.to] && minDist[cur.node] + edge.val < minDist[edge.to]) {minDist[edge.to] = minDist[cur.node] + edge.val;pq.add(new Pair(edge.to, minDist[edge.to]));}}}// 输出结果if (minDist[end] == Integer.MAX_VALUE) System.out.println(-1);else System.out.println(minDist[end]);}
}
关键字:网店运营包括哪些_多媒体展厅设计制作公司_排名优化价格_移动营销

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: