# 資料結構 20221205_Graph

>撰寫人[name=AmiYaku1049] [首頁--天空路1049號](https://skys-kid-lai.github.io/1004/)
>>最後編輯[time=Wed, Jan 18, 2023 8:12 PM]
___
## 題目敘述
- 將城市視為節點，火車路線視為邊
1.節點：TP-台北、TC-台中、TN-台南、KCG-高雄、TT-台東
2.邊：E1：台北-台中[直達]、E2：台中-台南[直達]、E3：台北-高雄[直達]、E4：台南-高雄[直達]、E5：高雄-台東[直達]、E6：台東-台北[直達]，分別為五個城市之間的火車路線

- (基本題)
1.請嘗試用圖形結構來儲存上圖
2.請以先深後廣法進行走訪，並列印出走訪後之城市順序

- (挑戰題)
請嘗試用圖形結構來儲存上圖
選單1: 新增城市
選單2: 新增連線
選單3: 先深後廣法進行走訪，並列印出走訪後之城市順序
## 程式碼

class Node
{
	int x;
	Node next;
	public Node(int x)
	{
		this.x = x;
		this.next = null;
	}
}
class GraphLink
{
	public Node first;
	public Node last;
	public boolean isEmpty()
	{
		return first == null ;
	}
	public void print()
	{
		String station[] = {"","TP","KCG","TT","TN","TC"};
		int stop = 0;
		Node current = first;
		while(current != null)
		{
			stop = current.x;
			System.out.print("[" + station[stop] + "]");
			//System.out.print("[" + stop + "]");
			current = current.next;
		}
		System.out.println();
	}
	public void insert(int x)
	{
		Node newNode = new Node(x);
		if(this.isEmpty())
		{
			first = newNode;
			last = newNode;
		}
		else
		{
			last.next = newNode;
			last = newNode;
		}
	}
}
class  ClassWork_1110832059_1205_Graph
{
	public static int run[] = new int[7];
	public static GraphLink Head[] = new GraphLink[7];
	public static String station[] = {"","TP","KCG","TT","TN","TC"};
	public static void Dfs(int current)
	{
		run[current] = 1;
		System.out.print("[" + station[current] + "]");

		while((Head[current].first) != null)
		{
			if (run[Head[current].first.x] == 0)
			{
				Dfs(Head[current].first.x);
			}
			Head[current].first = Head[current].first.next;
		}
	}
	public static void main(String[] args) 
	{
		//String station[] = {"TP","KCG","TT","TN","TC"};
		int StopStep[][] = {{1,2},{2,1},{2,3},{3,2},{2,4},{4,2},{1,3},{3,1},{4,5},{5,4},{1,5},{5,1}};

		int StopCipher;
		int j,i;
	
		System.out.println("圖形的鄰接串列內容：");
		for(i = 1; i < 6; i++)
		{
			run[i] = 0;
			Head[i] = new GraphLink();
			System.out.print("停靠站：" + station[i] + " => ");
			for (j = 0; j < 12 ; j ++)
			{

				//System.out.println("CipherStop == " + j + "||" + i);
				if(StopStep[j][0] == i)
				{
					//System.out.println("Cipher == " + j + "||" + i);
					StopCipher = StopStep[j][1];
					//System.out.println("Header == " + i);
					Head[i].insert(StopCipher);
				}
			}
			Head[i].print();
		}
		System.out.println("走訪頂點： ");
		Dfs(1);
		System.out.println("");
	}
}

## 結果圖示

## 用書資訊：
>書名：圖解資料結構 使用java（第三版）
>作者：吳燦銘、胡昭民
>出版社：博碩文化
>出版年份：2018年05月