資料結構-圖的鄰接矩陣表示
包含圖的結構實作和相關的一些重要算法實作
typedef struct ENode* PtrToENode;
struct ENode{
Vertex V1,V2; //有向邊<V1,V2>
WeightType Weight; //權重
};
typedef struct GNode* PtrToGNode;
struct GNode{
int Nv; //頂點數
int Ne; //邊數
WeightType G[MaxVertexNum][MaxVertexNum]; //鄰接矩陣
DataType Data[MaxVertexNum]; //存頂點的資料
//注意：很多情況下，頂點無資料，此時Data[]可以不用出現
};
typedef PtrToGNode MGraph; //以鄰接矩陣存儲的圖類型
#include<iostream>
#include<queue>
using namespace std;
/*圖的臨界矩陣表示法*/
#define ERROR -1
#define MaxVertexNum 100 //最大頂點數設為100
#define INFINITY 65536 //設為雙位元組無符号整數的最大值65535
typedef int Vertex; //用頂點下标表示頂點，為整形
typedef int WeightType; //邊的權值設為整形
typedef char DataType; //頂點存儲的資料結構設為字元型
bool Visited[MaxVertexNum]={false};
/*邊的定義*/
typedef struct ENode* PtrToENode;
struct ENode{
Vertex V1,V2; //有向邊<V1,V2>
WeightType Weight; //權重
};
typedef PtrToENode Edge;
/*圖結點的定義*/
typedef struct GNode* PtrToGNode;
struct GNode{
int Nv; //頂點數
int Ne; //邊數
WeightType G[MaxVertexNum][MaxVertexNum]; //鄰接矩陣
DataType Data[MaxVertexNum]; //存頂點的資料
//注意：很多情況下，頂點無資料，此時Data[]可以不用出現
};
typedef PtrToGNode MGraph; //以鄰接矩陣存儲的圖類型
MGraph CreateGraph(int VertexNum){
/*初始化一個有VertexNum個頂點但沒有邊的圖*/
Vertex V,W;
MGraph Graph;
Graph=(MGraph)malloc(sizeof(struct GNode));
Graph->Ne=0;
Graph->Nv=VertexNum;
/*初始化鄰接矩陣*/
/*注意：這裡預設頂點編号從0開始，到(Graph->Nv-1)*/
for(V=0;V<Graph->Nv;V++)
for(W=0;W<Graph->Nv;W++)
Graph->G[V][W]=INFINITY;
return Graph;
}
void InsertEdge(MGraph Graph,Edge E){
/*插入邊*/
Graph->G[E->V1][E->V2]=E->Weight;
/*若是無向圖，還要插入邊<V2,V1>*/
Graph->G[E->V2][E->V2]=E->Weight;
}
MGraph BuildGraph(){
MGraph Graph;
Edge E;
Vertex V;
int Nv,i;
scanf("%d",&Nv); /*讀入頂點個數*/
Graph=CreateGraph(Nv); /*初始化有Nv個頂點但沒有邊的圖*/
scanf("%d",&(Graph->Ne)); /*讀入邊數*/
if(Graph->Ne!=0){
E=(Edge)malloc(sizeof(struct ENode));
/*讀入邊，格式為“起點 終點 權重”，插入鄰接矩陣*/
for(i=0;i<Graph->Ne;i++)
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
/*注意：如果權重不是整形，Weight的讀入格式要改*/
InsertEdge(Graph,E);
}
for(V=0;V<Graph->Nv;V++){
scanf("%c",&(Graph->Data[V]));
}
return Graph;
}
void Visit(Vertex V){
printf("正在通路頂點%d\n",V);
}
/*鄰接矩陣存儲的圖 - BFS*/
/*IsEdge(Graph ,V,W)檢查<V,W>是否圖Graph中的一條邊，即W是否V的鄰接點。*/
/*此函數根據圖的不同類型要做不同的實作，關鍵取決于對不存在的邊的表示法*/
/*例如對有權圖，如果不存在的邊被初始化為INFINITY,則函數實作如下:*/
bool IsEdge(MGraph Graph,Vertex V,Vertex W){
return Graph->G[V][W]<INFINITY ?true :false;
}
void BFS(MGraph Graph,Vertex S,void(*Visit)(Vertex)){
/*以S為出發點對臨界矩陣存儲的圖Graph進行BFS搜尋*/
queue<int>Q;
Vertex V,W;
Visit(S);
Visited[S]=true;
Q.push(S);
while(!Q.empty()){
V=Q.front();
Q.pop();
for(W=0;W<Graph->Nv;W++){
if(!Visited[W]&&IsEdge(Graph,V,W)){
Visit(W);
Visited[W]=true;
Q.push(W);
}
}
}
}
/*鄰接矩陣存儲 - 有權圖的單源最短路徑算法*/
Vertex FindMinDist(MGraph Graph,int dist[],int collected[]){
/*傳回未被收錄頂點中dist最小者*/
Vertex MinV,V;
int MinDist=INFINITY;
for(V=0;V<Graph->Nv;V++){
if(collected[V]==false&&dist[V]<MinDist){
/*若V未被收錄，且dist[V]更小*/
MinDist=dist[V];/*更新最小距離*/
MinV=V;/*更新對應頂點*/
}
}
if(MinDist<INFINITY)/*若找到最小dist*/
return MinV; /*傳回對應的頂點下标*/
else
return -1; /*若這樣的頂點不存在，傳回錯誤标記*/
}
bool Dijkstra(MGraph Graph,int dist[],int path[],Vertex S){
int collected[MaxVertexNum];
Vertex V,W;
/*初始化：此處預設鄰接矩陣中不存在的邊用INFINITY*/
for(V=0;V<Graph->Nv;V++){
dist[V]=Graph->G[S][V];
if(dist[V]<INFINITY)
path[V]=S;
else
path[V]=-1;
collected[V]=false;
}
/*先将起點收入集合*/
dist[S]=0;
collected[S]=true;
while(1){
/*V=未被收錄頂點中dist最小者*/
V=FindMinDist(Graph,dist,collected);
if(V==-1) /*若這樣的V不存在*/
break;/*算法結束*/
collected[V]=true; /*收錄V*/
for(W=0;W<Graph->Nv;W++){/*對圖中的沒一個頂點W*/
/*若W是V的鄰接點并且未被收錄*/
if(!collected[W]&&Graph->G[V][W]<INFINITY){
if(Graph->G[V][W]<0) /*若有負邊*/
return false; /*不能正常解決問題傳回錯誤标記*/
/*若收錄V是的dist[W]變小*/
if(dist[V]+Graph->G[V][W]<dist[W]){
dist[W]=dist[V]+Graph->G[V][W];/*更新dist[W]*/
path[W]=V;/*跟新S到W的路徑*/
}
}
}
} /*while結束*/
return true;/*算法執行完畢，傳回正确标記*/
}
/*鄰接矩陣 - 多源最短路徑算法*/
bool Floyd(MGraph Graph,WeightType D[][MaxVertexNum],Vertex path[][MaxVertexNum]){
Vertex i,j,k;
/*初始化*/
for(i=0;i<Graph->Nv;i++)
for(j=0;j<Graph->Nv;j++){
D[i][j]=Graph->G[i][j];
path[i][j]=-1;
}
for(k=0;k<Graph->Nv;k++)
for(i=0;i<Graph->Nv;i++)
for(j=0;j<Graph->Nv;j++){
if(D[i][k]+D[k][j]<D[i][j]){
D[i][j]=D[i][k]+D[k][j];
if(i==j&&D[i][j]<0)/*若發現負值圈*/
return false;/*不能正确解決，傳回錯誤标記*/
path[i][j]=k;
}
}
return true;/*算法執行完畢，傳回正确标記*/
}
/*鄰接矩陣 - Prim最小生成樹算法*/
Vertex FindMinDist(MGraph Graph,WeightType dist[]){
Vertex MinV,V;
WeightType MinDist=INFINITY;
for(V=0;V<Graph->Nv;V++){
if(dist[V]!=0&&dist[V]<MinDist){
/*若V未被收錄，且dist[V]更小*/
MinDist=dist[V];/*更新最小距離*/
MinV=V; /*更新對應頂點*/
}
}
if(MinDist<INFINITY)/*若找到最小dist*/
return MinV; /*傳回對應的頂點下标*/
else return ERROR; /*若這樣的頂點不存在，傳回-1作為标記*/
}
int Prim(MGraph Graph,LGraph MST){
/*将最小生成樹儲存為鄰接表存儲的圖MST，傳回最小權重和*/
WeightType dist[MaxVertexNum],TotalWeight;
Vertex parent[MaxVertexNum],V,W;
int Count;
Edge V;
/*初始化。預設初始點下标是0*/
for(V=0;V<Graph->Nv;V++){
/*假設若V到W沒有直接邊，則Graph->G[V][W]定義為INFINITY*/
dist[V]=Graph->G[0][V];
parent[V]=0;/*暫且定義所有頂點的父節點都是初始結點0*/
}
TotalWeight=0;/*初始化權重和*/
VCount =0; /*初始化收錄的頂點數*/
/*建立包含所有頂點但沒有邊的圖。注意用鄰接表版本*/
MST=CreateGraph(Graph->Nv);
E=(Edge)malloc(sizeof(struct ENode));/*建立空的邊結點*/
/*将初始化點0收進MST*/
dist[0]=0;
VCount++;
parent[0]=-1;/*目前樹根是0*/
while(1){
V=FindMinDist(Graph,dist);
/*V=未被收錄頂點中dist最小者*/
if(V==ERROR)/*若這樣的V不存在*/
break; /*算法結束*/
/*将V及相應的邊<parent[V],V>收錄進MST*/
E->V1=parent[V];
E->V2=V;
E->Weight=dist[V];
InsertEdge(MST,E);
TotalWeight+=dist[V];
dist[V]=0;
VCount++;
for(W=0;W<Graph->Nv;W++){
if(dist[W]!=0&&Graph->G[V][W]<INFINITY){
/*若W是V的鄰接點并且未被收錄*/
if(Graph->G[V][W]<dist[W]){
/*若收錄V使得dist[W]變小*/
dist[W]=Graph->G[V][W];/*更新dist[W]*/
parent[W]=V;/*更新樹*/
}
}
}
} /*while結束*/
if(VCount<Graph->Nv)/*MST中收錄的頂點不到|V|個*/
TotalWeight=ERROR;
return TotalWeight; /*算法執行完畢，傳回最小權重和或錯誤标記*/
}
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)