1. 带权图中，边带有一个数字，叫做权，它可能代表距离、耗费、时间或其他意义。
2. 带权图用来最常解决的问题是最短路径问题（pps）。
3. 带权图的最小生成树中有所有的顶点和连接它们的必要的边，且这些边的权值最小。
4. 优先级队列的算法可用于寻找带权图的最小生成树。
5. 解决无向带权图的最小生成树的方法
1) 找到从最新的顶点到其他顶点的所有边，这些顶点不能在树的集合中，把这些边放如优先级队列。
2) 找出权值最小的边，把它和它所到达的顶点放入树的集合中。
3) 重复以上步骤，直到所有顶点都在树的集合中。
6. 带权图的最短路径问题可以用Dijkstra算法解决。这个算法基于图的邻接矩阵表示法，它不仅能找到任意两点间的最短路径，还可以找到某个指定点到其他所有顶点的最短路径。
Dijkstra算法的思想：
以解决寻找一条从一个城市到另一个城市的费用最低的路线为例（假设不能直接指导所有路线的费用，只能直接知道到邻接城市的费用）
1) 每次派一个代理人到新的城市，用这个代理人提供的新信息修正和完善费用清单，在表中之保留从源点到某个城市现在一直的最低费用
2) 不断向某个新城市派代理人，条件是从源点到那个城市的路线费用最低。
如图
7. 有时为了看出某条路线是否可能，需要创建一个连通表。在带权图中，用一张表给出任意两个顶点间的最低耗费，这对顶点可能通过几条边相连。这种问题叫做每一对顶点之间的最短路径问题。Warshall算法（此算法在图章节中详述）能很快创建这样的连通表。在带权图中类似的方法叫做Floyd算法。
Floyd算法与Warshall算法的区别。在Warshall算法中当找到一个两段路径时，只是简单的在表中插入1，在Floyd算法中，需要把两端的权值相加，并插入它们的和。
8. 关于各种图的算法的效率：
图的表示法有两种：邻接矩阵和邻接表
算法 时间级
邻接矩阵（所有） O（V²）
无权邻接表 O(V + E)
带权邻接表 O((E+V)logV)
Warshall和Floyd算法 O（V³）
其中V是顶点数量，E是边的数量
java排序算法的比较
import java.util.*;
import java.io.*;
public class SortAlgorithm
{
static Random rand = new Random();
void bubbleSort(int[] numlist) // 冒泡排序算法
{
int temp;
for(int j=1;j<numlist.length;j++)
for(int i=0;i<numlist.length-j;i++)
if(numlist>numlist[i+1])
{
temp = numlist[i+1];
numlist[i+1] = numlist;
numlist = temp;
}
}
void selectionSort (int[] numlist) //选择排序算法
{
int temp;
for(int i=0;i<numlist.length-1;i++)
for(int j=i+1;j<numlist.length;j++)
if(numlist>numlist[j])
{
temp = numlist[j];
numlist[j] = numlist;
numlist = temp;
}
}
void insertSort (int[] numlist) //插入排序算法
{
int temp,in,out;
for(out=1;out<numlist.length;out++)
{
temp=numlist[out];
in=out;
while(in>0 &&numlist[in-1]>=temp)
{
numlist[in]=numlist[in-1];
--in;
}
numlist[in]=temp;
}
}
void display (int[] num) // 打印出排序结果
{
for(int i = 0;i<num.length;i++)
System.out.print(num+" ");
System.out.println("");
}
static int pRand(int mod) // 生成随即数组
{
return Math.abs(rand.nextInt())%mod;
}
public static void main(Stringargs[])throws IOException
{
SortAlgorithm sortAlgorithm = newSortAlgorithm();
int[] numList = new int[10];
for(int i = 0;i<numList.length;i++)
numList = pRand(100); //调用pRand方法，把随即生成的数据输入到
// 数组中
System.out.println("随即生成的数组是：");
// 打印出原数组，
for(int j =0;j<numList.length;j++)
System.out.print(numList[j]+" ");
System.out.println("");
long begin = System.currentTimeMillis(); //排序开始时间，调用系统的当前时间
sortAlgorithm.bubbleSort(numList); //执行冒泡排序
long end = System.currentTimeMillis(); //排序结束时间，调用系统当前时间
System.out.println("冒泡排序用时为：" + (end-begin)); //排序用时
System.out.println("排序后的数组为：");
sortAlgorithm.display(numList);
begin = System.currentTimeMillis();
sortAlgorithm.selectionSort(numList);
end = System.currentTimeMillis();
System.out.println("选择排序用时为：" +(end-begin));
System.out.println("排序后的数组为：");
sortAlgorithm.display(numList);
begin = System.currentTimeMillis();
sortAlgorithm.insertSort(numList);
end = System.currentTimeMillis();
System.out.println("插入排序用时为：" + (end-begin));
System.out.println("排序后的数组为：");
sortAlgorithm.display(numList);
}
}
题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
static int[] bits = new int[] { 1, 2, 3, 4,5 };
/**
* @param args
*/
public static void main(String[] args) {
sort("", bits);
}
private static void sort(String prefix,int[] a) {
if (a.length == 1) {
System.out.println(prefix + a[0]);
}
for (int i = 0; i < a.length; i++) {
sort(prefix + a, copy(a, i));
}
}
private static int[] copy(int[] a,intindex){
int[] b = new int[a.length-1];
System.arraycopy(a, 0, b, 0, index);
System.arraycopy(a, index+1, b, index,a.length-index-1);
return b;
}
