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

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):
        visited[v] = True
        print(self.vertex_data[v], end=' ')

for i in range(self.size):
            if self.adj_matrix[v][i] == 1 and not visited[i]:
                self.dfs_util(i, visited)

def dfs(self, start_vertex_data):
        visited = [False] * self.size

start_vertex = self.vertex_data.index(start_vertex_data)
        self.dfs_util(start_vertex, visited)
        
    def bfs(self, start_vertex_data):
        queue = [self.vertex_data.index(start_vertex_data)]
        visited = [False] * self.size
        visited[queue[0]] = True
        
        while queue:
            current_vertex = queue.pop(0)
            print(self.vertex_data[current_vertex], end=' ')
            
            for i in range(self.size):
                if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
                    queue.append(i)
                    visited[i] = True

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(3, 4)  # D -> E
g.add_edge(4, 0)  # E -> A
g.add_edge(0, 2)  # A -> C
g.add_edge(2, 5)  # C -> F
g.add_edge(2, 6)  # C -> G
g.add_edge(5, 1)  # F -> B
g.add_edge(1, 2)  # B -> C

g.print_graph()

print("\nDepth First Search starting from vertex D:")
g.dfs('D')

print("\n\nBreadth First Search starting from vertex D:")
g.bfs('D')

#Python

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

typedef struct {
    int **adj_matrix;
    char *vertex_data;
    int size;
} Graph;

Graph* create_graph(int size) {
    Graph *g = malloc(sizeof(Graph));
    g->size = size;

g->adj_matrix = malloc(size * sizeof(int *));
    for (int i = 0; i < size; i++) {
        g->adj_matrix[i] = calloc(size, sizeof(int));
    }

g->vertex_data = malloc(size * sizeof(char));
    return g;
}

void add_edge(Graph *g, int u, int v) {
    if (u >= 0 && u < g->size && v >= 0 && v < g->size) {
        g->adj_matrix[u][v] = 1;
        // g->adj_matrix[v][u] = 1;
    }
}

void add_vertex_data(Graph *g, int vertex, char data) {
    if (vertex >= 0 && vertex < g->size) {
        g->vertex_data[vertex] = data;
    }
}

void print_graph(Graph *g) {
    printf("Adjacency Matrix:\n");
    for (int i = 0; i < g->size; i++) {
        for (int j = 0; j < g->size; j++) {
            printf("%d ", g->adj_matrix[i][j]);
        }
        printf("\n");
    }
    printf("\nVertex Data:\n");
    for (int i = 0; i < g->size; i++) {
        printf("Vertex %d: %c\n", i, g->vertex_data[i]);
    }
}

// Utility function for DFS
void dfs_util(Graph *g, int v, bool *visited) {
    visited[v] = true;
    printf("%c ", g->vertex_data[v]);

for (int i = 0; i < g->size; i++) {
        if (g->adj_matrix[v][i] == 1 && !visited[i]) {
            dfs_util(g, i, visited);
        }
    }
}

// Depth-First Search
void dfs(Graph *g, char start_vertex_data) {
    bool *visited = calloc(g->size, sizeof(bool));
    int start_vertex = -1;

for (int i = 0; i < g->size; i++) {
        if (g->vertex_data[i] == start_vertex_data) {
            start_vertex = i;
            break;
        }
    }

if (start_vertex != -1) {
        dfs_util(g, start_vertex, visited);
    }
    free(visited);
}

// Breadth-First Search
void bfs(Graph *g, char start_vertex_data) {
    bool *visited = calloc(g->size, sizeof(bool));
    int *queue = malloc(g->size * sizeof(int));
    int front = 0, rear = 0;
    int start_vertex = -1;

for (int i = 0; i < g->size; i++) {
        if (g->vertex_data[i] == start_vertex_data) {
            start_vertex = i;
            break;
        }
    }

if (start_vertex != -1) {
        queue[rear++] = start_vertex;
        visited[start_vertex] = true;

while (front < rear) {
            int current_vertex = queue[front++];
            printf("%c ", g->vertex_data[current_vertex]);

for (int i = 0; i < g->size; i++) {
                if (g->adj_matrix[current_vertex][i] == 1 && !visited[i]) {
                    queue[rear++] = i;
                    visited[i] = true;
                }
            }
        }
    }
    free(queue);
    free(visited);
}

void free_graph(Graph *g) {
    for (int i = 0; i < g->size; i++) {
        free(g->adj_matrix[i]);
    }
    free(g->adj_matrix);
    free(g->vertex_data);
    free(g);
}

int main() {
    Graph *g = create_graph(7);

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

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

print_graph(g);

printf("\nDepth First Search starting from vertex D:\n");
    dfs(g, 'D');

printf("\n\nBreadth First Search starting from vertex D:\n");
    bfs(g, 'D');

free_graph(g);
    return 0;
}

//C

public class Main {
    static class Graph {
        private int[][] adjMatrix;
        private String[] vertexData;
        private int size;

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

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

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

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

private void dfsUtil(int v, boolean[] visited) {
            visited[v] = true;
            System.out.print(vertexData[v] + " ");

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

public void dfs(String startVertexData) {
            boolean[] visited = new boolean[size];
            int startVertex = findVertexIndex(startVertexData);
            dfsUtil(startVertex, visited);
        }

public void bfs(String startVertexData) {
            int[] queue = new int[size];
            int queueStart = 0, queueEnd = 0;
            boolean[] visited = new boolean[size];
            int startVertex = findVertexIndex(startVertexData);
            queue[queueEnd++] = startVertex;
            visited[startVertex] = true;

while (queueStart < queueEnd) {
                int currentVertex = queue[queueStart++];
                System.out.print(vertexData[currentVertex] + " ");

for (int i = 0; i < size; i++) {
                    if (adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                        queue[queueEnd++] = i;
                        visited[i] = true;
                    }
                }
            }
        }

private int findVertexIndex(String data) {
            for (int i = 0; i < size; i++) {
                if (vertexData[i].equals(data)) {
                    return i;
                }
            }
            return -1;
        }
    }

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

g.printGraph();

System.out.println("\nDepth First Search starting from vertex D:");
        g.dfs("D");

System.out.println("\n\nBreadth First Search starting from vertex D:");
        g.bfs("D");
    }
}

//Java