算法入門篇十 圖

圖的存儲方式

  • 臨接表
  • 臨接矩陣

表達

  • 點集/邊集
  • 有向圖/無向圖

Graph（大結構就是圖）（包含點集合和邊集合）

import java.util.HashMap;
import java.util.HashSet;public class Graph {public HashMap<Integer, Node> nodes;//點集合public HashSet<Edge> edges;//邊集合public Graph() {nodes = new HashMap<>();edges = new HashSet<>();}
}

Node（點集合）?

import java.util.ArrayList;public class Node {public int value;//數值public int in;//入度public int out;//出度public ArrayList<Node> nexts;//從當前點出發，連接的數據點（出度連接的點）public ArrayList<Edge> edges;//從當前點出發，連接的邊（出度的邊）public Node(int value) {this.value = value;in = 0;out = 0;nexts = new ArrayList<>();edges = new ArrayList<>();}
}

Edge（邊集合）

 public class Edge {public int weight;//邊的權重public Node from;//有向邊public Node to;//有向邊public Edge(int weight, Node from, Node to) {this.weight = weight;this.from = from;this.to = to;}}

接口函數（將未知的題目類型轉化為我們所熟知的類型，如上圖所示）

public class GraphGenerator {// matrix 所有的邊// N*3 的矩陣// [weight, from節點上面的值，to節點上面的值]//example//【7，0，1】第一個代表from，第二個代表to，第三個代表weight//【6，1，2】//【4，2，0】public static Graph createGraph(Integer[][] matrix) {Graph graph = new Graph();for (int i = 0; i < matrix.length; i++) { // from：matrix[0][0], to：matrix[0][1]  權重（weight）：matrix[0][2]Integer from = matrix[i][0];Integer to = matrix[i][1];Integer weight = matrix[i][2];if (!graph.nodes.containsKey(from)) {//將未出現的from放入點集合graph.nodes.put(from, new Node(from));}if (!graph.nodes.containsKey(to)) {//將未出現的to放入點集合graph.nodes.put(to, new Node(to));}Node fromNode = graph.nodes.get(from);//獲取from點Node toNode = graph.nodes.get(to);//獲取to點Edge newEdge = new Edge(weight, fromNode, toNode);//創建邊fromNode.nexts.add(toNode);//from鄰居fromNode.out++;//出度++toNode.in++;//入度++fromNode.edges.add(newEdge);//將邊放到我所擁有的邊集合里面graph.edges.add(newEdge);//放入邊值}return graph;}}

圖的遍歷

寬度優先遍歷

代碼?

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;public class Code01_BFS {// 從node出發，進行寬度優先遍歷public static void bfs(Node node) {if (node == null) {return;}Queue<Node> queue = new LinkedList<>();HashSet<Node> set = new HashSet<>();//防止數據重復queue.add(node);set.add(node);while (!queue.isEmpty()) {Node cur = queue.poll();System.out.println(cur.value);for (Node next : cur.nexts) {if (!set.contains(next)) {set.add(next);queue.add(next);}}}}}

深度優先遍歷

代碼

import java.util.HashSet;
import java.util.Stack;public class Code02_DFS {public static void dfs(Node node) {if (node == null) {return;}Stack<Node> stack = new Stack<>();//保證深度的路徑HashSet<Node> set = new HashSet<>();stack.add(node);set.add(node);System.out.println(node.value);while (!stack.isEmpty()) {Node cur = stack.pop();for (Node next : cur.nexts) {if (!set.contains(next)) {stack.push(cur);stack.push(next);set.add(next);System.out.println(next.value);break;}}}}}

拓撲排序算法

  • 要求是有向圖，入度為0的節點，且沒有環

代碼

package class06;import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Code03_TopologySort {// directed graph and no looppublic static List<Node> sortedTopology(Graph graph) {// key：某一個node// value：剩余的入度HashMap<Node, Integer> inMap = new HashMap<>();// 入度為0的點，才能進這個隊列Queue<Node> zeroInQueue = new LinkedList<>();for (Node node : graph.nodes.values()) {inMap.put(node, node.in);if (node.in == 0) {zeroInQueue.add(node);}}// 拓撲排序的結果，依次加入resultList<Node> result = new ArrayList<>();while (!zeroInQueue.isEmpty()) {Node cur = zeroInQueue.poll();result.add(cur);for (Node next : cur.nexts) {inMap.put(next, inMap.get(next) - 1);if (inMap.get(next) == 0) {zeroInQueue.add(next);}}}return result;}
}

Kruskal算法（并查集）

無向圖

  • 加最小的邊，只要不形成環，就加上，否則不加入

代碼

package class06;import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.Stack;//undirected graph only
public class Code04_Kruskal {public static class MySets{public HashMap<Node, List<Node>>  setMap;public MySets(List<Node> nodes) {for(Node cur : nodes) {List<Node> set = new ArrayList<Node>();set.add(cur);setMap.put(cur, set);}}public boolean isSameSet(Node from, Node to) {//判斷from和to是否在一個集合List<Node> fromSet  = setMap.get(from);List<Node> toSet = setMap.get(to);return fromSet == toSet;//內存地址}public void union(Node from, Node to) {//List<Node> fromSet  = setMap.get(from);List<Node> toSet = setMap.get(to);for(Node toNode : toSet) {fromSet.add(toNode);setMap.put(toNode, fromSet);}}}// Union-Find Setpublic static class UnionFind {// key 某一個節點， value key節點往上的節點private HashMap<Node, Node> fatherMap;// key 某一個集合的代表節點, value key所在集合的節點個數private HashMap<Node, Integer> sizeMap;public UnionFind() {fatherMap = new HashMap<Node, Node>();sizeMap = new HashMap<Node, Integer>();}public void makeSets(Collection<Node> nodes) {fatherMap.clear();sizeMap.clear();for (Node node : nodes) {fatherMap.put(node, node);sizeMap.put(node, 1);}}private Node findFather(Node n) {Stack<Node> path = new Stack<>();while(n != fatherMap.get(n)) {path.add(n);n = fatherMap.get(n);}while(!path.isEmpty()) {fatherMap.put(path.pop(), n);}return n;}public boolean isSameSet(Node a, Node b) {return findFather(a) == findFather(b);}public void union(Node a, Node b) {if (a == null || b == null) {return;}Node aDai = findFather(a);Node bDai = findFather(b);if (aDai != bDai) {int aSetSize = sizeMap.get(aDai);int bSetSize = sizeMap.get(bDai);if (aSetSize <= bSetSize) {fatherMap.put(aDai, bDai);sizeMap.put(bDai, aSetSize + bSetSize);sizeMap.remove(aDai);} else {fatherMap.put(bDai, aDai);sizeMap.put(aDai, aSetSize + bSetSize);sizeMap.remove(bDai);}}}}public static class EdgeComparator implements Comparator<Edge> {@Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}}public static Set<Edge> kruskalMST(Graph graph) {UnionFind unionFind = new UnionFind();unionFind.makeSets(graph.nodes.values());PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());for (Edge edge : graph.edges) { // M 條邊priorityQueue.add(edge);  // O(logM)}Set<Edge> result = new HashSet<>();while (!priorityQueue.isEmpty()) { // M 條邊Edge edge = priorityQueue.poll(); // O(logM)if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)result.add(edge);unionFind.union(edge.from, edge.to);}}return result;}
}

prim算法

無向圖

代碼

package class06;import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;// undirected graph only
public class Code05_Prim {public static class EdgeComparator implements Comparator<Edge> {@Overridepublic int compare(Edge o1, Edge o2) {return o1.weight - o2.weight;}}public static Set<Edge> primMST(Graph graph) {// 解鎖的邊進入小根堆PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new EdgeComparator());HashSet<Node> set = new HashSet<>();Set<Edge> result = new HashSet<>(); // 依次挑選的的邊在result里for (Node node : graph.nodes.values()) { // 隨便挑了一個點// node 是開始點if (!set.contains(node)) {set.add(node);for (Edge edge : node.edges) { // 由一個點，解鎖所有相連的邊priorityQueue.add(edge);}while (!priorityQueue.isEmpty()) {Edge edge = priorityQueue.poll(); // 彈出解鎖的邊中，最小的邊Node toNode = edge.to; // 可能的一個新的點if (!set.contains(toNode)) { // 不含有的時候，就是新的點set.add(toNode);result.add(edge);for (Edge nextEdge : toNode.edges) {priorityQueue.add(nextEdge);}}}}//break;}return result;}// 請保證graph是連通圖// graph[i][j]表示點i到點j的距離，如果是系統最大值代表無路// 返回值是最小連通圖的路徑之和public static int prim(int[][] graph) {int size = graph.length;int[] distances = new int[size];boolean[] visit = new boolean[size];visit[0] = true;for (int i = 0; i < size; i++) {distances[i] = graph[0][i];}int sum = 0;for (int i = 1; i < size; i++) {int minPath = Integer.MAX_VALUE;int minIndex = -1;for (int j = 0; j < size; j++) {if (!visit[j] && distances[j] < minPath) {minPath = distances[j];minIndex = j;}}if (minIndex == -1) {return sum;}visit[minIndex] = true;sum += minPath;for (int j = 0; j < size; j++) {if (!visit[j] && distances[j] > graph[minIndex][j]) {distances[j] = graph[minIndex][j];}}}return sum;}public static void main(String[] args) {System.out.println("hello world!");}}

?Dijkstra算法（單元最遠路徑算法）

  • 要求沒有權值為負的邊

代碼

package class06;import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;// no negative weight
public class Code06_Dijkstra {public static HashMap<Node, Integer> dijkstra1(Node head) {// 從head出發到所有點的最小距離// key : 從head出發到達key// value : 從head出發到達key的最小距離// 如果在表中，沒有T的記錄，含義是從head出發到T這個點的距離為正無窮HashMap<Node, Integer> distanceMap = new HashMap<>();distanceMap.put(head, 0);// 已經求過距離的節點，存在selectedNodes中，以后再也不碰HashSet<Node> selectedNodes = new HashSet<>();Node minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);while (minNode != null) {int distance = distanceMap.get(minNode);for (Edge edge : minNode.edges) {Node toNode = edge.to;if (!distanceMap.containsKey(toNode)) {distanceMap.put(toNode, distance + edge.weight);} else {distanceMap.put(edge.to, Math.min(distanceMap.get(toNode), distance + edge.weight));}}selectedNodes.add(minNode);minNode = getMinDistanceAndUnselectedNode(distanceMap, selectedNodes);}return distanceMap;}public static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes) {Node minNode = null;int minDistance = Integer.MAX_VALUE;for (Entry<Node, Integer> entry : distanceMap.entrySet()) {Node node = entry.getKey();int distance = entry.getValue();if (!touchedNodes.contains(node) && distance < minDistance) {minNode = node;minDistance = distance;}}return minNode;}public static class NodeRecord {public Node node;public int distance;public NodeRecord(Node node, int distance) {this.node = node;this.distance = distance;}}public static class NodeHeap {private Node[] nodes; // 實際的堆結構// key 某一個node， value 上面數組中的位置private HashMap<Node, Integer> heapIndexMap;// key 某一個節點， value 從源節點出發到該節點的目前最小距離private HashMap<Node, Integer> distanceMap;private int size; // 堆上有多少個點public NodeHeap(int size) {nodes = new Node[size];heapIndexMap = new HashMap<>();distanceMap = new HashMap<>();size = 0;}public boolean isEmpty() {return size == 0;}// 有一個點叫node，現在發現了一個從源節點出發到達node的距離為distance// 判斷要不要更新，如果需要的話，就更新public void addOrUpdateOrIgnore(Node node, int distance) {if (inHeap(node)) {distanceMap.put(node, Math.min(distanceMap.get(node), distance));insertHeapify(node, heapIndexMap.get(node));}if (!isEntered(node)) {nodes[size] = node;heapIndexMap.put(node, size);distanceMap.put(node, distance);insertHeapify(node, size++);}}public NodeRecord pop() {NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));swap(0, size - 1);heapIndexMap.put(nodes[size - 1], -1);distanceMap.remove(nodes[size - 1]);// free C++同學還要把原本堆頂節點析構，對java同學不必nodes[size - 1] = null;heapify(0, --size);return nodeRecord;}private void insertHeapify(Node node, int index) {while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {swap(index, (index - 1) / 2);index = (index - 1) / 2;}}private void heapify(int index, int size) {int left = index * 2 + 1;while (left < size) {int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])? left + 1: left;smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;if (smallest == index) {break;}swap(smallest, index);index = smallest;left = index * 2 + 1;}}private boolean isEntered(Node node) {return heapIndexMap.containsKey(node);}private boolean inHeap(Node node) {return isEntered(node) && heapIndexMap.get(node) != -1;}private void swap(int index1, int index2) {heapIndexMap.put(nodes[index1], index2);heapIndexMap.put(nodes[index2], index1);Node tmp = nodes[index1];nodes[index1] = nodes[index2];nodes[index2] = tmp;}}// 改進后的dijkstra算法// 從head出發，所有head能到達的節點，生成到達每個節點的最小路徑記錄并返回public static HashMap<Node, Integer> dijkstra2(Node head, int size) {NodeHeap nodeHeap = new NodeHeap(size);nodeHeap.addOrUpdateOrIgnore(head, 0);HashMap<Node, Integer> result = new HashMap<>();while (!nodeHeap.isEmpty()) {NodeRecord record = nodeHeap.pop();Node cur = record.node;int distance = record.distance;for (Edge edge : cur.edges) {nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);}result.put(cur, distance);}return result;}}

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/447202.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/447202.shtml
英文地址，請注明出處：http://en.pswp.cn/news/447202.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

SDP協議 學習筆記

SDP協議 學習筆記

SDP:Session Description ProtocolSDP格式:Session descriptionv (protocolversion)o (owner/creatorand session identifier)s (sessionname)i* (sessioninformation)u* (URI ofdescription)e* (emailaddress)p* (phonenumber)c*(connection information - not required if in…
閱讀更多...
以太坊私有鏈 使用dev模式

以太坊私有鏈 使用dev模式

dev 使用dev模式&#xff0c;創建一個管理員賬號&#xff0c;控制挖礦&#xff0c;將證明機制改為POA啟動dev模式&#xff0c;需要重新創建一個文件夾&#xff0c;重新搭建私有鏈條 命令 mkdir myDevChain cd myDevChain geth --datadir . --dev console 2>output.log 實…
閱讀更多...
超文本傳輸協議

超文本傳輸協議

超文本傳輸協議 超文本傳輸協議超文件傳輸協定(HTTP&#xff0c;HyperTextTransfer Protocol)是因特網上應用最為廣泛的一種網絡傳輸協定。所有的WWW文件都必須遵守這個標準。設計HTTP最初的目的是為了提供一種發布和接收HTML頁面的方法。 目錄 介紹請求信息請求方法安全方法超…
閱讀更多...
以太坊區塊鏈 JSON-RPC

以太坊區塊鏈 JSON-RPC

RPC定義 以太坊客戶端提供了API和一組遠程調用的&#xff08;RPC&#xff09;命令&#xff0c;這些命令被編碼成json的格式&#xff0c;被叫做JSON-RPC-API。本質上&#xff0c;JSON-RPC API就是一個接口&#xff0c;允許我們編寫的程序使用以太坊客戶端作為網關&#xff0c;訪…
閱讀更多...
利用MFC調用libvlc.dll作一個簡單的播放器

利用MFC調用libvlc.dll作一個簡單的播放器

簡單介紹MFC調用libvlc.dll作一個簡單的播放器&#xff0c;拋磚引玉&#xff0c;各位VC達人繼續深入研究&#xff0c;Jeremiah對VC確實不太感興趣&#xff0c;所以就不做太深入的研究了。2009.10.29修改&#xff1a;加入clip_children屬性設置。參開第1步。環境&#xff1a; …
閱讀更多...
對于以太坊虛擬機 （EVM）及其相關知識的講解

對于以太坊虛擬機 （EVM）及其相關知識的講解

以太坊虛擬機&#xff08;EVM&#xff09; EVM是智能合約的運行環境作為區塊驗證協議的一部分&#xff0c;參與網絡的每個節點都會運行EVM&#xff0c;審查節點會檢查驗證正在驗證的區塊中列出的交易&#xff0c;并運行EVM中交易觸發的代碼EVM是沙盒封裝的&#xff0c;并且是完…
閱讀更多...
對于以太坊的Solidity語言介紹

對于以太坊的Solidity語言介紹

Solidity是什么 Solidity是一門面向合約的、為實現智能合約而創建的高級編程語言&#xff0c;主要目的是為了在以太坊虛擬機&#xff08;EVM&#xff09;上運行Solidity是靜態語言&#xff0c;支持繼承、庫和復雜的用戶定義等特性內含的類型除了常見的編程語言中的標準類型&am…
閱讀更多...
live555 接收rtsp視頻流流程分析

live555 接收rtsp視頻流流程分析

live555 接收rtsp視頻流流程分析 RTSP交互流程 C表示RTSP客戶端&#xff0c;S表示RTSP服務端 ① C->S: OPTIONrequest //詢問S有哪些方法可用 S->C: OPTION response //S回應信息中包括提供的所有可用方法 ② C->S: DESCRIBErequest //要求得到S…
閱讀更多...
使用Remix編寫Solidity語言的小例子

使用Remix編寫Solidity語言的小例子

設置數值/取數值/加法運算 講解 uint默認使用256位數的整型view表示這個函數僅僅對于數據僅僅是讀取&#xff0c;沒有修改操作returns(uint )&#xff0c;如果單純指定uint&#xff0c;返回的是函數體內的return值&#xff0c;如果包含uint sum,uint SAD_a&#xff0c;那么返…
閱讀更多...
RTP協議棧簡介

RTP協議棧簡介

流媒體指的是在網絡中使用流技術傳輸的連續時基媒體&#xff0c;其特點是在播放前不需要下載整個文件&#xff0c;而是采用邊下載邊播放的方式&#xff0c;它是視頻會議、IP電話等應用場合的技術基礎。RTP是進行實時流媒體傳輸的標準協議和關鍵技術&#xff0c;本文介紹如何在L…
閱讀更多...
深入理解Solidity

深入理解Solidity

Solidity源文件布局 pragma&#xff08;版本雜注&#xff09; 用于指定源文件的版本&#xff0c;表明編譯器的版本&#xff0c;例如 pragma solidity ^0.4.0^用于指代版本號需要大于0.4.0但是不可以超過大的層級&#xff0c;必須小于0.5.0也可以使用大于等于小于來指定版本 i…
閱讀更多...
H264 流媒體 編碼匯總

H264 流媒體 編碼匯總

實時傳輸協議&#xff08;RTP&#xff09;和實時控制協議&#xff08;RTCP&#xff09; RTP是一種提供端對端傳輸服務的實時傳輸協議&#xff0c;用來支持在單目標廣播和多目標廣播網絡服務中傳輸實時數據&#xff0c;而實時數據的傳輸則由RTCP協議來監視和控制。 RTP定義在RFC…
閱讀更多...
使用多線程的方式調用chineseocr_API

使用多線程的方式調用chineseocr_API

ChineseOCR在線API 網頁鏈接 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別代碼 import glob import base64 import os import requests import …
閱讀更多...
開源好代碼 音視頻

開源好代碼 音視頻

VirtualDub 一、簡介 圖1VirtualDub主界面 VirtualDub是一款開源的音視頻捕獲、處理軟件。VirtualDub也可稱為一款多媒體編輯軟件&#xff0c;因為它包含了多媒體輸入、編輯、處理、輸出等各個環節&#xff0c;但是作者并未將它定位為一款多媒體編輯軟件&#xff08;參見官網&a…
閱讀更多...
MAC對于Excel表格換行操作

MAC對于Excel表格換行操作

按住option之后&#xff0c;點擊Enter就可以完成換行操作
閱讀更多...
深入理解Solidity 二

深入理解Solidity 二

Solidity數據位置 所有復雜的數據類型&#xff0c;即數組、結構和映射類型&#xff0c;都會有一個額外屬性“數據位置”&#xff0c;用來指定數據的存儲位置&#xff0c;即數據是存儲在memory還是存儲在storage里面根據上下文環境&#xff0c;IDE會自動指定數據的默認存儲位置…
閱讀更多...
VOIP簡介

VOIP簡介

一、什么是VOIP VOIP全稱為&#xff08;VoiceOver Internet Protocol&#xff09;&#xff0c;是一種利用Internet網絡進行語音通信的技術&#xff0c;更通俗一點說&#xff0c;就是IP電話。就是以IP分組交換網為傳輸平臺&#xff0c;對模擬的語音信號進行編碼壓縮&#xff0c…
閱讀更多...
深入理解Solidity 三

深入理解Solidity 三

Solidity函數聲明和類型 函數的值類型有兩類&#xff1a;內部&#xff08;internal&#xff09;類型和外部&#xff08;external&#xff09;類型內部函數只可以在當前合約內部被調用&#xff08;即在當前代碼塊內&#xff0c;包括內部庫函數和繼承函數&#xff09;&#xff0c…
閱讀更多...
HTTP狀態代碼及其定義

HTTP狀態代碼及其定義

狀態行包含HTTP版本、狀態代碼、與狀態代碼對應的簡短說明信息。在大多數情況下&#xff0c;除了Content-Type之外的所有應答頭都是可選的。但Content-Type是必需的&#xff0c;它描述的是后面文檔的MIME類型。雖然大多數應答都包含一個文檔&#xff0c;但也有一些不包含&#…
閱讀更多...
安裝solc模塊4.25版本

安裝solc模塊4.25版本

使用國產阿里云的cnpm 如果不知道cnpm 參考鏈接 安裝solc模塊4.25版本 npm i solc0.4.25 --save -g查看安裝是否成功 可以配置軟連接使用solc&#xff0c;我的沒有配置 solcjs --version
閱讀更多...
最新文章

Copyright @ 2022~2023