graphNote - juedaiyuer/researchNote GitHub Wiki
#图笔记#
顶点表：V0,V1,V2,V3
临接表：图的存储结构，上图的总体即是临接表
##简易代码实现##
###节点定义###
package myAlgorithm.graphSimple;
/**
* Created by juedaiyuer on 16-10-28.
*/
public class GraphNode {
int val;
GraphNode next;
GraphNode[] neighbors;
boolean visited;
GraphNode(int x){
val = x;
}
GraphNode(int x , GraphNode[] n){
val = x;
neighbors = n;
}
public String toString(){
return "value: "+this.val;
}
}
###队列定义###
package myAlgorithm.graphSimple;
/**
* Created by juedaiyuer on 16-10-28.
*/
public class Queue {
GraphNode first, last;
/*
* first last并没有先后之分，只不过是遍历节点的标志
* */
public void enqueue(GraphNode n) {
if (first == null) {
first = n;
last = first;
} else {
last.next = n;
last = n;
}
}
/*
* Task:遍历当前节点
* */
public GraphNode IteratorQueue() {
if (first == null) {
return null;
} else {
GraphNode temp = new GraphNode(first.val, first.neighbors);
first = first.next;
return temp;
}
}
}
###广度搜索###
package myAlgorithm.graphSimple;
/**
* Created by juedaiyuer on 16-11-7.
*/
public class breathFirstSearch {
public breathFirstSearch(GraphNode root, int x) {
if (root.val == x) {
System.out.println("find in root");
}
Queue queue = new Queue();
root.visited = true;
queue.enqueue(root);
while (queue.first != null) {
GraphNode c = (GraphNode) queue.IteratorQueue();
for (GraphNode n : c.neighbors) {
if (!n.visited) {
// 打印当前遍历节点
System.out.println(n + " ");
n.visited = true;
if (n.val == x)
System.out.println("Find " + n);
queue.enqueue(n);
}
}
}
}
}
###测试###
package myAlgorithm.graphSimple;
/**
* Task:用队列Queue实现广度优先搜索
*
* Created by juedaiyuer on 16-11-7.
*/
public class GraphTest {
public static void main(String[] args) {
GraphNode n1 = new GraphNode(1);
GraphNode n2 = new GraphNode(2);
GraphNode n3 = new GraphNode(3);
GraphNode n4 = new GraphNode(4);
GraphNode n5 = new GraphNode(5);
n1.neighbors = new GraphNode[]{n2, n3, n5};
n2.neighbors = new GraphNode[]{n1, n4};
n3.neighbors = new GraphNode[]{n1, n4, n5};
n4.neighbors = new GraphNode[]{n2, n3, n5};
n5.neighbors = new GraphNode[]{n1, n3, n4};
breathFirstSearch bfs = new breathFirstSearch(n1, 5);
}
}
##顶点定义##
##深层优先遍历##
##拓扑排序##
- 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。
- 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
该DAG的拓扑序列为A B C D或者A C B D
而此有向图是不存在拓扑序列的，因为图中存在环路
##代码区##
##source##