====== Семинар 6 ======

Начальные сведения о графах можно найти {{:java:elective:kormen_p.88-91.pdf|здесь}}.

===== Задание 6.1 =====

Перед началом работы рекомендуется прочитать {{:java:elective:kormen_p.436-441.pdf|раздел 23.1}}.

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

<code java>
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;
    }	
}
</code>

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

<code java>
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());
}
</code>

Реализуйте алгоритм поиска в ширину, описанный в {{:java:elective:kormen_p.436-441.pdf|разделе 23.2}}.