Hafta 5 — Çizgeler ve Gezinme (Traversal) Algoritmaları¶

/* Week 5 -- Graphs and Traversals
 * Graph vocabulary: vertex, edge, directed/undirected, weighted, degree,
 * in/out-degree, self-loop, parallel (multi-) edge, connected component,
 * cycle. Builds a Graph as an adjacency list (Edge structs, one linked
 * list per vertex) and reports these properties for each scenario.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_V   16
#define MAX_LBL 4

typedef struct Edge {
    int to;               /* index of the other endpoint */
    int weight;           /* 1 if the graph is unweighted */
    struct Edge *next;
} Edge;

typedef struct Graph {
    char label[MAX_V][MAX_LBL];
    Edge *adj[MAX_V];     /* adjacency list, one linked list per vertex */
    int vertex_count;
    int directed;         /* 0 = undirected, 1 = directed */
} Graph;

int out_degree(Graph *g, int v) {
    int d = 0;
    for (Edge *e = g->adj[v]; e != NULL; e = e->next)
        d++;              /* undirected: this already counts BOTH ends written once each -> degree */
    return d;
}

int in_degree(Graph *g, int v) {   /* directed only: how many edges point INTO v */
    int d = 0;
    for (int u = 0; u < g->vertex_count; u++)
        for (Edge *e = g->adj[u]; e != NULL; e = e->next)
            if (e->to == v) d++;
    return d;
}

/* ---- construction helpers: not part of the lecture code panel above, but
 * needed to actually build a Graph from a list of (label, label, weight)
 * edges the way the animation's input box accepts them. ---- */

typedef struct { const char *a, *b; int weight; } EdgeIn;

static int find_or_add_vertex(Graph *g, const char *lbl) {
    for (int i = 0; i < g->vertex_count; i++)
        if (strcmp(g->label[i], lbl) == 0) return i;
    strncpy(g->label[g->vertex_count], lbl, MAX_LBL - 1);
    g->label[g->vertex_count][MAX_LBL - 1] = '\0';
    g->adj[g->vertex_count] = NULL;
    return g->vertex_count++;
}

static void append(Graph *g, int v, int neighbour, int weight) {
    Edge *n = malloc(sizeof(Edge));
    n->to = neighbour;
    n->weight = weight;
    n->next = NULL;
    if (g->adj[v] == NULL) { g->adj[v] = n; return; }
    Edge *cur = g->adj[v];
    while (cur->next != NULL) cur = cur->next;
    cur->next = n;
}

static void add_edge_labelled(Graph *g, const char *a, const char *b, int weight) {
    int ia = find_or_add_vertex(g, a), ib = find_or_add_vertex(g, b);
    append(g, ia, ib, weight);
    if (!g->directed && ia != ib) append(g, ib, ia, weight);
}

static void reset_graph(Graph *g, int directed) {
    g->vertex_count = 0;
    g->directed = directed;
    for (int i = 0; i < MAX_V; i++) g->adj[i] = NULL;
}

static void free_graph(Graph *g) {
    for (int i = 0; i < g->vertex_count; i++) {
        Edge *e = g->adj[i];
        while (e) { Edge *nx = e->next; free(e); e = nx; }
        g->adj[i] = NULL;
    }
}

/* ---- analysis: components (BFS, direction ignored) and cycle (DFS) ---- */

static int undirected_neighbours(Graph *g, int v, int out[]) {
    int n = 0;
    for (Edge *e = g->adj[v]; e; e = e->next)
        if (e->to != v) out[n++] = e->to;             /* v's own out-edges (self-loops excluded here) */
    if (g->directed)
        for (int u = 0; u < g->vertex_count; u++)
            if (u != v)
                for (Edge *e = g->adj[u]; e; e = e->next)
                    if (e->to == v) out[n++] = u;      /* edges pointing INTO v, walked backwards */
    return n;
}

static int count_components(Graph *g, int comp_of[]) {
    int queue_data[MAX_V];
    for (int i = 0; i < g->vertex_count; i++) comp_of[i] = -1;
    int next_id = 0;
    for (int s = 0; s < g->vertex_count; s++) {
        if (comp_of[s] != -1) continue;
        int front = 0, rear = 0;
        comp_of[s] = next_id;
        queue_data[rear++] = s;
        while (front < rear) {
            int u = queue_data[front++];
            int nb[2 * MAX_V];
            int n = undirected_neighbours(g, u, nb);
            for (int i = 0; i < n; i++)
                if (comp_of[nb[i]] == -1) { comp_of[nb[i]] = next_id; queue_data[rear++] = nb[i]; }
        }
        next_id++;
    }
    return next_id;
}

static int color[MAX_V];

static int dfs_has_cycle(Graph *g, int u, int parent) {
    color[u] = 1;
    int skipped_parent = 0;
    for (Edge *e = g->adj[u]; e; e = e->next) {
        int v = e->to;
        if (v == u) return 1;                                        /* self-loop: trivially a cycle */
        if (!g->directed && v == parent && !skipped_parent) { skipped_parent = 1; continue; }
        if (color[v] == 0) { if (dfs_has_cycle(g, v, u)) return 1; }
        else if (color[v] == 1) return 1;                            /* back edge: an ancestor -> a cycle */
    }
    color[u] = 2;
    return 0;
}

static int has_cycle(Graph *g) {
    for (int i = 0; i < g->vertex_count; i++) color[i] = 0;
    for (int i = 0; i < g->vertex_count; i++)
        if (color[i] == 0 && dfs_has_cycle(g, i, -1)) return 1;
    return 0;
}

static void run_scenario(const char *label, int directed, EdgeIn edges[], int n) {
    printf("-- %s --\n", label);
    Graph g;
    reset_graph(&g, directed);
    for (int i = 0; i < n; i++) add_edge_labelled(&g, edges[i].a, edges[i].b, edges[i].weight);

    printf("%s, %d vertices, %d edges\n", directed ? "directed" : "undirected", g.vertex_count, n);

    int self_loops = 0;
    for (int i = 0; i < n; i++)
        if (strcmp(edges[i].a, edges[i].b) == 0) { printf("self-loop: %s-%s\n", edges[i].a, edges[i].b); self_loops++; }
    if (!self_loops) printf("self-loops: none\n");

    int multi_found = 0;
    for (int i = 0; i < n && !multi_found; i++) {
        if (strcmp(edges[i].a, edges[i].b) == 0) continue;
        for (int j = i + 1; j < n; j++) {
            int same = directed
                ? (strcmp(edges[i].a, edges[j].a) == 0 && strcmp(edges[i].b, edges[j].b) == 0)
                : ((strcmp(edges[i].a, edges[j].a) == 0 && strcmp(edges[i].b, edges[j].b) == 0) ||
                   (strcmp(edges[i].a, edges[j].b) == 0 && strcmp(edges[i].b, edges[j].a) == 0));
            if (same) { printf("multi-edge: %s%s%s (%d copies)\n", edges[i].a, directed ? ">" : "-", edges[i].b, 2); multi_found = 1; break; }
        }
    }
    if (!multi_found) printf("multi-edges: none\n");

    if (!directed) {
        printf("degree (list-length, via out-degree):");
        for (int i = 0; i < g.vertex_count; i++) printf(" %s=%d", g.label[i], out_degree(&g, i));
        printf("\n");
    } else {
        printf("in-degree: ");
        for (int i = 0; i < g.vertex_count; i++) printf(" %s=%d", g.label[i], in_degree(&g, i));
        printf("\n");
        printf("out-degree:");
        for (int i = 0; i < g.vertex_count; i++) printf(" %s=%d", g.label[i], out_degree(&g, i));
        printf("\n");
    }

    int comp_of[MAX_V];
    int comps = count_components(&g, comp_of);
    printf("connected components: %d\n", comps);

    int cyc = has_cycle(&g);
    printf("has cycle: %s\n", cyc ? "yes" : "no");

    free_graph(&g);
    printf("\n");
}

int main(void) {
    /* normal: 8 vertices, weighted, a cycle, a self-loop, a multi-edge and 2 components */
    EdgeIn normal[] = {
        {"A", "B", 3}, {"B", "C", 5}, {"C", "A", 2}, {"C", "D", 4},
        {"D", "E", 1}, {"E", "F", 6}, {"E", "F", 9}, {"D", "D", 7},
        {"G", "H", 2}, {"F", "C", 8}
    };
    run_scenario("normal: 8 vertices, weighted, a cycle, a self-loop, a multi-edge and 2 components", 0, normal, 10);

    /* hard: 8 vertices, directed, multiple cycles, a self-loop, a multi-edge and 2 weak components */
    EdgeIn hard[] = {
        {"P", "Q", 3}, {"Q", "R", 1}, {"R", "P", 4}, {"R", "S", 2},
        {"S", "T", 5}, {"T", "U", 1}, {"T", "U", 1}, {"U", "U", 6},
        {"Q", "S", 2}, {"S", "Q", 3}, {"V", "W", 2}, {"W", "V", 3}
    };
    run_scenario("hard: 8 vertices, directed, multiple cycles, a self-loop, a multi-edge and 2 weak components", 1, hard, 12);

    /* edge: an 11-vertex chain, no cycle, unweighted, connected */
    EdgeIn no_cycle[] = {
        {"V1", "V2", 1}, {"V2", "V3", 1}, {"V3", "V4", 1}, {"V4", "V5", 1}, {"V5", "V6", 1},
        {"V6", "V7", 1}, {"V7", "V8", 1}, {"V8", "V9", 1}, {"V9", "V10", 1}, {"V10", "V11", 1}
    };
    run_scenario("edge: an 11-vertex chain, no cycle, unweighted, connected", 0, no_cycle, 10);

    /* edge: a single vertex, shown with a self-loop */
    EdgeIn single[] = { {"A", "A", 1} };
    run_scenario("edge: a single vertex, shown with a self-loop", 0, single, 1);

    return 0;
}

/* Week 5 -- Graphs and Traversals
 * Graph vocabulary: vertex, edge, directed/undirected, weighted, degree,
 * in/out-degree, self-loop, parallel (multi-) edge, connected component,
 * cycle. Builds a Graph as an adjacency list (Edge nodes, one linked list
 * per vertex) and reports these properties for each scenario.
 * CEN207 Data Structures (formerly CE205)
 */
public class GraphTerminology {
    static final int MAX_V = 16;

    static class Edge {
        int to;                 // index of the other endpoint
        int weight;              // 1 if the graph is unweighted
        Edge next;
    }

    static class Graph {
        String[] label = new String[MAX_V];
        Edge[] adj = new Edge[MAX_V];   // adjacency list, one linked list per vertex
        int vertexCount;
        boolean directed;
    }

    static int outDegree(Graph g, int v) {
        int d = 0;
        for (Edge e = g.adj[v]; e != null; e = e.next)
            d++;              // undirected: this already counts BOTH ends written once each -> degree
        return d;
    }

    static int inDegree(Graph g, int v) {   // directed only: how many edges point INTO v
        int d = 0;
        for (int u = 0; u < g.vertexCount; u++)
            for (Edge e = g.adj[u]; e != null; e = e.next)
                if (e.to == v) d++;
        return d;
    }

    // ---- construction helpers: not part of the lecture code panel above, but
    // needed to actually build a Graph from a list of (label, label, weight)
    // edges the way the animation's input box accepts them. ----

    static class EdgeIn {
        String a, b;
        int weight;
        EdgeIn(String a, String b, int weight) { this.a = a; this.b = b; this.weight = weight; }
    }

    static int findOrAddVertex(Graph g, String lbl) {
        for (int i = 0; i < g.vertexCount; i++)
            if (g.label[i].equals(lbl)) return i;
        g.label[g.vertexCount] = lbl;
        g.adj[g.vertexCount] = null;
        return g.vertexCount++;
    }

    static void append(Graph g, int v, int neighbour, int weight) {
        Edge n = new Edge();
        n.to = neighbour;
        n.weight = weight;
        n.next = null;
        if (g.adj[v] == null) { g.adj[v] = n; return; }
        Edge cur = g.adj[v];
        while (cur.next != null) cur = cur.next;
        cur.next = n;
    }

    static void addEdgeLabelled(Graph g, String a, String b, int weight) {
        int ia = findOrAddVertex(g, a), ib = findOrAddVertex(g, b);
        append(g, ia, ib, weight);
        if (!g.directed && ia != ib) append(g, ib, ia, weight);
    }

    // ---- analysis: components (BFS, direction ignored) and cycle (DFS) ----

    static int undirectedNeighbours(Graph g, int v, int[] out) {
        int n = 0;
        for (Edge e = g.adj[v]; e != null; e = e.next)
            if (e.to != v) out[n++] = e.to;             // v's own out-edges (self-loops excluded here)
        if (g.directed)
            for (int u = 0; u < g.vertexCount; u++)
                if (u != v)
                    for (Edge e = g.adj[u]; e != null; e = e.next)
                        if (e.to == v) out[n++] = u;     // edges pointing INTO v, walked backwards
        return n;
    }

    static int countComponents(Graph g, int[] compOf) {
        int[] queueData = new int[MAX_V];
        for (int i = 0; i < g.vertexCount; i++) compOf[i] = -1;
        int nextId = 0;
        for (int s = 0; s < g.vertexCount; s++) {
            if (compOf[s] != -1) continue;
            int front = 0, rear = 0;
            compOf[s] = nextId;
            queueData[rear++] = s;
            while (front < rear) {
                int u = queueData[front++];
                int[] nb = new int[2 * MAX_V];
                int n = undirectedNeighbours(g, u, nb);
                for (int i = 0; i < n; i++)
                    if (compOf[nb[i]] == -1) { compOf[nb[i]] = nextId; queueData[rear++] = nb[i]; }
            }
            nextId++;
        }
        return nextId;
    }

    static int[] color = new int[MAX_V];

    static boolean dfsHasCycle(Graph g, int u, int parent) {
        color[u] = 1;
        boolean skippedParent = false;
        for (Edge e = g.adj[u]; e != null; e = e.next) {
            int v = e.to;
            if (v == u) return true;                                        // self-loop: trivially a cycle
            if (!g.directed && v == parent && !skippedParent) { skippedParent = true; continue; }
            if (color[v] == 0) { if (dfsHasCycle(g, v, u)) return true; }
            else if (color[v] == 1) return true;                            // back edge: an ancestor -> a cycle
        }
        color[u] = 2;
        return false;
    }

    static boolean hasCycle(Graph g) {
        for (int i = 0; i < g.vertexCount; i++) color[i] = 0;
        for (int i = 0; i < g.vertexCount; i++)
            if (color[i] == 0 && dfsHasCycle(g, i, -1)) return true;
        return false;
    }

    static void runScenario(String label, boolean directed, EdgeIn[] edges) {
        System.out.println("-- " + label + " --");
        Graph g = new Graph();
        g.directed = directed;
        for (EdgeIn e : edges) addEdgeLabelled(g, e.a, e.b, e.weight);

        System.out.println((directed ? "directed" : "undirected") + ", " + g.vertexCount + " vertices, " + edges.length + " edges");

        int selfLoops = 0;
        for (EdgeIn e : edges)
            if (e.a.equals(e.b)) { System.out.println("self-loop: " + e.a + "-" + e.b); selfLoops++; }
        if (selfLoops == 0) System.out.println("self-loops: none");

        boolean multiFound = false;
        outer:
        for (int i = 0; i < edges.length; i++) {
            if (edges[i].a.equals(edges[i].b)) continue;
            for (int j = i + 1; j < edges.length; j++) {
                boolean same = directed
                    ? (edges[i].a.equals(edges[j].a) && edges[i].b.equals(edges[j].b))
                    : ((edges[i].a.equals(edges[j].a) && edges[i].b.equals(edges[j].b)) ||
                       (edges[i].a.equals(edges[j].b) && edges[i].b.equals(edges[j].a)));
                if (same) {
                    System.out.println("multi-edge: " + edges[i].a + (directed ? ">" : "-") + edges[i].b + " (2 copies)");
                    multiFound = true;
                    break outer;
                }
            }
        }
        if (!multiFound) System.out.println("multi-edges: none");

        StringBuilder sb;
        if (!directed) {
            sb = new StringBuilder("degree (list-length, via out-degree):");
            for (int i = 0; i < g.vertexCount; i++) sb.append(' ').append(g.label[i]).append('=').append(outDegree(g, i));
            System.out.println(sb);
        } else {
            sb = new StringBuilder("in-degree: ");
            for (int i = 0; i < g.vertexCount; i++) sb.append(' ').append(g.label[i]).append('=').append(inDegree(g, i));
            System.out.println(sb);
            sb = new StringBuilder("out-degree:");
            for (int i = 0; i < g.vertexCount; i++) sb.append(' ').append(g.label[i]).append('=').append(outDegree(g, i));
            System.out.println(sb);
        }

        int[] compOf = new int[MAX_V];
        int comps = countComponents(g, compOf);
        System.out.println("connected components: " + comps);

        boolean cyc = hasCycle(g);
        System.out.println("has cycle: " + (cyc ? "yes" : "no"));

        System.out.println();
    }

    public static void main(String[] args) {
        // normal: 8 vertices, weighted, a cycle, a self-loop, a multi-edge and 2 components
        EdgeIn[] normal = {
            new EdgeIn("A", "B", 3), new EdgeIn("B", "C", 5), new EdgeIn("C", "A", 2), new EdgeIn("C", "D", 4),
            new EdgeIn("D", "E", 1), new EdgeIn("E", "F", 6), new EdgeIn("E", "F", 9), new EdgeIn("D", "D", 7),
            new EdgeIn("G", "H", 2), new EdgeIn("F", "C", 8)
        };
        runScenario("normal: 8 vertices, weighted, a cycle, a self-loop, a multi-edge and 2 components", false, normal);

        // hard: 8 vertices, directed, multiple cycles, a self-loop, a multi-edge and 2 weak components
        EdgeIn[] hard = {
            new EdgeIn("P", "Q", 3), new EdgeIn("Q", "R", 1), new EdgeIn("R", "P", 4), new EdgeIn("R", "S", 2),
            new EdgeIn("S", "T", 5), new EdgeIn("T", "U", 1), new EdgeIn("T", "U", 1), new EdgeIn("U", "U", 6),
            new EdgeIn("Q", "S", 2), new EdgeIn("S", "Q", 3), new EdgeIn("V", "W", 2), new EdgeIn("W", "V", 3)
        };
        runScenario("hard: 8 vertices, directed, multiple cycles, a self-loop, a multi-edge and 2 weak components", true, hard);

        // edge: an 11-vertex chain, no cycle, unweighted, connected
        EdgeIn[] noCycle = {
            new EdgeIn("V1", "V2", 1), new EdgeIn("V2", "V3", 1), new EdgeIn("V3", "V4", 1), new EdgeIn("V4", "V5", 1), new EdgeIn("V5", "V6", 1),
            new EdgeIn("V6", "V7", 1), new EdgeIn("V7", "V8", 1), new EdgeIn("V8", "V9", 1), new EdgeIn("V9", "V10", 1), new EdgeIn("V10", "V11", 1)
        };
        runScenario("edge: an 11-vertex chain, no cycle, unweighted, connected", false, noCycle);

        // edge: a single vertex, shown with a self-loop
        EdgeIn[] single = { new EdgeIn("A", "A", 1) };
        runScenario("edge: a single vertex, shown with a self-loop", false, single);
    }
}

/* Week 5 -- Graphs and Traversals
 * Graph representation: adjacency matrix. Builds a V x V table from an
 * edge list, one edge at a time (undirected mirrors both cells across the
 * diagonal), and prints the whole matrix after every edge is added.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <string.h>

#define MAX_V   16
#define MAX_LBL 4

int matrix[MAX_V][MAX_V];      /* all cells start at 0 */

typedef struct { int a, b, weight; } Edge;

void add_edge(int a, int b, int weight, int directed) {
    matrix[a][b] = weight;      /* 1 if the graph is unweighted */
    if (!directed)
        matrix[b][a] = weight;  /* undirected: mirror across the diagonal */
}

void build_adjacency_matrix(Edge *edges, int edge_count, int directed) {
    for (int i = 0; i < MAX_V; i++)
        for (int j = 0; j < MAX_V; j++)
            matrix[i][j] = 0;
    for (int k = 0; k < edge_count; k++)
        add_edge(edges[k].a, edges[k].b, edges[k].weight, directed);
}

/* ---- construction helpers: turn a (label, label, weight) edge list into
 * the (index, index, weight) Edge array build_adjacency_matrix() expects,
 * with vertex indices assigned in alphabetical label order. ---- */

typedef struct { const char *a, *b; int weight; } EdgeIn;

