Как я реализую Биграф в Java?
ОБНОВЛЕНИЕ
Некоторые ответы до сих пор предложили использовать список смежности. Как список смежности был бы похож в Java?... никакое право указателей :)
Я пытаюсь реализовать Биграф в Java к виду в 2 информации о группах из файла. Я нашел этот пример, и он на самом деле делает задание:
http://users.skynet.be/alperthereal/source_files/html/java/Bipartite.java.html
Однако я хотел бы реализовать свою собственную версию..., если бы Вы смотрите на предыдущее мое сообщение, Вы поняли бы, почему я хочу сделать это сам.
Таким образом, я должен считать файл, от которого я могу получить количество вершин легко, но количество краев не так легко. Строка в качестве примера была бы "PersonA PersonB", который может быть считан, поскольку "PersonA заявляет PersonB". Так чтение этих строк...
"A says B"
"C says B"
"D says B"
"B says D"
"E says A & C"
... производит эту группировку:
{A,D,C} and {B,E}.
Как я пошел бы о реализации этого биграфа? Что такое хороший ресурс для этой задачи? Какие вещи (алгоритмы) я должен рассматривать и думать о при создании класса BipartiteGraph..., возможно, пересекающие/сортирующие алгоритмы?
2 ответа
Это должно быть довольно просто реализовать со списком смежности. Если бы это был неориентированный двудольный граф, я бы предложил использовать матрицу инцидентности.
Таким образом, у вас будет массив связанных списков или массив какого-нибудь динамически распределенного списка для каждого узла. Это должно сделать добавление ребер довольно естественным, например, в вашем примере у вас есть ребро:
Person A-> Person B
Затем вы должны перейти к индексу массива, соответствующему Person A, и отодвинуть индекс, соответствующий Persona B:
[Человек A] = Человек B
Тогда, возможно, вы получите еще одно преимущество
Персона A-> Человек C
Тогда ваш индекс там будет выглядеть так:
[Persona A] = Person B, Person C
В качестве последнего примера это будет список смежности для вашего примера графа:
[A] B
[B] D
[C] B
[D] B
[E] A, C
Каждый индекс имеет список узлов, доступных с этого узла.
«Какие вещи (алгоритмы) я должен учитывать и думать при создании класса BipartiteGraph ...возможно, алгоритмы обхода / сортировки? »
Это действительно зависит от того, что вы хотите делать с графом ...
Для справки: Аналогичный вопрос с кодом на форумах Sun
Ориентированный граф - это такой граф, в котором ребро, соединяющее узлы A и B, имеет направление; если есть край от A до B, это не означает, что есть край от B до A. В вашем примере края имеют направление. (От B к D будет два ребра, одно от B к D и одно от D к B.)
Один из способов реализовать это - аналогично связному списку, с узлами, имеющими ссылки друг на друга, если это необходимо. . Возвращаясь к вашему примеру, nodeA будет иметь ссылку на nodeB , но не наоборот. nodeE будет иметь ссылку на nodeA и nodeC , и так далее. Вы действительно создаете (своего рода) структуру данных, которая имеет понятие узлов и, возможно, ребер. Есть несколько способов сделать это.
Возможная реализация Java могла бы иметь класс под названием AdjacencyList , который имеет Map , содержащий вершину и смежные с ней вершины. AdjacencyList тогда будет иметь возможность выполнять операции со своей картой.
Что касается алгоритмов и вещей, о которых следует помнить, взгляните на свойства двудольных графов в Википедии , в частности
- Граф двудольный тогда и только тогда, когда он не содержит нечетного цикла. . Следовательно, двудольный граф не может содержать клику размера 3 и более.
- Каждое дерево двудольное.
- Циклические графы с четным числом вершин двудольны.
Хорошим тестом была бы реализация алгоритма 2-раскраски, чтобы подтвердить, что граф действительно двудольный.Поиск в глубину, поиск в ширину - хорошие упражнения для реализации.