Spaces:
Running
Running
| <html lang="en"> | |
| <head> | |
| <meta charset="UTF-8"> | |
| <meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
| <title>Graph Algorithms - Algorithm Animator</title> | |
| <link rel="icon" type="image/x-icon" href="/static/favicon.ico"> | |
| <script src="https://cdn.tailwindcss.com"></script> | |
| <script src="https://cdn.jsdelivr.net/npm/feather-icons/dist/feather.min.js"></script> | |
| <script src="https://unpkg.com/feather-icons"></script> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML" async></script> | |
| <style> | |
| body { | |
| background-color: #0f172a; | |
| color: #e2e8f0; | |
| font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif; | |
| } | |
| .algorithm-selector { | |
| background-color: #1e293b; | |
| border-radius: 8px; | |
| transition: all 0.3s ease; | |
| } | |
| .algorithm-selector:hover { | |
| background-color: #334155; | |
| } | |
| .active-algorithm { | |
| background-color: #334155; | |
| border-left: 4px solid #34d399; | |
| } | |
| .visualization-area { | |
| background: linear-gradient(135deg, #1e293b 0%, #0f172a 100%); | |
| border-radius: 12px; | |
| box-shadow: 0 10px 30px rgba(0, 0, 0, 0.5); | |
| } | |
| .node { | |
| fill: #60a5fa; | |
| stroke: #93c5fd; | |
| stroke-width: 2px; | |
| transition: all 0.3s ease; | |
| } | |
| .node.visited { | |
| fill: #34d399; | |
| stroke: #6ee7b7; | |
| } | |
| .node.current { | |
| fill: #fbbf24; | |
| stroke: #fcd34d; | |
| } | |
| .edge { | |
| stroke: #64748b; | |
| stroke-width: 2; | |
| } | |
| .edge.visited { | |
| stroke: #34d399; | |
| stroke-width: 3; | |
| } | |
| .edge.current { | |
| stroke: #fbbf24; | |
| stroke-width: 3; | |
| } | |
| .code-block { | |
| background-color: #1e293b; | |
| border-left: 4px solid #34d399; | |
| font-family: 'Fira Code', monospace; | |
| } | |
| .complexity-badge { | |
| background-color: #334155; | |
| } | |
| </style> | |
| </head> | |
| <body class="min-h-screen"> | |
| <!-- Navigation --> | |
| <nav class="bg-slate-900 border-b border-slate-700 sticky top-0 z-50"> | |
| <div class="max-w-7xl mx-auto px-4 sm:px-6 lg:px-8"> | |
| <div class="flex items-center justify-between h-16"> | |
| <div class="flex items-center"> | |
| <div class="flex-shrink-0 flex items-center"> | |
| <i data-feather="cpu" class="text-blue-400 mr-2"></i> | |
| <span class="font-bold text-xl text-white">Algorithm Animator</span> | |
| </div> | |
| <div class="hidden md:block"> | |
| <div class="ml-10 flex items-baseline space-x-4"> | |
| <a href="index.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Home</a> | |
| <a href="sorting.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Sorting</a> | |
| <a href="#" class="text-white px-3 py-2 rounded-md text-sm font-medium">Graph Algorithms</a> | |
| <a href="dynamic.html" class="text-gray-300 hover:text-white px-3 py-2 rounded-md text-sm font-medium">Dynamic Programming</a> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </nav> | |
| <!-- Main Content --> | |
| <div class="max-w-7xl mx-auto px-4 sm:px-6 lg:px-8 py-8"> | |
| <div class="text-center mb-10"> | |
| <h1 class="text-3xl font-extrabold text-white sm:text-4xl"> | |
| Graph Algorithms Visualization | |
| </h1> | |
| <p class="mt-3 max-w-2xl mx-auto text-xl text-gray-300"> | |
| Explore fundamental graph algorithms through interactive visualizations | |
| </p> | |
| </div> | |
| <div class="flex flex-col lg:flex-row gap-8"> | |
| <!-- Algorithm Selection Panel --> | |
| <div class="lg:w-1/4"> | |
| <div class="bg-slate-800 rounded-lg p-6 sticky top-24"> | |
| <h2 class="text-xl font-bold text-white mb-4">Graph Algorithms</h2> | |
| <div class="space-y-3"> | |
| <div class="algorithm-selector p-4 cursor-pointer active-algorithm"> | |
| <h3 class="font-medium text-white">Breadth-First Search</h3> | |
| <p class="text-sm text-gray-300 mt-1">Level-order traversal algorithm</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">Depth-First Search</h3> | |
| <p class="text-sm text-gray-300 mt-1">Recursive traversal algorithm</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">Dijkstra's Algorithm</h3> | |
| <p class="text-sm text-gray-300 mt-1">Shortest path in weighted graphs</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">Prim's Algorithm</h3> | |
| <p class="text-sm text-gray-300 mt-1">Minimum spanning tree</p> | |
| </div> | |
| <div class="algorithm-selector p-4 cursor-pointer"> | |
| <h3 class="font-medium text-white">Kruskal's Algorithm</h3> | |
| <p class="text-sm text-gray-300 mt-1">Minimum spanning forest</p> | |
| </div> | |
| </div> | |
| <div class="mt-8"> | |
| <h3 class="font-medium text-white mb-3">Controls</h3> | |
| <div class="grid grid-cols-2 gap-3"> | |
| <button class="bg-green-600 hover:bg-green-700 text-white py-2 px-4 rounded"> | |
| Play | |
| </button> | |
| <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded"> | |
| Pause | |
| </button> | |
| <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded"> | |
| Reset | |
| </button> | |
| <button class="bg-slate-700 hover:bg-slate-600 text-white py-2 px-4 rounded"> | |
| Step | |
| </button> | |
| </div> | |
| </div> | |
| <div class="mt-8"> | |
| <h3 class="font-medium text-white mb-3">Graph Type</h3> | |
| <select class="w-full bg-slate-700 text-white rounded p-2"> | |
| <option>Undirected Graph</option> | |
| <option>Directed Graph</option> | |
| <option>Weighted Graph</option> | |
| </select> | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Visualization Area --> | |
| <div class="lg:w-3/4"> | |
| <div class="visualization-area p-6 rounded-xl"> | |
| <div class="flex justify-between items-center mb-6"> | |
| <h2 class="text-2xl font-bold text-white">Breadth-First Search Visualization</h2> | |
| <div class="flex space-x-3"> | |
| <div class="complexity-badge px-3 py-1 rounded-full text-sm"> | |
| Time: O(V + E) | |
| </div> | |
| <div class="complexity-badge px-3 py-1 rounded-full text-sm"> | |
| Space: O(V) | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Graph Visualization --> | |
| <div class="mb-8"> | |
| <div class="bg-slate-800 rounded-lg p-6 h-96 flex items-center justify-center"> | |
| <!-- SVG Graph Visualization --> | |
| <svg width="100%" height="100%" viewBox="0 0 600 300"> | |
| <!-- Edges --> | |
| <line x1="100" y1="150" x2="200" y2="100" class="edge visited"></line> | |
| <line x1="200" y1="100" x2="300" y2="150" class="edge current"></line> | |
| <line x1="300" y1="150" x2="400" y2="100" class="edge"></line> | |
| <line x1="100" y1="150" x2="200" y2="200" class="edge"></line> | |
| <line x1="200" y1="200" x2="300" y2="150" class="edge visited"></line> | |
| <line x1="300" y1="150" x2="400" y2="200" class="edge"></line> | |
| <!-- Nodes --> | |
| <circle cx="100" cy="150" r="20" class="node visited"></circle> | |
| <circle cx="200" cy="100" r="20" class="node visited"></circle> | |
| <circle cx="300" cy="150" r="20" class="node current"></circle> | |
| <circle cx="400" cy="100" r="20" class="node"></circle> | |
| <circle cx="200" cy="200" r="20" class="node visited"></circle> | |
| <circle cx="400" cy="200" r="20" class="node"></circle> | |
| <!-- Node Labels --> | |
| <text x="100" y="155" text-anchor="middle" class="text-white font-bold">A</text> | |
| <text x="200" y="105" text-anchor="middle" class="text-white font-bold">B</text> | |
| <text x="300" y="155" text-anchor="middle" class="text-white font-bold">C</text> | |
| <text x="400" y="105" text-anchor="middle" class="text-white font-bold">D</text> | |
| <text x="200" y="205" text-anchor="middle" class="text-white font-bold">E</text> | |
| <text x="400" y="205" text-anchor="middle" class="text-white font-bold">F</text> | |
| </svg> | |
| </div> | |
| </div> | |
| <!-- Current Step Description --> | |
| <div class="bg-slate-800 rounded-lg p-4 mb-6"> | |
| <h3 class="font-bold text-white mb-2">Current Step</h3> | |
| <p class="text-gray-300">Visiting node C. Adding its unvisited neighbors D and F to the queue.</p> | |
| </div> | |
| <!-- Queue Visualization --> | |
| <div class="bg-slate-800 rounded-lg p-4 mb-6"> | |
| <h3 class="font-bold text-white mb-2">BFS Queue</h3> | |
| <div class="flex space-x-2"> | |
| <div class="bg-blue-500 px-3 py-1 rounded">D</div> | |
| <div class="bg-blue-500 px-3 py-1 rounded">F</div> | |
| <div class="bg-gray-700 px-3 py-1 rounded text-gray-400">Empty</div> | |
| <div class="bg-gray-700 px-3 py-1 rounded text-gray-400">Empty</div> | |
| </div> | |
| </div> | |
| <!-- Pseudocode --> | |
| <div class="code-block p-4 rounded mb-6"> | |
| <h3 class="font-bold text-white mb-2">Pseudocode</h3> | |
| <pre class="text-green-400 text-sm"> | |
| BFS(graph, start): | |
| queue = [start] | |
| visited = set([start]) | |
| while queue: | |
| node = queue.pop(0) | |
| process(node) | |
| for neighbor in graph[node]: | |
| if neighbor not in visited: | |
| visited.add(neighbor) | |
| queue.append(neighbor)</pre> | |
| </div> | |
| <!-- Mathematical Explanation --> | |
| <div class="bg-slate-800 rounded-lg p-4"> | |
| <h3 class="font-bold text-white mb-3">Mathematical Analysis</h3> | |
| <div class="math-display text-green-300"> | |
| \( \text{Time Complexity: } O(V + E) \) | |
| </div> | |
| <p class="text-gray-300 mt-3"> | |
| BFS visits each vertex exactly once and examines each edge exactly twice | |
| (once from each endpoint in undirected graphs). Therefore, the time complexity | |
| is proportional to the sum of vertices and edges. | |
| </p> | |
| <div class="math-display text-green-300"> | |
| \( \text{Space Complexity: } O(V) \) | |
| </div> | |
| <p class="text-gray-300 mt-3"> | |
| The space complexity is determined by the maximum size of the queue, which | |
| can contain at most \( V-1 \) vertices in the worst case (when all but one | |
| vertex are at the same level of the BFS tree). | |
| </p> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| </div> | |
| <!-- Footer --> | |
| <footer class="bg-slate-900 border-t border-slate-800 mt-12"> | |
| <div class="max-w-7xl mx-auto py-12 px-4 sm:px-6 lg:px-8"> | |
| <div class="md:flex md:items-center md:justify-between"> | |
| <div class="flex justify-center md:justify-start"> | |
| <div class="flex items-center"> | |
| <i data-feather="cpu" class="text-blue-400 mr-2"></i> | |
| <span class="text-white font-bold">Algorithm Animator</span> | |
| </div> | |
| </div> | |
| <div class="mt-8 md:mt-0 md:order-1"> | |
| <p class="text-center text-base text-gray-400"> | |
| © 2023 Algorithm Animator. All rights reserved. | |
| </p> | |
| </div> | |
| </div> | |
| </div> | |
| </footer> | |
| <script> | |
| feather.replace(); | |
| </script> | |
| </body> | |
| </html> | |