迄今为止，有些答案建议使用邻接表。在Java中，邻接表会是什么样子呢？…没有指针，对吧 :)
我正在尝试在Java中实现二分图，以将文件中的信息分成两组。我找到了这个例子，它确实做到了：
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类时，我应该考虑哪些事情（算法）...也许是遍历/排序算法？
请试试这个：
Bipartite.java
/*************************************************************************
* Compilation: javac Bipartite.java
* Dependencies: Graph.java
*
* Given a graph, find either (i) a bipartition or (ii) an odd-length cycle.
* Runs in O(E + V) time.
*
*
*************************************************************************/
/**
* The <tt>Bipartite</tt> class represents a data type for
* determining whether an undirected graph is bipartite or whether
* it has an odd-length cycle.
* The <em>isBipartite</em> operation determines whether the graph is
* bipartite. If so, the <em>color</em> operation determines a
* bipartition; if not, the <em>oddCycle</em> operation determines a
* cycle with an odd number of edges.
* <p>
* This implementation uses depth-first search.
* The constructor takes time proportional to <em>V</em> + <em>E</em>
* (in the worst case),
* where <em>V</em> is the number of vertices and <em>E</em> is the number of edges.
* Afterwards, the <em>isBipartite</em> and <em>color</em> operations
* take constant time; the <em>oddCycle</em> operation takes time proportional
* to the length of the cycle.
*/
public class Bipartite {
private boolean isBipartite; // is the graph bipartite?
private boolean[] color; // color[v] gives vertices on one side of bipartition
private boolean[] marked; // marked[v] = true if v has been visited in DFS
private int[] edgeTo; // edgeTo[v] = last edge on path to v
private Stack<Integer> cycle; // odd-length cycle
/**
* Determines whether an undirected graph is bipartite and finds either a
* bipartition or an odd-length cycle.
* @param G the graph
*/
public Bipartite(Graph G) {
isBipartite = true;
color = new boolean[G.V()];
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
dfs(G, v);
}
}
assert check(G);
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
// short circuit if odd-length cycle found
if (cycle != null) return;
// found uncolored vertex, so recur
if (!marked[w]) {
edgeTo[w] = v;
color[w] = !color[v];
dfs(G, w);
}
// if v-w create an odd-length cycle, find it
else if (color[w] == color[v]) {
isBipartite = false;
cycle = new Stack<Integer>();
cycle.push(w); // don't need this unless you want to include start vertex twice
for (int x = v; x != w; x = edgeTo[x]) {
cycle.push(x);
}
cycle.push(w);
}
}
}
/**
* Is the graph bipartite?
* @return <tt>true</tt> if the graph is bipartite, <tt>false</tt> otherwise
*/
public boolean isBipartite() {
return isBipartite;
}
/**
* Returns the side of the bipartite that vertex <tt>v</tt> is on.
* param v the vertex
* @return the side of the bipartition that vertex <tt>v</tt> is on; two vertices
* are in the same side of the bipartition if and only if they have the same color
* @throws UnsupportedOperationException if this method is called when the graph
* is not bipartite
*/
public boolean color(int v) {
if (!isBipartite)
throw new UnsupportedOperationException("Graph is not bipartite");
return color[v];
}
/**
* Returns an odd-length cycle if the graph is not bipartite, and
* <tt>null</tt> otherwise.
* @return an odd-length cycle (as an iterable) if the graph is not bipartite
* (and hence has an odd-length cycle), and <tt>null</tt> otherwise
*/
public Iterable<Integer> oddCycle() {
return cycle;
}
private boolean check(Graph G) {
// graph is bipartite
if (isBipartite) {
for (int v = 0; v < G.V(); v++) {
for (int w : G.adj(v)) {
if (color[v] == color[w]) {
System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
return false;
}
}
}
}
// graph has an odd-length cycle
else {
// verify cycle
int first = -1, last = -1;
for (int v : oddCycle()) {
if (first == -1) first = v;
last = v;
}
if (first != last) {
System.err.printf("cycle begins with %d and ends with %d\n", first, last);
return false;
}
}
return true;
}
/**
* Unit tests the <tt>Bipartite</tt> data type.
*/
public static void main(String[] args) {
// create random bipartite graph with V vertices and E edges; then add F random edges
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
int F = Integer.parseInt(args[2]);
Graph G = new Graph(V);
int[] vertices = new int[V];
for (int i = 0; i < V; i++) vertices[i] = i;
StdRandom.shuffle(vertices);
for (int i = 0; i < E; i++) {
int v = StdRandom.uniform(V/2);
int w = StdRandom.uniform(V/2);
G.addEdge(vertices[v], vertices[V/2 + w]);
}
// add F extra edges
for (int i = 0; i < F; i++) {
int v = (int) (Math.random() * V);
int w = (int) (Math.random() * V);
G.addEdge(v, w);
}
StdOut.println(G);
Bipartite b = new Bipartite(G);
if (b.isBipartite()) {
StdOut.println("Graph is bipartite");
for (int v = 0; v < G.V(); v++) {
StdOut.println(v + ": " + b.color(v));
}
}
else {
StdOut.print("Graph has an odd-length cycle: ");
for (int x : b.oddCycle()) {
StdOut.print(x + " ");
}
StdOut.println();
}
}
}
Here is the code for that.
int[,] BPGraph = new int[7,7]{
{0,1,0,1,0,0,0},
{1,0,1,0,1,1,0},
{0,1,0,1,0,0,1},
{1,0,1,0,1,1,0},
{0,1,0,1,0,0,1},
{0,1,0,1,0,0,1},
{0,0,1,0,1,1,0}
};
int[] BPArray = new int[7] { 0, 0, 0, 0, 0, 0, 0 };
public Boolean BiPartite()
{
Queue<int> VertexQueue = new Queue<int>();
int level = 0;
int nextlevel=0;
Boolean BPFlg = true;
VertexQueue.Enqueue(0);
while(VertexQueue.Count!=0)
{
int current = VertexQueue.Dequeue();
level = BPArray[current];
if (level == 0)
level = 1;
if (level == 2)
nextlevel=1;
else
nextlevel=2;
if(BPArray[current]==0)
BPArray[current] = level;
for (int i = 0; i < 7; i++)
{
if (BPGraph[current, i] == 1)
{
if (BPArray[i] == 0)
{
BPArray[i] = nextlevel;
VertexQueue.Enqueue(i);
}
else if (BPArray[i] == level)
{
BPFlg = false;
break;
}
}
}
if (!BPFlg)
break;
}
return BPFlg;
}
有向图是指连接节点A和B的边具有方向性；如果从A到B有一条边，这并不意味着从B到A也有一条边。在您的示例中，边具有方向性。（从B到D将成为两条边，一条从B到D，另一条从D到B。）
一种实现方法类似于链表，节点根据需要相互引用。回到您的示例，nodeA将引用nodeB，但反之则不然。nodeE将引用nodeA和nodeC等等。您实际上正在创建一种（某种程度上的）数据结构，其中包含节点和可能的边缘概念。有许多方法可以实现它。
一个可能的Java实现方式是创建一个名为AdjacencyList的类，该类具有包含顶点及其相邻顶点的Map<Vertex, List<Vertex>>。然后，AdjacencyList将能够对其Map执行操作。
关于算法和需要注意的事项，请查看Wikipedia上的二分图属性，特别是：
一个好的测试是实现一个2-着色算法来确认该图确实是二分图。深度优先搜索、广度优先搜索是实现的好练习。
1.) 随机选择一个节点。将其放在二分图的“左”侧。
2.) 选择与步骤1中选择的节点相邻的所有节点，并将它们全部放在“右”侧。
3.) 剩余的所有节点都属于二分图的“左”侧。
结束