Семинар 6

Начальные сведения о графах можно найти здесь.

Перед началом работы рекомендуется прочитать раздел 23.1.

Приведем одну из возможных реализаций неориентированного графа в виде списков смежных вершин:

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class UndirectedGraph {
 
    private HashMap<Integer, List<Integer>> verticesMap = new HashMap<Integer, List<Integer>>();	
 
    public void addVertex(Integer vertexNumber){
	if (!hasVertex(vertexNumber)) {
            verticesMap.put(vertexNumber, new ArrayList<Integer>());
        }
    }
 
    public boolean hasVertex(Integer vertexNumber) {
        return verticesMap.containsKey(vertexNumber);
    }
 
    public boolean hasEdge(Integer vertexNumber1, Integer vertexNumber2) {
        if (!hasVertex(vertexNumber1)) return false;
        List<Integer> edges = verticesMap.get(vertexNumber1);
        return Collections.binarySearch(edges, vertexNumber2) >= 0;
    }
 
    public void addEdge(Integer vertexNumber1, Integer vertexNumber2) {
        if (!hasVertex(vertexNumber1)) addVertex(vertexNumber1);
        if (!hasVertex(vertexNumber2)) addVertex(vertexNumber2);
        List<Integer> edges1 = verticesMap.get(vertexNumber1);
        List<Integer> edges2 = verticesMap.get(vertexNumber2);
        edges1.add(vertexNumber2);
        edges2.add(vertexNumber1);
        Collections.sort(edges1);
        Collections.sort(edges2);
    }
 
    public Map<Integer, List<Integer>> getVerticesMap() {
        return verticesMap;
    }	
}

Пример использования класса UndirectedGraph:

Random random = new Random();
UndirectedGraph graph = new UndirectedGraph();
int numberOfVertices = 10;
 
for(int i = 0; i < numberOfVertices; i++) // добавление вершин графа
	graph.addVertex(new Integer(i));
 
for(int i = 0; i < numberOfVertices; i++)
	for(int j = i + 1; j < numberOfVertices; j++){ // добавление ребер графа (случайным образом)
		if(random.nextBoolean())
			graph.addEdge(new Integer(i), new Integer(j));
	}
 
Iterator iterator = graph.getVerticesMap().keySet().iterator();
Object key;
 
while(iterator.hasNext()){// печать списков смежных вершин
	key = iterator.next();
	System.out.println(key.toString() + ": " + graph.getVerticesMap().get(key).toString());
}

Реализуйте алгоритм поиска в ширину, описанный в разделе 23.2.