Graph
An implementation of the Graph data structure in java
Implementation
The graph data structure is typically implemented using an Adjacency-List or and Adjacency-Matrix.
Adjacency-Matrix: an adjacency-matrix uses a 2d array of 1s and 0s (called weights) to represent the connections between nodes. A 0 means there is no connection, and a 1 means there is a connection.
Note: weights may be greater than 1
Adjacency-List: an adjacency-list stores each node as a linked list. Meanwhile, the Linked List of every node contains a link to all of its neighbors.
Terminology:
adjacent: vertices that share an edge (connected)
undirected graph: (a,b) is the same as (b,a)
directed graph: (a,b) is not the same as (b,a)
connected graph: a graph where a path exists between every pair of vertices
complete graph: a graph where an edge exists from every vertex to all of the other vertices.
Algorithms associated with the Graph data structure
1. Breadth First Search (BFS)
2. Depth First Search (DFS)
3. Shortest Path from source to all vertices **Dijkstra**
4. Shortest Path from every vertex to every other vertex **Floyd Warshall**
5. To detect cycle in a Graph **Union Find**
6. Minimum Spanning tree **Prim**
7. Minimum Spanning tree **Kruskal**
8. Topological Sort
9. Boggle (Find all possible words in a board of characters)
10. Bridges in a Graph
Sources
support.csis.pace.edu/CSISWeb/docs/techReports/techReport224.pdf
http://www1.cs.columbia.edu/~bert/courses/3134/slides/Lecture16%20(examples%20cut).pdf
http://www.wou.edu/~jcm/WebPageSpring2014/Postings/GraphADTIntro.pdf
http://www.java2blog.com/2015/12/depth-first-search-in-java.html
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Graph/bfs.html
