module Graphs where
import Numeric
Copyright By PowCoder代写 加微信 powcoder
— We assume that the vertices are numbered 0 … n-1
{- In and adjacency list al, the i-th element al!!i
is a list of all the vertices j such that
there is an edge from i to j
type AdjList = [[Int]]
{- In and adjacencly matrix am, the element with
coordinates i,j, that is am!!i!!j
is True if there is an edge from i to j
False if there is no edge from i to j
type AdjMatrix = [[Bool]]
— Suppose we’re given a graph as a list of edges (i,j)
— Generate the Adjacency List and Adjacencty Matrix representations
— GENERATION OF ADJACENCY LIST
adjList :: [(Int,Int)] -> AdjList
— GENERATION OF ADJACENCY MATRIX
adjMatrix :: [(Int,Int)] -> AdjMatrix
——————————————————–
— WEIGHTED GRAPHS: every edge has a “weight”
{- In an adjacency list al, the i-th element al!!i
contains all the pairs (j,w) such that
there is an edge from i to j with weight w
type WAdjList = [[(Int,Float)]]
{- In an adjacency matrix am, the element with
coordinates i,j is
Nothing if there is no edge from i to j
(Just w) if there is an edge from i to j with weight w
type WAdjMatrix = [[Maybe Float]]
{- We can also represent a weighted graphs by a list of edges
(i,j,w) denotes an edge from i to j with weight w
type Edges = [(Int,Int,Float)]
— GENERATION OF ADJACENCY LIST
— from a list of edges
adjListW :: Edges -> WAdjList
— GENERATION OF ADJACENCY MATRIX
— from a list of edges
adjMatrixW :: Edges -> WAdjMatrix
— DIJKSTRA’S ALGORITHM
Given an adjacencly list al and a source vertex s
return the list of minimum distances of vertices from s:
(dijkstra al s)!!j is the minimum distance from s to j
dijkstra :: WAdjList -> Int -> [Maybe Float]
— FLOYD-WARSHALL ALGORITHM
Given an adjacency matrix am, return the matrix of minimum distances:
(floydWarshall am)!!i!!j is
Nothing if there is no path from i to j
(Just x) if the shortest path from i to j has length x
floydWarshall :: WAdjMatrix -> WAdjMatrix
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com