廣度優先周遊

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;


public class extentTravel {

	public static void main(String[] args) {
		//圖的鄰接表定義
		int[][] g={
				{0,1,1,0,0,0,0},
				{1,0,0,1,0,0,1},
				{1,0,0,0,0,1,1},
				{0,1,0,0,1,0,0},
				{0,0,0,1,0,1,1},
				{0,0,1,0,1,0,0},
				{0,1,1,0,1,0,0}
		};
		<img src="https://img-blog.csdn.net/20160315163624455?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

		//廣度優先周遊 
		List lst = new ArrayList();//等待周遊
		Set set = new HashSet();//已經周遊節點的集合
		lst.add(0);
		
		while(true){
			if(lst.isEmpty()) break;
			
			int node = (Integer)lst.get(0);
			System.out.println(node);
			set.add(node);
			lst.remove(0);
			
			for(int i=0;i<g[node].length;i++){
				if(g[node][i] == 1 && set.contains(i) == false && lst.indexOf(i)<0){
					lst.add(i);
				}
			}
		}
	}

}
           

最短路徑問題

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

public class minRoot {
	static class Cell {
		int node;// 連接配接到哪個節點
		int weight;// 邊的權值

		public Cell(int node, int weight) {
			this.node = node;
			this.weight = weight;
		}
	}

	// 已找到的最短路徑資訊

	public static void main(String[] args) {
		List[] g = new List[11];
		for (int i = 0; i < g.length; i++)
			g[i] = new ArrayList();
		g[0].add(new Cell(1, 3));
		g[0].add(new Cell(4, 1));
		g[1].add(new Cell(2, 1));
		g[1].add(new Cell(6, 3));
		g[1].add(new Cell(9, 4));
		g[1].add(new Cell(5, 5));
		g[1].add(new Cell(0, 3));
		g[2].add(new Cell(1, 1));
		g[2].add(new Cell(3, 1));
		g[2].add(new Cell(6, 7));
		g[3].add(new Cell(2, 1));
		g[3].add(new Cell(10, 2));
		g[4].add(new Cell(0, 1));
		g[4].add(new Cell(5, 2));
		g[5].add(new Cell(4, 2));
		g[5].add(new Cell(1, 5));
		g[5].add(new Cell(7, 2));
		g[5].add(new Cell(8, 3));
		g[6].add(new Cell(2, 3));
		g[6].add(new Cell(3, 7));
		g[6].add(new Cell(8, 2));
		g[6].add(new Cell(10, 1));
		g[7].add(new Cell(5, 2));
		g[8].add(new Cell(5, 3));
		g[8].add(new Cell(6, 2));
		g[9].add(new Cell(1, 4));
		g[9].add(new Cell(10, 2));
		g[10].add(new Cell(3, 2));
		g[10].add(new Cell(6, 1));
		g[10].add(new Cell(9, 2));
                <img src="https://img-blog.csdn.net/20160315163732063?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />


		// 求0号節點開始的所有最小路徑

		Map map = new HashMap();// 節點号-->最小路徑值

		while (true) {
			int min = Integer.MAX_VALUE;// 最小路徑值
			int min_no = -1;// 對應的節點号

			// 所有與0号節點鄰接，并且不在map中的點
			for (int i1 = 0; i1 < g[0].size(); i1++) {
				Cell t = (Cell) g[0].get(i1);
				if (map.get(t.node) == null && t.weight < min) {
					min_no = t.node;
					min = t.weight;
				}
			}

			// 與map中點鄰接所有不在map中的點
			Iterator it = map.keySet().iterator();
			while (it.hasNext()) {
				int k = (Integer) it.next();
				int v = (Integer) map.get(k);// 集合中的節點對應的最小路徑值

				for (int i1 = 0; i1 < g[k].size(); i1++) {
					Cell t = (Cell) g[k].get(i1);
					if (map.get(t.node) == null && t.weight + v < min) {
						min_no = t.node;
						min = t.weight + v;
					}
				}
			}

			if (min < Integer.MAX_VALUE) {
				map.put(min_no, min);
			} else {
				break;
			}
		}

		System.out.println(map);

	}

}