# Graphs

* **Vertices**&#x20;
* **Edges**
  * Directed edges: source, destination
  * Undirected edges
    * adjacent nodes
    * degree: 連結的node數
    * path
    * cycle
    * forest- a disjoint set of trees

## 1.Types

### Adjacency matrix

```
class Graph {
    int [][] adjacencyMatrix;
    int numVertices;
}

public class AdjacencyMatrixGraph implements Graph {
    private int [][] adjacencyMatrix;
    private GraphType graphType = GraphType.DIRECTED;
    private int numVertices = 0; 
    public  AdjacencyMatrixGraph(int numVertices, GraphType graphType) {
        this.numVertices = numVertices;
        this.graphType = graphType;
        
        adjacencyMatrix = new int[numVertices][numVertices];
        
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                adjacencyMatrix[i][j] = 0;
            }
        }
    }
    
    public void addEdge(int v1, int v2) {
        if (v1 >= numVertices || V1 < 0 || v2 >= numVertices || v2 < 0) {
            throw new IllegalArgumentException("Vertex number is not valid");
        }
        
        adjacencyMatrix[v1][v2] = 1;
        if (graphType == GraphType.UNDIRECTED) {
             adjacencyMatrix[v2][v1] = 1;
        }
    }
    
    public List<Integar> getAdjacentVertices(int v) {
        if (v >= numVertices || v < 0) {
            throw new IllegalArgumentException("Vertex number is not valid");
        }
        
        List<Integar> adjacencyVerticesList = new ArrayList<>();
        for (int i = 0; i < numVertices; i++) {
            if (adjacencyMatrix[v][i] == 1) {
                adjacencyVerticesList.add(i);
            }
        }
        
        Collections.sort(adjacencyVerticesList);
        
        return adjacencyVerticesList;
    }
}
```

### Adjacency list

* Each vertex has a pointer to a linked list
* Downside: The same graph can have multiple representations

```
class Node {
    int vertexId;
    Node* next;
}

class Gragh {
    List<Node> vertices;
}
```

### Adjacency set

```
class Node {
    int vertexId;
    Set<Node> nodes;
}

class Gragh {
    List<Node> vertices;
}

public class AdjacencySetGraph implement Graph {
    private List<Node> vertexList = new ArrayList<>();
    private GaraphType = GaraphType.DIRECTED;
    private int numVertices = 0; 
    public  AdjacencyMatrixGraph(int numVertices, GraphType graphType) {
        this.numVertices = numVertices;
        for (int i = 0; i < numVertices; i++) {
            vertexList.add(new Node(i));
        }
        this.graphType = graphType;
    }
    
    public void addEdge(int v1, int v2) {
        if (v1 >= numVertices || V1 < 0 || v2 >= numVertices || v2 < 0) {
            throw new IllegalArgumentException("Vertex number is not valid");
        }
        
        vertexList.get(v1).addEdge(v2);
        if (graphType == GaraphType.UNDIRECTED) {
            vertexList.get(v2).addEdge(v1);
        }
    }
    
    public List<Integar> getAdjacentVertices(int v) {
        if (v >= numVertices || v < 0) {
            throw new IllegalArgumentException("Vertex number is not valid");
        }
        
        return vertexList.get(v).getAdjacentVertices();
    }
}
```

## 2.Compares

|                                | Matrix  | List        | Set               |
| ------------------------------ | ------- | ----------- | ----------------- |
| Space                          | V^2     | E + V       | E + V             |
| Is edge present                | 1       | Degree of V | Log (Degree of V) |
| Iterate over edges on a vertex | V       | Degree of V | Degree of V       |
| Scenario                       | 當連結數夠大時 | 當連結數少時      | 當連結數少時            |

## 3.Traversal

* This is very similar to tree traversal&#x20;
* In a graph multiple paths can lead from one to another
* Graph has circle, so the same node can be visited multiple times
  * Keep track of the nodes previously visited

### Depth-first traversal (post order)

* Use a visited list to keep track of nodes already visited
  * e.g., boolean array

```
public static void depthFirstTraversal(Gragh graph, int[] visited, int currentVertex) {
    if (visited[currentVertex] == 1) {
        return;
    }
    visited[currentVertex] = 1;
    List<Integar> list = new gragh.getAdjacentVertices(currentVertex);
    
    for (int vertex : list) {
        depthFirstTraversal(graph, visited, vertex);
    }
}
```

### Breadth-first traversal&#x20;

