# Data Structure - Graph

The concept of Graphs
Graph is a set of vertices connected by edges.
Edges can have weights, that is, each edge can be assigned either positive or negative.
Edges are divided into Directed Edge and Undirected Edge.
The degree of a vertex connects the number of edges of that vertex.

Graph representation For the figure above, there are two main representations:

The advantage of adjacency tables is that they save space and only store the actual edges.
The disadvantage is that when you focus on the degree of vertices, you may have to traverse a list of chains.
The implementation illustration is as follows: Java implementation code:
``````/**
* Adjacency Table Implementation of Directed Weighted Graph
*/

//vertex
private class Vertex {
char data;          //Name of vertex (value)
Node firstEdge;     //The first adjacent point of a vertex
}

private class Node {
int index;       //Represents the ordinal number of this Node in the vertex array
int weight;      //The weight of the vertex on the edge of this adjacent point
Node nextNode;   //Next Adjacent Point of Point
}

//edge
static class Edge {
char start;        //The vertex name (value) of the starting point
char end;          //The vertex name (value) of the focus
int weight;        //Edge weight

public Edge(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
}

private Vertex[] vertexNameList;    //Array of all vertex names

vertexNameList = new Vertex[vert.length];
parent = new int[vert.length];

for (int i = 0; i < vert.length; i++) {
vertexNameList[i] = new Vertex();
vertexNameList[i].data = vert[i];   //Vertex Name
vertexNameList[i].firstEdge = null; //No adjacent points, of course no side
}

//Initialize Edges
for (int i = 0; i < edge.length; i++) {
char start = edge[i].start;
char end = edge[i].end;

//Get the ordinal of the vertex
int startRank = getPosition(start);
int endRank = getPosition(end);

//1.endRank is the adjacent point of startRank, linking endRank to a list of chains headed with startRank
Node endRankNode = new Node();
endRankNode.index = endRank;
endRankNode.weight = edge[i].weight;
}
}

//A tail interpolation method that connects a vertex to the tail of a list of chains
private void linkedLast(int index, Node node) {
if(vertexNameList[index].firstEdge == null)
vertexNameList[index].firstEdge = node;
else{
Node tmp = vertexNameList[index].firstEdge;
while(tmp.nextNode != null){
tmp = tmp.nextNode;
}
tmp.nextNode = node;
}
}

//Gets the ordinal number of a vertex in an array
private int getPosition(char v) {
for (int i = 0; i < vertexNameList.length; i++) {
if(vertexNameList[i].data == v) return i;
}
//Returns -1 if no such vertex exists
return -1;
}

public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E'};   //vertex
Edge[] edges = {                           //edge
// Right of Start and End
new Edge('A', 'B', 5.6),
new Edge('A', 'C', 1.0),
new Edge('A', 'D', 4.2),
new Edge('B', 'C', 2.7),
new Edge('C', 'A',  1.0),
new Edge('C', 'B',  2.7),
new Edge('E', 'B',  -3.0)
};
}
``````
The advantage of adjacency matrix is that edges can be added and deleted quickly, and edges can be quickly determined between two points.
The disadvantage is that, for example, fewer edges between vertices wastes space because it is an n*n matrix.
The implementation illustration is as follows: Java implementation code:
``````/**
*/
public class MatrixGraph {

private char[] vertex;     //Set of vertex names

private int[][] edges;     //Adjacency matrix, storing edges

private int numOfEdges;     //Number of Edges

public MatrixGraph(int n){
edges = new int[n][n];
vertex = new char[n];
}

//Number of vertices
public int getNumOfVertexs(){
return vertex.length;
}

//Number of Edges
public int getNumOfEdges(){
return numOfEdges;
}

//Gets the weight from the vertex of ordinal v1 to the vertex of ordinal v2
public int getWeight(int v1,int v2){
return edges[v1][v2];
}

//Insert an edge
public void insertEdge(int v1,int v2,int weight){
edges[v1][v2] = weight;
numOfEdges++;
}

//Gets the subscript of the vertex array for the first adjacent point of a vertex subscript v
public int getFirstNeighbor(int v){
for (int i = 0; i < vertex.length; i++) {
if(edges[v][i] != 0)
return i;
}
return -1;
}

//Gets the next adjacent point of V1 from the previous adjacent point subscript v2 of vertex subscript v1
public int getNextNeighbor(int v1,int v2){
for (int i = v2+1; i < vertex.length; i++) {
if(edges[v1][i] != 0)
return i;
}
return -1;
}
}
``````

