Created
October 24, 2016 18:56
-
-
Save mding5692/567f353d86de1662732034b482190f4b to your computer and use it in GitHub Desktop.
3 Graph representations - Object/Pointer, Adjacency List, Adjacency Matrix
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Uses Node class like below | |
/*Node(int val) { | |
Node next; | |
int val = val; | |
}*/ | |
public HashMap<Integer,Node<Integer>> adjList(Pair pairArr) { | |
if (pairArr.length == 0) { | |
return null; | |
} | |
HashMap<Integer,Node<Integer>> nodeMap = new HashMap<Integer,Node<Integer>>(); | |
for (Pair p : pairArr) { | |
if (!nodeMap.containsKey(p.firstInt)) { | |
Node firstNode = new Node(p.secondInt); | |
nodeMap.put(p.firstInt, firstNode); | |
} else { | |
Node currNode = nodeMap.get(p.firstInt); | |
Node newNode = new Node(p.secondInt); | |
newNode.next = currNode; | |
nodeMap.put(p.firstInt,newNode); | |
} | |
} | |
return nodeMap; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public int[][] adjMatrix(Pair pairArr, boolean directed) { | |
if (pairArr.length == 0) { | |
return null; | |
} | |
int connected = 1; | |
int[][] adjMatrix = new int[pairArr.length][pairArr.length]; | |
// has to make sure if directed or undirected just in case it ignores edges in undirected case | |
if (directed == true) { | |
for (Pair p : pairArr) { | |
int[p.firstInt][p.secondInt] = connected; | |
} | |
} else { // in the case its undirected and doesn’t write in pairArr both connected cases | |
for (Pair p: pairArr) { | |
int[p.firstInt][p.secondInt] = connected; | |
int[p.secondInt][p.firstInt] = connected; | |
} | |
} | |
return adjMatrix; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Uses Node class like below | |
Node(int val) { | |
List<Node> neighbours; | |
Int val = val; | |
} | |
// Didn’t want to do this similarly to my adjacency list hashtable implementation so | |
// tried to go through pairArr and add newNode whenever hit a similar firstInt | |
public ArrayList<Node> objPointer(Pair[] pairArr) { | |
if (pairArr.length == 0) { | |
return null; | |
} | |
ArrayList<Node> nodeList = new ArrayList<Node>(); | |
for (int i = 0; i < pairArr.length; i++) { | |
int checkInt = pairArr[i].firstInt; | |
Node newNode = new Node(checkInt) | |
for (Pair p: pairArr) { | |
if (checkInt == p.firstInt) { | |
Node connectedNode = new Node(p.secondInt); | |
newNode.neighbours.add(connectedNode); | |
} | |
} | |
nodeList.add(newNode); | |
} | |
return nodeList; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment