Master Graphs - Network Algorithms

from collections import deque, defaultdict

class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v, weight=1):
        self.graph[u].append((v, weight))
        if not self.directed:
            self.graph[v].append((u, weight))

    def bfs(self, start):
        visited = set()
        queue = deque([start])
        order = []

        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                visited.add(vertex)
                order.append(vertex)
                for neighbor, _ in self.graph[vertex]:
                    if neighbor not in visited:
                        queue.append(neighbor)
        return order

    def dfs(self, start):
        visited = set()
        order = []

        def dfs_visit(vertex):
            visited.add(vertex)
            order.append(vertex)
            for neighbor, _ in self.graph[vertex]:
                if neighbor not in visited:
                    dfs_visit(neighbor)

        dfs_visit(start)
        return order

# Usage
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
print(g.bfs('A'))  # Output: ['A', 'B', 'C', 'D']

class Graph {
    constructor(directed = false) {
        this.adjacencyList = new Map();
        this.directed = directed;
    }

    addVertex(vertex) {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }

    addEdge(v1, v2, weight = 1) {
        this.addVertex(v1);
        this.addVertex(v2);
        this.adjacencyList.get(v1).push({ node: v2, weight });
        if (!this.directed) {
            this.adjacencyList.get(v2).push({ node: v1, weight });
        }
    }

    bfs(start) {
        const visited = new Set();
        const queue = [start];
        const order = [];

        while (queue.length > 0) {
            const vertex = queue.shift();
            if (!visited.has(vertex)) {
                visited.add(vertex);
                order.push(vertex);
                const neighbors = this.adjacencyList.get(vertex) || [];
                for (const { node } of neighbors) {
                    if (!visited.has(node)) {
                        queue.push(node);
                    }
                }
            }
        }
        return order;
    }
}

// Usage
const g = new Graph();
g.addEdge('A', 'B');
g.addEdge('A', 'C');
g.addEdge('B', 'D');
console.log(g.bfs('A')); // Output: ['A', 'B', 'C', 'D']

package main

type Graph struct {
    vertices map[string]*Vertex
    adjList  map[string][]*Edge
    directed bool
}

type Vertex struct {
    ID    string
    Label string
}

type Edge struct {
    From   string
    To     string
    Weight int
}

func NewGraph(directed bool) *Graph {
    return &Graph{
        vertices: make(map[string]*Vertex),
        adjList:  make(map[string][]*Edge),
        directed: directed,
    }
}

func (g *Graph) AddVertex(id, label string) {
    g.vertices[id] = &Vertex{ID: id, Label: label}
    if g.adjList[id] == nil {
        g.adjList[id] = []*Edge{}
    }
}

func (g *Graph) AddEdge(from, to string, weight int) {
    g.adjList[from] = append(g.adjList[from], &Edge{
        From: from, To: to, Weight: weight,
    })
    if !g.directed {
        g.adjList[to] = append(g.adjList[to], &Edge{
            From: to, To: from, Weight: weight,
        })
    }
}

func (g *Graph) BFS(start string) []string {
    visited := make(map[string]bool)
    queue := []string{start}
    order := []string{}

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        if visited[current] {
            continue
        }
        visited[current] = true
        order = append(order, current)

        for _, edge := range g.adjList[current] {
            if !visited[edge.To] {
                queue = append(queue, edge.To)
            }
        }
    }
    return order
}

import java.util.*;

class Graph {
    private Map<String, List<Edge>> adjList;
    private boolean directed;

    class Edge {
        String to;
        int weight;
        Edge(String to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public Graph(boolean directed) {
        this.adjList = new HashMap<>();
        this.directed = directed;
    }

    public void addVertex(String vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(String from, String to, int weight) {
        addVertex(from);
        addVertex(to);
        adjList.get(from).add(new Edge(to, weight));
        if (!directed) {
            adjList.get(to).add(new Edge(from, weight));
        }
    }

    public List<String> bfs(String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        List<String> order = new ArrayList<>();

        queue.offer(start);

        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            if (visited.contains(vertex)) continue;

            visited.add(vertex);
            order.add(vertex);

            for (Edge edge : adjList.get(vertex)) {
                if (!visited.contains(edge.to)) {
                    queue.offer(edge.to);
                }
            }
        }
        return order;
    }
}

#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
using namespace std;

class Graph {
private:
    map<string, vector<pair<string, int>>> adjList;
    bool directed;

public:
    Graph(bool dir = false) : directed(dir) {}

    void addEdge(string from, string to, int weight = 1) {
        adjList[from].push_back({to, weight});
        if (!directed) {
            adjList[to].push_back({from, weight});
        }
    }

    vector<string> bfs(string start) {
        set<string> visited;
        queue<string> q;
        vector<string> order;

        q.push(start);

        while (!q.empty()) {
            string vertex = q.front();
            q.pop();

            if (visited.count(vertex)) continue;

            visited.insert(vertex);
            order.push_back(vertex);

            for (auto& [neighbor, weight] : adjList[vertex]) {
                if (!visited.count(neighbor)) {
                    q.push(neighbor);
                }
            }
        }
        return order;
    }
};

use std::collections::{HashMap, HashSet, VecDeque};

struct Graph {
    adj_list: HashMap<String, Vec<(String, i32)>>,
    directed: bool,
}

impl Graph {
    fn new(directed: bool) -> Self {
        Graph {
            adj_list: HashMap::new(),
            directed,
        }
    }

    fn add_edge(&mut self, from: &str, to: &str, weight: i32) {
        self.adj_list
            .entry(from.to_string())
            .or_insert(Vec::new())
            .push((to.to_string(), weight));

        if !self.directed {
            self.adj_list
                .entry(to.to_string())
                .or_insert(Vec::new())
                .push((from.to_string(), weight));
        }
    }

    fn bfs(&self, start: &str) -> Vec<String> {
        let mut visited = HashSet::new();
        let mut queue = VecDeque::new();
        let mut order = Vec::new();

        queue.push_back(start.to_string());

        while let Some(vertex) = queue.pop_front() {
            if visited.contains(&vertex) {
                continue;
            }

            visited.insert(vertex.clone());
            order.push(vertex.clone());

            if let Some(neighbors) = self.adj_list.get(&vertex) {
                for (neighbor, _) in neighbors {
                    if !visited.contains(neighbor) {
                        queue.push_back(neighbor.clone());
                    }
                }
            }
        }
        order
    }
}