Kompyuter injeneringi

TATU NURAFSHON FILIALI “KOMPYUTER INJENERINGI” 210-22 GURUH TALABASI NAZIRQULOV BARKAMOLNING MA’LUMOTLAR TUZILMASI VA ALGORITMI

FANIDAN BAJARGAN
3-AMALIY TOPSHIRIG’I

13.mavzu
import java.util.ArrayList;

import java.util.List;
import java.util.Stack;

class Graph {

private int vertexCount;
private List> adjacencyList;

public Graph(int vertexCount) {

this.vertexCount = vertexCount;
adjacencyList = new ArrayList<>(vertexCount);
for (int i = 0; i < vertexCount; i++) {
adjacencyList.add(new ArrayList<>());
}
}

public void addEdge(int source, int destination) {

adjacencyList.get(source).add(destination);
}

public void DFS(int startVertex) {

boolean[] visited = new boolean[vertexCount];
Stack stack = new Stack<>();

visited[startVertex] = true;

stack.push(startVertex);

while (!stack.isEmpty()) {

int currentVertex = stack.pop();
System.out.print(currentVertex + " ");

List neighbors = adjacencyList.get(currentVertex);

for (int neighbor : neighbors) {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
}
}

public class GraphTraversal {

public static void main(String[] args) {
Graph graph = new Graph(6);

graph.addEdge(0, 1);

graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);

System.out.print("DFS traversal: ");

graph.DFS(0);
}
}
14.mavzu
import java.util.ArrayList;
import java.util.List;

class Graph {

private int vertexCount;
private List> adjacencyList;
private int[][] adjacencyMatrix;

public Graph(int vertexCount) {

this.vertexCount = vertexCount;
adjacencyList = new ArrayList<>(vertexCount);
adjacencyMatrix = new int[vertexCount][vertexCount];
for (int i = 0; i < vertexCount; i++) {
adjacencyList.add(new ArrayList<>());
}
}

public void addEdge(int source, int destination) {

adjacencyList.get(source).add(destination);
adjacencyList.get(destination).add(source);
adjacencyMatrix[source][destination] = 1;
adjacencyMatrix[destination][source] = 1;
}

public void printAdjacencyList() {

for (int i = 0; i < vertexCount; i++) {
System.out.print("Vertex " + i + ": ");
for (int neighbor : adjacencyList.get(i)) {
System.out.print(neighbor + " ");
}
System.out.println();
}
}

public void printAdjacencyMatrix() {

for (int i = 0; i < vertexCount; i++) {
for (int j = 0; j < vertexCount; j++) {
System.out.print(adjacencyMatrix[i][j] + " ");
}
System.out.println();
}
}
}

public class GraphRepresentation {

public static void main(String[] args) {
Graph graph = new Graph(6);

graph.addEdge(0, 1);

graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);

System.out.println("Adjacency List:");

graph.printAdjacencyList();

System.out.println("\nAdjacency Matrix:");

graph.printAdjacencyMatrix();
}
}
15-mavzu. Dijkstra algoritmi dasturi:
import java.util.*;

class Graph {

private int vertexCount;
private List> adjacencyList;

public Graph(int vertexCount) {

this.vertexCount = vertexCount;
adjacencyList = new ArrayList<>(vertexCount);
for (int i = 0; i < vertexCount; i++) {
adjacencyList.add(new ArrayList<>());
}
}

public void addEdge(int source, int destination, int weight) {

adjacencyList.get(source).add(new Edge(destination, weight));
}

public int[] dijkstra(int source) {

int[] distances = new int[vertexCount];
Arrays.fill(distances, Integer.MAX_VALUE);
distances[source] = 0;

PriorityQueue pq = new PriorityQueue<>(Comparator.comparingInt(node -> node.distance));

pq.add(new Node(source, 0));

while (!pq.isEmpty()) {

Node current = pq.poll();
int vertex = current.vertex;
int distance = current.distance;

if (distance > distances[vertex]) {

continue;
}

for (Edge edge : adjacencyList.get(vertex)) {

int newDistance = distance + edge.weight;
if (newDistance < distances[edge.destination]) {
distances[edge.destination] = newDistance;
pq.add(new Node(edge.destination, newDistance));
}
}
}

return distances;

}

private static class Edge {

private int destination;
private int weight;

public Edge(int destination, int weight) {

this.destination = destination;
this.weight = weight;
}
}

private static class Node {

private int vertex;
private int distance;

public Node(int vertex, int distance) {

this.vertex = vertex;
this.distance = distance;
}
}
}

public class DijkstraAlgorithm {

public static void main(String[] args) {
Graph graph = new Graph(6);

graph.addEdge(0, 1, 2);

graph.addEdge(0, 2, 4);
graph.addEdge(1, 3, 7);
graph.addEdge(1, 4, 3);
graph.addEdge(2, 4, 1);
graph.addEdge(3, 4, 5);
graph.addEdge(3, 5, 2);

int[] distances = graph.dijkstra(0);

System.out.println("Shortest distances from source vertex 0:");
for (int i = 0; i < distances.length; i++) {
System.out.println("Vertex " + i + ": " + distances[i]);
}
}
}

•