图 邻接表 Java 实现

 

package abc.Dijkstra.pack3;

import java.util.ArrayList;
import java.util.List;

public class AlGraph {
	
	List<HeadNode> headNodes = new ArrayList<HeadNode>();
	
	void addVertex(HeadNode node) {
		headNodes.add(node);
	}
	
	void addArc(HeadNode head, HeadNode tail) {
		if(head.firstArcNode == null)
			head.firstArcNode = new ArcNode(tail);
		else {
			ArcNode arcNode = head.firstArcNode;
			while (arcNode.nextArcNode != null) {
				arcNode = arcNode.nextArcNode;
			}
			arcNode.nextArcNode = new ArcNode(tail);
		}
	}
	
	static AlGraph createAlGraph() {
		AlGraph alGraph = new AlGraph();
		
		HeadNode A = new HeadNode("A");
		HeadNode B = new HeadNode("B");
		HeadNode C = new HeadNode("C");
		HeadNode D = new HeadNode("D");
		
		alGraph.addVertex(A);
		alGraph.addVertex(B);
		alGraph.addVertex(C);
		alGraph.addVertex(D);
		
		alGraph.addArc(A, B);	alGraph.addArc(A, C);	alGraph.addArc(A, D);
		alGraph.addArc(B, A);	alGraph.addArc(B, D);
		alGraph.addArc(C, A);
		alGraph.addArc(D, A);	alGraph.addArc(D, B);
		
		return alGraph;
	}
	
	void print() {
		for(HeadNode head : headNodes) {
			System.out.print(head.name);
			if(head.firstArcNode != null) {
				ArcNode arcNode = head.firstArcNode;
				System.out.print(" -> ");
				System.out.print(arcNode.headNode.name);
				while (arcNode.nextArcNode != null) {
					arcNode = arcNode.nextArcNode;
					System.out.print(" -> ");
					System.out.print(arcNode.headNode.name);
				}
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		AlGraph.createAlGraph().print();
	}
}

class ArcNode {
	public ArcNode(HeadNode tail) {
		this.headNode = tail;
	}
	HeadNode headNode;
	ArcNode nextArcNode;
}
class HeadNode {
	String name;
	ArcNode firstArcNode;
	
	HeadNode(String name) {
		this.name = name;
	}
}

 

输出 写道

A -> B -> C -> D
B -> A -> D
C -> A
D -> A -> B

 

也许实现的时候，可以不区别头结点和表结点。

但是不区分的话，遍历麻烦些。

 

可以有List代替Link

 

public class AlGraph3 {
	
	List<Node> vertexes = new ArrayList<Node>();
	
	void addVertex(Node vertex) {
		vertexes.add(vertex);
	}
	
	void addArc(Node head, Node tail) {
		head.addArc(tail);
	}
	
	static AlGraph3 createAlGraph() {
		AlGraph3 alGraph = new AlGraph3();
		
		Node A = new Node("A");
		Node B = new Node("B");
		Node C = new Node("C");
		Node D = new Node("D");
		
		alGraph.addVertex(A);
		alGraph.addVertex(B);
		alGraph.addVertex(C);
		alGraph.addVertex(D);
		
		alGraph.addArc(A, B);	alGraph.addArc(A, C);	alGraph.addArc(A, D);
		alGraph.addArc(B, A);	alGraph.addArc(B, D);
		alGraph.addArc(C, A);
		alGraph.addArc(D, A);	alGraph.addArc(D, B);
		
		return alGraph;
	}
	
	void print() {
		for(Node head : vertexes) {
			System.out.print(head.name);
			for(Node arc : head.adjs) {
				System.out.print(" -> ");
				System.out.print(arc.name);
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		AlGraph3.createAlGraph().print();
	}
}

class Node {
	String name;
	List<Node> adjs = new ArrayList<Node>();
	
	Node(String name) {
		this.name = name;
	}
	
	void addArc(Node node) {
		adjs.add(node);
	}
}