Graphs

• Vertices

• 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

• 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