亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

頂點：??

頂點索引? ? ? ? ? ? ? ?出弧鏈表頭指針? ? ? ? ? ? ? ? ? ? ? ? ?頂點數據

? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?|

頂點索引? ? ? 第一個出弧的指針(可以是NULL)? ? ? ? ?頂點數據

弧的表示方法：

弧頭頂點索引? ? ? ? ? ? ? ? 下一條弧指針? ? ? ? ? ? ? ? ? 弧數據

????? ? ?|? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |

弧頭頂點(指向的點)? ? ? ? 一個點有多個弧? ? ? ? ? ? ? 弧數據

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?每個弧保存下一條弧的指針

鄰接表表達圖：

頂點和圖：

頂點保存點的索引和數據

圖保存頂點數組和鄰接矩陣

鄰接矩陣方法：

圖->數據

圖的存儲結構：

????鄰接矩陣(數組)

????鄰接表(鏈表)-->存儲有向圖

????十字鏈表(鏈表)-->存儲有向圖

????鄰接多重表(鏈表) -->無向圖

【圖的遍歷】深度優先搜索（前序遍歷）、廣度優先搜索（一層一層搜索）

【最小生成樹】普里姆Prim算法、克魯斯卡爾Kruskal算法

1、Prim算法

• 點集合

• 邊集合

• 待選邊集合

2、Kruskal算法

• 待選邊集合

• 已選邊集合

• 已涉及點集合
  

1、十字鏈表-鏈式存儲

• 頂點的表示：頂點索引+頂點數據+以該頂點為弧尾的弧節點指針+以該節點為弧頭的弧節點指針

• ?。夯∥岔旤c索引+弧頭頂點索引+弧尾相同的下一條弧的指針+弧頭相同的下一條弧的指針+弧的數據

• struct Arc{弧尾頂點索引；弧頭頂點索引；指向下一條弧頭相同的弧的指針；指向下一條弧尾相同的弧的指針；弧的數據；}

• struct Node{頂點索引；頂點數據；第一條入弧節點指針；第一條出弧節點指針；}

• struct Map{頂點數組；}

2、鄰接多重表-鏈式存儲（無向圖）

• 頂點：頂點索引+連接該頂點的邊+頂點數據

• 邊：A頂點索引+B頂點索引+與A頂點相連接的下一條邊的指針+與B頂點相連接的下一條邊的指針+邊的數據

• struct Edge{頂點A索引；頂點B索引；連接A的下一條邊的指針；連接B的下一條邊的指針；邊信息；}

• struct Node{頂點索引；頂點數據；第一條邊節點的指針；}

• struct Map{頂點數組；}
  

【圖的存儲結構】鄰接矩陣（用數組表達）、鄰接表（鏈表，有向圖）、十字鏈表（鏈表，有向圖）、鄰接多重表（鏈表，用于表達無向圖）

【權值】弧/邊上的數據（比如兩個城市之間的某條公路是300km）

1、鄰接矩陣

• 頂點的表示：頂點索引+頂點數據

• 有弧的用1表示，沒有弧的用0表示，自己和自己用0

• 

• int matrix[4][4];

• struct Node{頂點索引；頂點數據；}

• struct Map{頂點數組；鄰接矩陣；}

2、鄰接表-鏈式存儲

• 頂點的表示：頂點索引+出弧鏈表頭指針+頂點數據

• 弧：弧頭頂點索引+下一條弧指針+弧數據

• 逆鄰接表：記錄的是 入弧鏈表頭指針 和 弧尾頂點索引

• struct Node{頂點索引；該頂點弧鏈表的頭結點；頂點數據；}

• struct Arc{指向的頂點索引；指向下一條弧的指針；弧信息；}

• struct Map{頂點數組；}
  

【圖】無向圖、有向圖

【有向圖】每個節點都叫做“頂點”，頂點之間的有方向的連線叫做“弧”

• 方向箭頭的尾端：弧尾

• 方向箭頭的頭端：弧頭

• 某個頂點發射出去的箭頭數：出度（數）

• 某個頂點接受到的箭頭數：入度（數）

【無向圖】節點為“頂點”；節點間的連線是無方向的（即可以看做雙向的），叫做“邊”；由邊連接的兩個頂點為鄰接點

• 連通圖：每個頂點都有通往其他頂點的連線（直接/間接）

• 完全圖：任意頂點都與其他頂點有直接的連線，邊數=n(n-1)/2

• 生成樹：最少數量的邊連接每一個頂點，邊數=n-1

鄰接表與逆鄰接表:

頂點：頂點索引，出弧鏈表頭指針，頂點數據；

弧：弧頭頂點索引，嚇一跳弧指針，弧數據

頂點結構體：包括頂點索引和頂點數據;

圖的結構體：包括頂點數組和鄰接矩陣

頂點結構體：包括頂點索引和頂點數據就行 圖的結構體：包括頂點數組（記錄頂點）和鄰接矩陣（記錄邊，并且頂點和邊的關系）就行 鄰接表與逆鄰接表：相對于弧的出入頂點說的，如果存儲的是弧出頂點的就是鄰接表，如果存儲的是弧進頂點就是逆鄰接表

不用看第二遍

/**	
*?廣度優先遍歷	(java實現)
*/	
public?void?breadthFirstTraverse(int?nodeIndex)?{	
	System.out.print(NodeArray[nodeIndex].date+"??");	
	NodeArray[nodeIndex].isVistited?=?true;		
	Vector<Integer>?v1?=?new?Vector<Integer>();		
	v1.add(nodeIndex);		
	breadthFirst(v1);	
}		
public?void?breadthFirst(Vector<Integer>?v1)?{	
	int[]?value?=?new?int[1];		
	Vector<Integer>?v2?=?new?Vector<Integer>();		
	for(int?j?=?0;?j?<?(int)v1.size()?;?j++)?{			
	????for(int?i?=?0;?i?<?Capacity?;?i++)?{				
	????????getValueFromMatrix(v1.get(j),?i,?value);
	????????if(value[0]?!=?0)?{
	????	????if(NodeArray[i].isVistited)?{
	????	????????continue;
	????	????}else?{
	????	????????System.out.print(NodeArray[i].date+"??");
	????	????????NodeArray[i].isVistited?=?true;
	????	????????v2.add(i);
	????	????}
	????????}
	????}
?????}
?????if(v2.size()?==?0)?{
?????????return;
?????}else?{
?????????breadthFirst(v2);
?????}
}