W3Schools 線上編輯器 - W3Schools 教學

Python

Java

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

def add_edge(self, u, v):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = 1
            #self.adj_matrix[v][u] = 1 <- used for undirected Graphs

def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

def print_graph(self):
        print("Adjacency Matrix:")
        for row in self.adj_matrix:
            print(' '.join(map(str, row)))
        print("\nVertex Data:")
        for vertex, data in enumerate(self.vertex_data):
            print(f"Vertex {vertex}: {data}")
            
    def dfs_util(self, v, visited, recStack):
        visited[v] = True
        recStack[v] = True
        print("Current vertex:",self.vertex_data[v])

for i in range(self.size):
            if self.adj_matrix[v][i] == 1:
                if not visited[i]:
                    if self.dfs_util(i, visited, recStack):
                        return True
                elif recStack[i]:
                    return True
        
        recStack[v] = False
        return False
    
    def is_cyclic(self):
        visited = [False] * self.size
        recStack = [False] * self.size
        for i in range(self.size):
            if not visited[i]:
                print() #new line
                if self.dfs_util(i, visited, recStack):
                    return True
        return False

g = Graph(7)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(3, 0)  # D -> A
g.add_edge(0, 2)  # A -> C
g.add_edge(2, 1)  # C -> B
g.add_edge(2, 4)  # C -> E
g.add_edge(1, 5)  # B -> F
g.add_edge(4, 0)  # E -> A
g.add_edge(2, 6)  # C -> G

g.print_graph()

print("\nGraph has cycle:", g.is_cyclic())

#Python

#include <stdio.h>
#include <stdbool.h>

#define SIZE 7

typedef struct {
    int adjMatrix[SIZE][SIZE];
    char vertexData[SIZE];
} Graph;

void initGraph(Graph *g) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            g->adjMatrix[i][j] = 0;
        }
        g->vertexData[i] = '\0';
    }
}

void addEdge(Graph *g, int u, int v) {
    if (u >= 0 && u < SIZE && v >= 0 && v < SIZE) {
        g->adjMatrix[u][v] = 1;
    }
}

void addVertexData(Graph *g, int vertex, char data) {
    if (vertex >= 0 && vertex < SIZE) {
        g->vertexData[vertex] = data;
    }
}

void printGraph(Graph *g) {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%d ", g->adjMatrix[i][j]);
        }
        printf("\n");
    }

printf("\nVertex Data:\n");
    for (int i = 0; i < SIZE; i++) {
        printf("Vertex %d: %c\n", i, g->vertexData[i]);
    }
}

bool dfsUtil(Graph *g, int v, bool visited[], bool recStack[]) {
    visited[v] = true;
    recStack[v] = true;
    printf("Current vertex: %c\n", g->vertexData[v]);

for (int i = 0; i < SIZE; i++) {
        if (g->adjMatrix[v][i] == 1) {
            if (!visited[i]) {
                if (dfsUtil(g, i, visited, recStack)) {
                    return true;
                }
            } else if (recStack[i]) {
                return true;
            }
        }
    }

recStack[v] = false;
    return false;
}

bool isCyclic(Graph *g) {
    bool visited[SIZE] = {false};
    bool recStack[SIZE] = {false};

for (int i = 0; i < SIZE; i++) {
        if (!visited[i]) {
            printf("\n");
            if (dfsUtil(g, i, visited, recStack)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    Graph g;
    initGraph(&g);

addVertexData(&g, 0, 'A');
    addVertexData(&g, 1, 'B');
    addVertexData(&g, 2, 'C');
    addVertexData(&g, 3, 'D');
    addVertexData(&g, 4, 'E');
    addVertexData(&g, 5, 'F');
    addVertexData(&g, 6, 'G');

addEdge(&g, 3, 0); // D -> A
    addEdge(&g, 0, 2); // A -> C
    addEdge(&g, 2, 1); // C -> B
    addEdge(&g, 2, 4); // C -> E
    addEdge(&g, 1, 5); // B -> F
    addEdge(&g, 4, 0); // E -> A
    addEdge(&g, 2, 6); // C -> G

printGraph(&g);

printf("\nGraph has cycle: %s\n", isCyclic(&g) ? "Yes" : "No");
    return 0;
}

//C

public class Main {

static class Graph {
        private int[][] adjMatrix;
        private char[] vertexData;
        private int size;

public Graph(int size) {
            this.size = size;
            this.adjMatrix = new int[size][size];
            this.vertexData = new char[size];
        }

public void addEdge(int u, int v) {
            if (u >= 0 && u < size && v >= 0 && v < size) {
                adjMatrix[u][v] = 1;
            }
        }

public void addVertexData(int vertex, char data) {
            if (vertex >= 0 && vertex < size) {
                vertexData[vertex] = data;
            }
        }

public void printGraph() {
            System.out.println("Adjacency Matrix:");
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    System.out.print(adjMatrix[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("\nVertex Data:");
            for (int i = 0; i < size; i++) {
                System.out.println("Vertex " + i + ": " + vertexData[i]);
            }
        }

private boolean dfsUtil(int v, boolean[] visited, boolean[] recStack) {
            visited[v] = true;
            recStack[v] = true;
            System.out.println("Current vertex: " + vertexData[v]);

for (int i = 0; i < size; i++) {
                if (adjMatrix[v][i] == 1) {
                    if (!visited[i]) {
                        if (dfsUtil(i, visited, recStack)) {
                            return true;
                        }
                    } else if (recStack[i]) {
                        return true;
                    }
                }
            }

recStack[v] = false;
            return false;
        }

public boolean isCyclic() {
            boolean[] visited = new boolean[size];
            boolean[] recStack = new boolean[size];

for (int i = 0; i < size; i++) {
                if (!visited[i]) {
                    System.out.println(); //new line
                    if (dfsUtil(i, visited, recStack)) {
                        return true;
                    }
                }
            }
            return false;
        }
    }

public static void main(String[] args) {
        Graph g = new Graph(7);

g.addVertexData(0, 'A');
        g.addVertexData(1, 'B');
        g.addVertexData(2, 'C');
        g.addVertexData(3, 'D');
        g.addVertexData(4, 'E');
        g.addVertexData(5, 'F');
        g.addVertexData(6, 'G');

g.addEdge(3, 0); // D -> A
        g.addEdge(0, 2); // A -> C
        g.addEdge(2, 1); // C -> B
        g.addEdge(2, 4); // C -> E
        g.addEdge(1, 5); // B -> F
        g.addEdge(4, 0); // E -> A
        g.addEdge(2, 6); // C -> G

g.printGraph();
        
        System.out.println("\nGraph has cycle: " + g.isCyclic());
    }
}

//Java