邻接矩阵是一种不错的图存储结构，但是我们发现，对于边数相对顶点较少的图，这种结构是存在很大的空间浪费的。因此我们考虑另一种存储结构，把数组和链表相结合的存储方法称为：邻接表。
1.邻接表的处理方法- 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以用单链表存储，无向图称为顶点Vi的边表，有向图称为顶点Vi作为弧尾的出边表。
从图中我们知道，顶点的各个结点有 data 和 firstdge 两个域表示，data域是数据域储存顶点信息，firstedge 是指针域，指向边表的第一个结点，即此结点的第一个邻接点。边表结点有 adjvex 和 next 两个域组成。adjvex 是邻接点域，存储某顶点的邻接点在顶点表中的下标，next 则存储指向边表的下一个指针。
这样的结构，对于我们要获取图的相关信息也是很方便的。比如我们要想知道某个顶点的度，就去查找这个顶点的边表中结点的个数。若要判断顶点Vi到Vj是否存在边，只需要测试顶点 Vi 边表中adjvex是否存在 Vj 的下标 j 就行了。
2.代码实现
package datastructure.graph;
import datastructure.queue.CircleObjectQueue;
public class AdjacencyList {
// 一个内部类：邻接结点
class AdjacencyNode{
// 列索引
int column;
// 下一个邻接结点
AdjacencyNode next;
// 第一个构造方法
public AdjacencyNode(int paraColumn) {
column = paraColumn;
next = null;
} // Of AdjacencyNode
} // Of class AdjacencyNode
// 节点数。这个成员可能是多余的，因为它总是等于header.length
int numNodes;
// 每一行的队头
AdjacencyNode[] headers;
// 第一个邻接表的构造方法
public AdjacencyList(int[][] paraMatrix) {
numNodes = paraMatrix.length;
// 初始化，headers的数据域没有意义
AdjacencyNode tempPreviousNode, tempNode;
headers = new AdjacencyNode[numNodes];
for (int i = 0; i < numNodes; i++) {
headers[i] = new AdjacencyNode(-1);
tempPreviousNode = headers[i];
for(int j = 0; j < numNodes; j++) {
if(paraMatrix[i][j] == 0) {
continue;
} // Of if
// 创造一个新节点。
tempNode = new AdjacencyNode(j);
// 连接
tempPreviousNode.next =tempNode;
tempPreviousNode = tempNode;
} // Of for j
} // Of for i
} // Of class AdjacencyList
public String toString() {
String resultString = "";
AdjacencyNode tempNode;
for (int i = 0; i < numNodes; i++) {
tempNode = headers[i].next;
while (tempNode != null) {
resultString += "(" + i + ", " + +tempNode.column + ")";
tempNode = tempNode.next;
} // Of while
resultString += "rn";
} // Of for i
return resultString;
} // Of toString
//广度优先遍历
public String breadthFirstTraversal(int paraStartIndex) {
CircleObjectQueue tempQueue = new CircleObjectQueue();
String resultString = "";
boolean[] tempVisitedArray = new boolean[numNodes];
tempVisitedArray[paraStartIndex] = true;
// 初始化队列，先访问再入队
resultString += paraStartIndex;
tempQueue.enqueue(paraStartIndex);
// 现在遍历剩下的图
int tempIndex;
Integer tempInteger = (Integer) tempQueue.dequeue();
AdjacencyNode tempNode;
while (tempInteger != null) {
tempIndex =tempInteger.intValue();
// 把所有没有访问的相邻结点入队
tempNode = headers[tempIndex].next;
while(tempNode != null) {
if (!tempVisitedArray[tempNode.column]) {
// 先访问后入队
tempVisitedArray[tempNode.column] = true;
resultString += tempNode.column;
tempQueue.enqueue(new Integer(tempNode.column));
} // Of if
tempNode = tempNode.next;
} // Of while
// 出队
tempInteger = (Integer) tempQueue.dequeue();
} // Of while
return resultString;
} // Of breadthFirstTraversal
public static void breadthFirstTraversalTest() {
// Test an undirected graph.
int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1 }, { 0, 1, 1, 0 } };
Graph tempGraph = new Graph(tempMatrix);
System.out.println(tempGraph);
String tempSequence = "";
try {
tempSequence = tempGraph.breadthFirstTraversal(2);
} catch (Exception ee) {
System.out.println(ee);
} // Of try.
System.out.println("The breadth first order of visit: " + tempSequence);
}// Of breadthFirstTraversalTest
public static void main(String args[]) {
int[][] tempMatrix = { { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 } };
AdjacencyList tempTable = new AdjacencyList(tempMatrix);
System.out.println("The data are:rn" + tempTable);
// breadthFirstTraversalTest();
}// Of main
}
里面给了一个广度遍历，可以复习一下。实际可以删除
