Graph algorithms
From Algorithm wiki
[edit] Graph algorithms list
- Bellman-Ford algorithm:computes shortest path problem in a weighted graph (where some of the edge weights may be negative)
- Kruskal's algorithm: finds a minimum spanning tree for a graph
- Prim's algorithm: finds a minimum spanning tree for a graph
- Dijkstra's algorithm: computes shortest path problem in a graph with non-negative edge weights
- Floyd-Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph
- Breadth-first search
- Creation of trees
- Depth-First Search
- Greedy tour of a Euclidean graph
- Huffman Tree
- K-entry Node Search
- Topological sort
- Eight queens puzzle
- travelling salesman problem
- Perturbation methods: an algorithm that computes a locally shortest paths in a graph
- Johnson algorithm: All pairs shortest path algorithm in sparse weighted directed graph
- Boruvka's algorithm: finds a minimum spanning tree for a graph
- Ford-Fulkerson algorithm: computes the maximum flow in a graph
- Edmonds-Karp algorithm: implementation of Ford-Fulkerson
- Nonblocking Minimal Spanning Switch say, for a telephone exchange
- Woodhouse-Sharp algorithm: finds a minimum spanning tree for a graph
- Spring based algorithm: algorithm for graph drawing
- Topological sort: finds linear order of nodes(e.g. jobs) based on their dependencies.
- Hungarian algorithm: algorithm for finding a perfect matching
- Coloring algorithm: Graph coloring algorithm.
- Nearest neighbour algorithm.
[edit] Computer Graphics
- Bezier curve for n-points
- Bezier Curves Algorithm
- Bresenham Circle algorithm
- Drawing a polygon
- Nearest-neighbour tour
- contour plotting algorithm
- Bresenham's line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses decision variables)
- Line drawing algorithm: graphical algorithm for approximating a line segment on discrete graphical media.
- * DDA line algorithm: plots points of a 2-dimensional array to form a straight line between 2 specified points (uses floating-point math)
- Flood fill: fills a connected region of a multi-dimensional array with a specified symbol
- Xiaolin Wu's line algorithm: algorithm for line antialiasing.
- Painter's algorithm: detects visible parts of a 3-dimensional scenery
- Ray tracing: realistic image rendering
- Phong shading: an illumination model and an interpolation method in 3D computer graphics
- Gouraud shading: an algorithm to simulate the differing effects of light and colour across the surface of an object in 3D computer graphics
- Scanline rendering: constructs an image by moving an imaginary line over the image
- Global illumination algorithms: Considers direct illumination and reflection from other objects.
- Interpolation: Constructing new data points such as in digital zoom.
- Spline interpolation: Reduces error with Runge's phenomenon.
