数据结构——图的应用：最短路径、拓扑排序、关键路径
的遍历之后图的高级应用是 408 考研的重点大题。一、最短路径Dijkstra 算法单源最短路径不能处理负权边。publicint[]dijkstra(int[][]graph,intstart){intngraph.length;int[]distnewint[n];boolean[]visitednewboolean[n];Arrays.fill(dist,Integer.MAX_VALUE);dist[start]0;for(inti0;in-1;i){intu-1;for(intj0;jn;j)if(!visited[j](u-1||dist[j]dist[u]))uj;visited[u]true;for(intv0;vn;v)if(!visited[v]graph[u][v]!0dist[u]graph[u][v]dist[v])dist[v]dist[u]graph[u][v];}returndist;}二、拓扑排序publicint[]topologicalSort(ListInteger[]adj){intnadj.length;int[]inDegreenewint[n];for(inti0;in;i)for(intv:adj[i])inDegree[v];QueueIntegerqueuenewLinkedList();for(inti0;in;i)if(inDegree[i]0)queue.offer(i);int[]resultnewint[n];intidx0;while(!queue.isEmpty()){intuqueue.poll();result[idx]u;for(intv:adj[u])if(--inDegree[v]0)queue.offer(v);}returnresult;} 觉得有用的话点赞 关注【张老师技术栈】吧
