一肄扎、術(shù)語
圖：由有窮、非空點(diǎn)集和邊集合組成腰涧，簡(jiǎn)寫成G(V頂點(diǎn),E邊);
無向圖：圖中每條邊都沒有方向韧掩；
有向圖：圖中每條邊都有方向；
無向邊：邊是沒有方向的窖铡，寫為(a,b)
有向邊：邊是有方向的疗锐，寫為<a,b>
有向邊也成為弧费彼；開始頂點(diǎn)稱為弧尾滑臊，結(jié)束頂點(diǎn)稱為弧頭；
簡(jiǎn)單圖：不存在指向自己的邊箍铲、不存在兩條重復(fù)的邊的圖雇卷；
無向完全圖：每個(gè)頂點(diǎn)之間都有一條邊的無向圖；
有向完全圖：每個(gè)頂點(diǎn)之間都有兩條互為相反的邊的無向圖颠猴；
稀疏圖：邊相對(duì)于頂點(diǎn)來說很少的圖关划；
稠密圖：邊很多的圖；
權(quán)重：圖中的邊可能會(huì)帶有一個(gè)權(quán)重翘瓮，為了區(qū)分邊的長(zhǎng)短贮折；
網(wǎng)：帶有權(quán)重的圖；
度：與特定頂點(diǎn)相連接的邊數(shù)资盅；
出度脱货、入度：對(duì)于有向圖的概念岛都，出度表示此頂點(diǎn)為起點(diǎn)的邊的數(shù)目，入度表示此頂點(diǎn)為終點(diǎn)的邊的數(shù)目振峻；
環(huán)：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑臼疫；
簡(jiǎn)單環(huán)：除去第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)后沒有重復(fù)頂點(diǎn)的環(huán)；
連通圖：任意兩個(gè)頂點(diǎn)都相互連通的圖扣孟；
極大連通子圖：包含竟可能多的頂點(diǎn)（必須是連通的）烫堤，即找不到另外一個(gè)頂點(diǎn)，使得此頂點(diǎn)能夠連接到此極大連通子圖的任意一個(gè)頂點(diǎn)凤价；
連通分量：極大連通子圖的數(shù)量鸽斟；
強(qiáng)連通圖：此為有向圖的概念，表示任意兩個(gè)頂點(diǎn)a利诺，b富蓄，使得a能夠連接到b，b也能連接到a 的圖慢逾；
生成樹：n個(gè)頂點(diǎn)立倍，n-1條邊，并且保證n個(gè)頂點(diǎn)相互連通（不存在環(huán)）侣滩；
最小生成樹：此生成樹的邊的權(quán)重之和是所有生成樹中最小的口注；
AOV網(wǎng)：結(jié)點(diǎn)表示活動(dòng)的網(wǎng)；
AOE網(wǎng)：邊表示活動(dòng)的持續(xù)時(shí)間的網(wǎng)君珠；
二寝志、圖的存儲(chǔ)結(jié)構(gòu)
1.鄰接矩陣
維持一個(gè)二維數(shù)組，Array[i][j]表示i到j(luò)的邊策添，如果兩頂點(diǎn)之間存在邊材部，則為1，否則為0唯竹；
維持一個(gè)一維數(shù)組败富，存儲(chǔ)頂點(diǎn)信息，比如頂點(diǎn)的名字摩窃；
下圖為一般的有向圖：
注意：如果我們要看vi節(jié)點(diǎn)鄰接的點(diǎn)兽叮，則只需要遍歷arr[i]即可；
下圖為帶有權(quán)重的圖的鄰接矩陣表示法：
缺點(diǎn)：鄰接矩陣表示法對(duì)于稀疏圖來說不合理猾愿，因?yàn)樘速M(fèi)空間鹦聪；
2.鄰接表
如果圖示一般的圖，則如下圖：
如果是網(wǎng)蒂秘，即邊帶有權(quán)值泽本，則如下圖：
3.十字鏈表
只針對(duì)有向圖；姻僧，適用于計(jì)算出度和入度规丽；
頂點(diǎn)結(jié)點(diǎn)：
邊結(jié)點(diǎn)：
好處：創(chuàng)建的時(shí)間復(fù)雜度和鄰接鏈表相同蒲牧，但是能夠同時(shí)計(jì)算入度和出度；
4.鄰接多重表
針對(duì)無向圖赌莺； 如果我們只是單純對(duì)節(jié)點(diǎn)進(jìn)行操作冰抢，則鄰接表是一個(gè)很好的選擇，但是如果我們要在鄰接表中刪除一條邊艘狭，則需要?jiǎng)h除四個(gè)頂點(diǎn)（因?yàn)闊o向圖）挎扰；
在鄰接多重表中，只需要?jiǎng)h除一個(gè)節(jié)點(diǎn)巢音，即可完成邊的刪除遵倦，因此比較方便；
因此鄰接多重表適用于對(duì)邊進(jìn)行刪除的操作官撼；
頂點(diǎn)節(jié)點(diǎn)和鄰接表沒區(qū)別梧躺，邊表節(jié)點(diǎn)如下圖：
比如：
5.邊集數(shù)組
適合依次對(duì)邊進(jìn)行操作；
存儲(chǔ)邊的信息傲绣，如下圖：
三掠哥、圖的遍歷
1.深度遍歷
/**
* O(v+e)
*/
@Test
public void DFS() {
for (int i = 0; i < g.nodes.length; i++) {
if (!visited[i]) {
DFS_Traverse(g, i);
}
}
}
private void DFS_Traverse(Graph2 g, int i) {
visited[i] = true;
System.out.println(i);
EdgeNode node = g.nodes[i].next;
while (node != null) {
if (!visited[node.idx]) {
DFS_Traverse(g, node.idx);
}
node = node.next;
}
}
2.廣度遍歷
/**
* O(v+e)
*/
@Test
public void BFS() {
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < g.nodes.length; i++) {
if (!visited[i]) {
visited[i] = true;
list.add(i);
System.out.println(i);
while (!list.isEmpty()) {
int k = list.remove(0);
EdgeNode current = g.nodes[k].next;
while (current != null) {
if (!visited[current.idx]) {
visited[current.idx] = true;
System.out.println(current.idx);
list.add(current.idx);
}
current = current.next;
}
}
}
}
}
四、最小生成樹
1.Prim
鄰接矩陣存儲(chǔ)斜筐；
* 時(shí)間復(fù)雜度為O(n^2)
* 適用于稠密圖
*/
@Test
public void prim(){
int cost[] = new int[9];
int pre[] = new int[9];
for(int i=0;i<g1.vertex.length;i++){
cost[i] = g1.adjMatrix[0][i];
}
cost[0] = 0;
for(int i=1;i<g1.vertex.length;i++){
int min = 65536;
int k = 0;
for(int j=1;j<g1.vertex.length;j++){
if(cost[j]!=0&&cost[j]<min){
min = cost[j];
k = j;
}
}
cost[k] = 0;
System.out.println(pre[k]+","+k);
for(int j=1;j<g1.vertex.length;j++){
if(cost[j]!=0&&g1.adjMatrix[k][j]<cost[j]){
pre[j] = k;
cost[j] = g1.adjMatrix[k][j];
}
}
}
}
2.Krustral
邊集數(shù)組存儲(chǔ)；
* 時(shí)間復(fù)雜度：O(eloge)
* 適用于稀疏圖
*/
@Test
public void krustral(){
Edge[] edges = initEdges();
int parent[] = new int[9];
for(int i=0;i<edges.length;i++){
Edge edge = edges[i];
int m = find(parent,edge.begin);
int n = find(parent,edge.end);
if(m!=n){
parent[m] = n;
System.out.println(m+","+n);
}
}
}
private static int find(int[] parent, int f) {
while (parent[f] > 0) {
f = parent[f];
}
return f;
}
五蛀缝、最短路徑
Dijkstra算法
鄰接矩陣存儲(chǔ)顷链；
public void Dijkstra(){
int distance[] = new int[9];
int pre[] = new int[9];
boolean finished[] = new boolean[9];
finished[0] = true;
for(int i=0;i<9;i++){
distance[i] = g1.adjMatrix[0][i];
}
int k = 0;
for(int i=1;i<9;i++){
int min = 65536;
for(int j=0;j<9;j++){
if(!finished[j]&&distance[j]<min){
min = distance[j];
k = j;
}
}
finished[k] = true;
System.out.println(pre[k]+","+k);
for(int j=1;j<9;j++){
if(!finished[j]&&(min+g1.adjMatrix[k][j])<distance[j]){
distance[j] = min+g1.adjMatrix[k][j];
pre[j] = k;
}
}
}
}
2.Floyd
使用：
(1)鄰接矩陣：存儲(chǔ)圖；
* O(n^3)
* 求出任意頂點(diǎn)之間的距離
*/
@Test
public void floyd(Graph1 g) {
int i, j, k;
int length = g.vertex.length;
int dist[][] = new int[length][length];
int pre[][] = new int[length][length];
for (i = 0; i < g.vertex.length; i++) {
for (j = 0; j < g.vertex.length; j++) {
pre[i][j] = j;
dist[i][j] = g.adjMatrix[i][j];
}
}
for (i = 0; i < length; i++) {
for (j = 0; j < g.vertex.length; j++) {
for (k = 0; k < g.vertex.length; k++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
pre[i][j] = pre[i][k];
}
}
}
}
System.out.println();
}
六屈梁、拓?fù)渑判?/h4>
使用數(shù)據(jù)結(jié)構(gòu)：
(1)棧：用來存放入度為0的節(jié)點(diǎn)嗤练；
(2)變種鄰接列表：作為圖的存儲(chǔ)結(jié)構(gòu)；此鄰接列表的頂點(diǎn)節(jié)點(diǎn)還需要存放入度屬性在讶；
/**
* O(n+e)
*/
private static String topologicalSort(Graph2 g2) {
Stack<Integer> s = new Stack<Integer>();
int count = 0;
for(int i=0;i<g2.nodes.length;i++){
if(g2.nodes[i].indegree==0){
s.push(i);
}
}
while(!s.isEmpty()){
int value = s.pop();
System.out.println(value+"煞抬、");
count++;
EdgeNode node = g2.nodes[value].next;
while(node!=null){
g2.nodes[node.idx].indegree--;
if(g2.nodes[node.idx].indegree==0){
s.push(node.idx);
}
node = node.next;
}
}
if(count<g2.nodes.length){
return "error";
}
return "ok";
}
七、關(guān)鍵路徑
使用數(shù)據(jù)結(jié)構(gòu)：
(1)變種鄰接列表：同拓?fù)渑判颍?br>
(2)變量：
ltv表示某個(gè)事件的最晚開始時(shí)間构哺；
etv表示事件最早開始時(shí)間革答；
ete表示活動(dòng)最早開始時(shí)間；
lte表示活動(dòng)最晚開始時(shí)間曙强；
public void CriticalPath(){
Stack<Integer> stack = topological_etv();
int length = stack.size();
if(stack==null){
return ;
}
else{
int[]ltv = new int[length];
for(int i=0;i<stack.size();i++){
ltv[i] = etv[stack.size()-1];
}
//從拓?fù)渑判虻淖詈箝_始計(jì)算ltv
while(!stack.isEmpty()){
int top = stack.pop();
EdgeNode current = g.nodes[top].next;
while(current!=null){
int idx = current.idx;
//最晚發(fā)生時(shí)間要取所有活動(dòng)中最早的
if((ltv[idx]-current.weight)<ltv[top]){
ltv[top] = ltv[idx]-current.weight;
}
}
}
int ete = 0;
int lte = 0;
for(int j=0;j<length;j++){
EdgeNode current = g.nodes[j].next;
while(current!=null){
int idx = current.idx;
ete = etv[j];
lte = ltv[idx]-current.weight;
if(ete==lte){
//是關(guān)鍵路徑
}
}
}
}
}
private Stack<Integer> topological_etv(){
Stack<Integer> stack2 = new Stack<Integer>();
Stack<Integer>stack1 = new Stack<Integer>();
for(int i=0;i<g.nodes.length;i++){
if(g.nodes[i].indegree==0){
stack1.add(i);
}
}
etv[] = new int[g.nodes.length];
int count = 0;
while(!stack1.isEmpty()){
int top = stack1.pop();
count++;
stack2.push(top);
EdgeNode current = g.nodes[top].next;
while(current!=null){
int idx = current.idx;
if((--g.nodes[idx].indegree)==0){
stack1.push(idx);
}
if((etv[top]+current.weight)>etv[idx]){
etv[idx] = etv[top]+current.weight;
}
current = current.next;
}
}
if(count<g.nodes.length){
return null;
}
return stack2;
}