Traversal algorithm of graph (based on adjacency table)

1. Depth first traversal (DFS: Depth First Search)
The process of depth-first algorithm is simply to start from the starting point, find a deepest path, and then go back to the previous node and continue to find the deepest path (each node can only visit once).
Java implementation code:
``````    //Depth First Search (DFS) traversal graph starting from the first vertex
public void DFS(){
boolean[] visited = new boolean[vertexNameList.length];  //Whether the vertex has been traversed, defaulting to false
int[] path = new int[vertexNameList.length];             //The order in which the vertices appear during traversal, recording their subscripts in order
int index = 0;                                           //Index of path[]

/**
* MyStack:Represents the data structure - stack; FIFO
* Basic operation of stack:
* 1) push(Object o): Element stacking
* 2) Object pop(): Returns the top element of the stack and removes it from the stack.
* 3) Object peek(): Returns the top element of the stack without deleting it.
*/
MyStack stack = new MyStack(vertexNameList.length);

for (int i = 0; i < visited.length; i++)
{
//Use the stack's LIFO feature to find the deepest path first
stack.push(i);

if(!visited[i])
{
visited[i] = true;                                     //The vertex of subscript i is traversed
path[index++] = i;                                     //The first traversed vertex whose subscript is i

while(!stack.isEmpty())
{
int v = getUnVisitedVertex(stack.peek(),visited);
//If there are no adjacent points to visit, go out of the stack and go back
if(v == -1) stack.pop();
else
{
path[index++] = v;   //Access Contiguity Order
visited[v] = true;   //Adjacency point v has been visited
stack.push(v);       //Push
}

}
}
else
{
stack.pop();
}
}

//Print DFS Path
System.out.println("DFS Route:");
for (int i = 0; i < path.length; i++) {
System.out.print(vertexNameList[path[i]].data + " ");
}

}

//Returns the sequence number of an adjacent point whose vertex has not been visited
private int getUnVisitedVertex(Integer v, boolean[] visited) {
Node tmp = vertexNameList[v].firstEdge;

//If there is an adjacent point and the adjacent point has not been traversed, the adjacent point subscript is returned.
while(tmp != null){
if(!visited[tmp.index]) return tmp.index;
tmp = tmp.nextNode;
}
//There are no unreached adjacent points
return -1;
}
``````

Stack in and out stack order: 1. Width preferred traversal (BFS: Breadth First Search)
The breadth-first algorithm starts with the starting point, finds all the adjacent points of this point, and then, starting with its first adjacent point, continues to find the widest path (each node can only visit once).
Java implementation code:
``````    //Width first search, traverse from the first vertex
public void BFS(){
boolean[] visited = new boolean[vertexNameList.length];  //Whether the vertex has been traversed, defaulting to false
int[] path = new int[vertexNameList.length];             //The order in which the vertices appear during traversal, recording their subscripts in order
int index = 0;                                           //Index of path[]

/**
* MyQueue:Represents a data structure - a queue; FIFO
* Basic operation of queue:
* 1) enqueue(T t): Element Entry
* 2)  T dequeue(): The element queues and deletes it from the queue.
* 3)     T peek(): Returns the queue header element without deleting it.
*/
MyQueue<Integer> queue = new MyQueue<Integer>(vertexNameList.length);

for (int i = 0; i < visited.length; i++)
{
//Find the broadest route first using the first-in-first-out feature of the queue
queue.enqueue(i);

if(!visited[i])
{
visited[i] = true;                                     //The vertex of subscript i is traversed
path[index++] = i;                                     //The first traversed vertex whose subscript is i

while(!queue.isEmpty())
{
int v = getUnVisitedVertex(queue.peek(),visited);
//If no adjacent points are visited, queue
if(v == -1) queue.dequeue();
else
{
path[index++] = v;
visited[v] = true;
queue.enqueue(v);
}
}
}
else
{
queue.dequeue();
}

}

//Print BFS Path
System.out.println("BFS Route:");
for (int i = 0; i < path.length; i++) {
System.out.print(vertexNameList[path[i]].data + " ");
}
}
``````

Queue in and out queue order: Tags: Programming Java

Posted on Sun, 08 Sep 2019 09:49:43 -0700 by surfnjunkie