{"action":"opened","issue":{"url":"https://api.github.com/repos/bananabot1024/USACO/issues/9","repository_url":"https://api.github.com/repos/bananabot1024/USACO","labels_url":"https://api.github.com/repos/bananabot1024/USACO/issues/9/labels{/name}","comments_url":"https://api.github.com/repos/bananabot1024/USACO/issues/9/comments","events_url":"https://api.github.com/repos/bananabot1024/USACO/issues/9/events","html_url":"https://github.com/bananabot1024/USACO/issues/9","id":186107294,"number":9,"title":"Minimum Spanning Trees / Prim's - Week 8 Notes","user":{"login":"bananabot1024","id":9922999,"avatar_url":"https://avatars.githubusercontent.com/u/9922999?v=3","gravatar_id":"","url":"https://api.github.com/users/bananabot1024","html_url":"https://github.com/bananabot1024","followers_url":"https://api.github.com/users/bananabot1024/followers","following_url":"https://api.github.com/users/bananabot1024/following{/other_user}","gists_url":"https://api.github.com/users/bananabot1024/gists{/gist_id}","starred_url":"https://api.github.com/users/bananabot1024/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/bananabot1024/subscriptions","organizations_url":"https://api.github.com/users/bananabot1024/orgs","repos_url":"https://api.github.com/users/bananabot1024/repos","events_url":"https://api.github.com/users/bananabot1024/events{/privacy}","received_events_url":"https://api.github.com/users/bananabot1024/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2016-10-29T23:35:13Z","updated_at":"2016-10-29T23:35:13Z","closed_at":null,"body":"## Prim's Algorithm (Finding the Minimum Spanning Tree) O(N^2)\r\nAlgorithm: Pick a starting node, at each step pick the cheapest edge (smallest weight) and add the node to the current tree. Repeat for n-1 steps.\r\nKeep distances and visited array\r\n1) Initialize distances to infinity\r\nfor x in 1 to N: dist[x] = INF\r\n2) Set distance to root node to 0\r\ndist[start] = 0 // start can be any node\r\n3) Pick the minimum edge\r\nloop through all x from 1 to N and find minimum dist that's not visited\r\n4) Mark visited\r\nvisited[node] = true\r\n5) Update neighbors\r\nloop through neighbors of the node: dist[j] = min(dist[j], mat[x][j])"}}
{"actor":{"display_login":"bananabot1024"}}