数据结构的实现（持续完整中）
 |
leon_a
2007-06-25
节点类
package graph;
public class GraphNode {
public GraphNode link;
public int info;
}
|
|
leon_a
2007-06-25
邻接表表示图的链表类
package graph;
public class GraphList {
public GraphNode first;
public GraphNode last;
public boolean visitable;
public int getAjd(int[] ajd) {
GraphNode current = first;
int length = 0;
while(current != null) {
ajd[length++] = current.info;
current = current.link;
}
return length;
}
public void addNode(int v) {
GraphNode node = new GraphNode();
node.info = v;
if(first == null) {
first = node;
last = node;
} else {
last.link = node;
last = node;
}
}
}
|
|
leon_a
2007-06-25
图类
package graph;
public class Graph {
private int length;
private GraphList[] list;
public Graph(int length) {
this.length = length;
list = new GraphList[length];
}
public void dfs(int v) {
int[] ajd = new int[length];
int ajdlength = list[v].getAjd(ajd);
list[v].visitable = true;
System.out.print(v+" ");
for(int i=0;i<ajdlength;i++) {
int w = ajd[i];
if(!list[w].visitable) {
dfs(w);
}
}
}
//深度优先遍历
public void dfsTravel() {
for(int i=0;i<length;i++) {
list[i].visitable = false;
}
for(int i=0;i<length;i++) {
if(!list[i].visitable) {
dfs(i);
}
}
}
//广度优先遍历
public void bfsTravel() {
for(int i=0;i<length;i++) {
list[i].visitable = false;
}
bfs();
}
private void bfs() {
Queue queue = new Queue();
for(int index=0;index<length;index++) {
if(!list[index].visitable) {
queue.addQueue(index);
list[index].visitable = true;
System.out.print(index+" ");
while(!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] adj = new int[length];
int ajdlength = list[temp].getAjd(adj);
for(int i=0;i<ajdlength;i++) {
int w = adj[i];
if(!list[w].visitable) {
System.out.print(w+" ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}
}
}
//长度
public void length() {
System.out.println(length);
}
public boolean isEmpty() {
return length == 0;
}
//添加节点
public void addGraph(int info) {
for(int i=0;i<length;i++) {
if(list[i] == null) {
GraphList g = new GraphList();
g.addNode(info);
list[i] = g;
break;
}
}
}
//添加边
public void addSide(int vfrom,int vto) {
list[vfrom].addNode(vto);
}
//打印图
public void print() {
for(int i=0;i<length;i++) {
GraphNode current = list[i].first;
while(current != null) {
System.out.print(current.info+" ");
current = current.link;
}
System.out.println();
}
}
public static void main(String[] args) {
Graph graph = new Graph(11);
System.out.println("create graph start");
for(int i=0;i<11;i++) {
graph.addGraph(i);
}
graph.addSide(0, 1);
graph.addSide(0, 5);
graph.addSide(1, 2);
graph.addSide(1, 3);
graph.addSide(1, 5);
graph.addSide(2, 4);
graph.addSide(4, 3);
graph.addSide(5, 6);
graph.addSide(6, 8 );
graph.addSide(7, 3);
graph.addSide(7, 8 );
graph.addSide(8, 10);
graph.addSide(9, 4);
graph.addSide(9, 7);
graph.addSide(9, 10);
graph.print();
System.out.println("create graph end");
graph.bfsTravel();
}
}
|
|
leon_a
2007-06-25
test
|
 |
Spike
2007-06-25
[code]public static[/code]
[code]public static[\code] |
|
leon_a
2007-06-26
接上面，实现队列
package graph;
public class Queue {
public GraphNode first;
public GraphNode last;
public int count;
public void addQueue(int info) {
GraphNode node = new GraphNode();
node.info = info;
if(first == null) {
first = node;
last = node;
} else {
last.link = node;
last = last.link;
}
count++;
}
public void deleteQueue() {
if(first == null) {
System.out.println("null queue");
} else {
first = first.link;
count--;
}
}
public boolean isEmpty() {
return count == 0;
}
public int front() {
if(first == null) {
return -1;
}
return first.info;
}
public int back() {
if(last == null) {
return -1;
}
return last.info;
}
}
|
|
leon_a
2007-06-26
接上面，堆栈
package graph;
public class Stack {
public GraphNode stackTop;
public int count;
public void push(int info) {
GraphNode node = new GraphNode();
node.info = info;
node.link = stackTop;
stackTop = node;
count++;
}
public void pop() {
if(stackTop == null) {
System.out.println("null stack");
} else {
stackTop = stackTop.link;
count--;
}
}
public int top() {
if(stackTop == null) {
return -1;
}
return stackTop.info;
}
}
|
|
leon_a
2007-06-27
Graph类补充了广度优先遍历方法
|
|
leon_a
2007-06-29
图的最短路径算法（迪杰斯特拉实现），有时间再写个弗洛伊德实现
虽然写完了，但感觉代码很垃圾，希望朋友帮忙优化一下，谢谢 两边之间的权值采用了二维数组存储,添加一条边的时候加上了第三个参数：权值
package graph;
public class Graph {
private int length;
private GraphList[] list;
private int[][] weight;
public Graph(int length) {
this.length = length;
list = new GraphList[length];
weight = new int[length][length];
}
public void dfs(int v) {
int[] ajd = new int[length];
int ajdlength = list[v].getAjd(ajd);
list[v].visitable = true;
System.out.print(v + " ");
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
dfs(w);
}
}
}
// 深度优先遍历
public void dfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
for (int i = 0; i < length; i++) {
if (!list[i].visitable) {
dfs(i);
}
}
}
// 广度优先遍历
public void bfsTravel() {
for (int i = 0; i < length; i++) {
list[i].visitable = false;
}
bfs();
}
private void bfs() {
Queue queue = new Queue();
for (int index = 0; index < length; index++) {
if (!list[index].visitable) {
queue.addQueue(index);
list[index].visitable = true;
System.out.print(index + " ");
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!list[w].visitable) {
System.out.print(w + " ");
queue.addQueue(w);
list[w].visitable = true;
}
}
}
}
}
}
// 最短路径
private int[] shortPath(int v) {
int[] shortPath = new int[length];
boolean[] weightFound = new boolean[length];
for (int i = 0; i < length; i++) {
// 趋近无穷
shortPath[i] = 9999;
weightFound[i] = false;
}
shortPath[v] = 0;
weightFound[v] = true;
Queue queue = new Queue();
queue.addQueue(v);
while (!queue.isEmpty()) {
int temp = queue.front();
queue.deleteQueue();
int[] ajd = new int[length];
int ajdlength = list[temp].getAjd(ajd);
for (int i = 0; i < ajdlength; i++) {
int w = ajd[i];
if (!weightFound[w]) {
if (shortPath[w] > shortPath[temp] + weight[temp][w]) {
shortPath[w] = shortPath[temp] + weight[temp][w];
}
}
}
int minWeightNode = 0;
for (int i = 0; i < length; i++) {
if (!weightFound[i]) {
minWeightNode = i;
for (int j = 0; j < length; j++) {
if (!weightFound[j]) {
if (shortPath[j] < shortPath[minWeightNode]) {
minWeightNode = j;
}
}
}
break;
}
}
if (!weightFound[minWeightNode]) {
weightFound[minWeightNode] = true;
queue.addQueue(minWeightNode);
}
}
return shortPath;
}
// 长度
public void length() {
System.out.println(length);
}
public boolean isEmpty() {
return length == 0;
}
// 添加节点
public void addGraph(int info) {
for (int i = 0; i < length; i++) {
if (list[i] == null) {
GraphList g = new GraphList();
g.addNode(info);
list[i] = g;
break;
}
}
}
// 添加边
public void addSide(int vfrom, int vto, int value) {
list[vfrom].addNode(vto);
weight[vfrom][vto] = value;
}
// 打印图
public void print() {
for (int i = 0; i < length; i++) {
GraphNode current = list[i].first;
while (current != null) {
System.out.print(current.info + " ");
current = current.link;
}
System.out.println();
}
}
public static void main(String[] args) {
Graph graph = new Graph(5);
System.out.println("create graph start");
for (int i = 0; i < 5; i++) {
graph.addGraph(i);
}
graph.addSide(0, 1, 16);
graph.addSide(0, 3, 2);
graph.addSide(0, 4, 3);
graph.addSide(3, 4, 7);
graph.addSide(3, 1, 12);
graph.addSide(4, 1, 10);
graph.addSide(4, 3, 5);
graph.addSide(4, 2, 4);
graph.addSide(2, 1, 3);
graph.addSide(1, 2, 5);
graph.print();
System.out.println("create graph end");
int[] shortPath = graph.shortPath(0);
for (int i = 0; i < shortPath.length; i++) {
System.out.print(shortPath[i] + " ");
}
}
}
|
|
leon_a
2007-06-29
上面的程序测试的CASE 不多，有BUG告诉我
|