static int index_of(char labels[][MAX_LBL], int n, const char *lbl) {
    for (int i = 0; i < n; i++) if (strcmp(labels[i], lbl) == 0) return i;
    return -1;
}

static int collect_labels(EdgeIn edges[], int n, char labels[][MAX_LBL]) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (index_of(labels, count, edges[i].a) < 0) strcpy(labels[count++], edges[i].a);
        if (index_of(labels, count, edges[i].b) < 0) strcpy(labels[count++], edges[i].b);
    }
    /* simple insertion sort, alphabetical -- matches the vertex order the animation uses */
    for (int i = 1; i < count; i++) {
        char key[MAX_LBL];
        strcpy(key, labels[i]);
        int j = i - 1;
        while (j >= 0 && strcmp(labels[j], key) > 0) { strcpy(labels[j + 1], labels[j]); j--; }
        strcpy(labels[j + 1], key);
    }
    return count;
}

static void print_matrix(char labels[][MAX_LBL], int n) {
    printf("    ");
    for (int j = 0; j < n; j++) printf("%3s", labels[j]);
    printf("\n");
    for (int i = 0; i < n; i++) {
        printf("%3s ", labels[i]);
        for (int j = 0; j < n; j++) printf("%3d", matrix[i][j]);
        printf("\n");
    }
}

static void run_scenario(const char *label, int directed, EdgeIn in_edges[], int n) {
    printf("-- %s --\n", label);
    char labels[MAX_V][MAX_LBL];
    int v = collect_labels(in_edges, n, labels);

    Edge edges[MAX_V];
    for (int i = 0; i < n; i++) {
        edges[i].a = index_of(labels, v, in_edges[i].a);
        edges[i].b = index_of(labels, v, in_edges[i].b);
        edges[i].weight = in_edges[i].weight;
    }

    build_adjacency_matrix(NULL, 0, directed);   /* zero the matrix first */
    printf("%d vertices, empty matrix:\n", v);
    print_matrix(labels, v);

    for (int k = 0; k < n; k++) {
        add_edge(edges[k].a, edges[k].b, edges[k].weight, directed);
        printf("add_edge(%s, %s, %d)%s\n", in_edges[k].a, in_edges[k].b, in_edges[k].weight,
               (!directed && edges[k].a != edges[k].b) ? " [mirrored]" : "");
        print_matrix(labels, v);
    }
    printf("\n");
}

int main(void) {
    /* normal: 7 vertices, undirected, unweighted, 10 edges */
    EdgeIn normal[] = {
        {"A", "B", 1}, {"B", "C", 1}, {"C", "D", 1}, {"D", "E", 1},
        {"E", "F", 1}, {"F", "G", 1}, {"G", "A", 1},
        {"A", "D", 1}, {"B", "E", 1}, {"C", "F", 1}
    };
    run_scenario("normal: 7 vertices, undirected, unweighted, 10 edges", 0, normal, 10);

    /* hard: 8 vertices, directed, weighted, 10 edges including a reversed pair */
    EdgeIn hard[] = {
        {"P", "Q", 3}, {"Q", "R", 1}, {"R", "S", 4}, {"S", "T", 2},
        {"T", "U", 5}, {"U", "V", 1}, {"V", "W", 3}, {"W", "P", 2},
        {"P", "R", 6}, {"R", "P", 7}
    };
    run_scenario("hard: 8 vertices, directed, weighted, 10 edges including a reversed pair", 1, hard, 10);

    /* edge: 5 vertices, a complete graph (every pair connected), 10 edges */
    EdgeIn dense[] = {
        {"A", "B", 1}, {"A", "C", 1}, {"A", "D", 1}, {"A", "E", 1},
        {"B", "C", 1}, {"B", "D", 1}, {"B", "E", 1},
        {"C", "D", 1}, {"C", "E", 1}, {"D", "E", 1}
    };
    run_scenario("edge: 5 vertices, a complete graph (every pair connected), 10 edges", 0, dense, 10);

    /* edge: a single vertex, shown with a self-loop -- a 1x1 matrix */
    EdgeIn single[] = { {"A", "A", 1} };
    run_scenario("edge: a single vertex, shown with a self-loop -- a 1x1 matrix", 0, single, 1);

    return 0;
}