图的遍历及最小生成树（prim，kruskal）的实现

关于图的介绍网上很多，这里就不介绍了，直接上代码：
最小生成树算法可以看看：http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html

#include <iostream>
#include <iomanip>
#include <climits>
#include <queue>
using namespace std;

#define MAX_VERTEX_NUM 20 // 顶点数量上限 
typedef char VerType;      // 顶点结构 , 顶点的字母名称 
typedef int ArcType;       // 边的结构 , 权值 
typedef enum {DG, UDG} GKind;  // 图类型，{有向图,无向图}

// 图的存储结构 
typedef struct
{
int verNum, arcNum;  // 顶点数量, 边数量 
    GKind kind;          // 图类型 
    VerType vertex[MAX_VERTEX_NUM];                 //顶点
    ArcType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];   //边 
}Graph;


void CreateGraphByArray(Graph &G);                 // 创建图G (通过预定义的数组)
void CreateGraph(Graph &G);                        // 创建图G (通过输入)
int  VertexLoc(const Graph &G, const VerType &v);  // 获取顶点v在图G中的位置 
void PrintGraphArcs(const Graph &G);               // 输出图G邻接矩阵
void DFS(const Graph G, int vi, bool visited[]);   // 图G的深度优先遍历的准备 
void DFS_Traverse(const Graph &G);                 // 图G的深度优先遍历
void BFS_Traverse(const Graph &G);                 // 图G的广度优先遍历
void MinSpanTree_Prim(const Graph &G);             // 输出图G最小生成树 (Prim算法)
void MinSpanTree_Kruskal(const Graph &G);          // 输出图G最小生成树 (kruskal算法)


int main()
{
    Graph G;
//CreateGraph(G);
    CreateGraphByArray(G);

cout << "图的邻接矩阵: " << endl;
    PrintGraphArcs(G);

cout << "图的深度优先遍历：";
    DFS_Traverse(G);
cout << endl;

cout << "图的广度优先遍历：";
    BFS_Traverse(G);
cout << endl;

cout << "最小生成树：（prim算法）"  << endl;
    MinSpanTree_Prim(G);
cout << endl;

cout << "最小生成树：（kruskal算法）"  << endl;
    MinSpanTree_Kruskal(G);
cout << endl;
return 0;
}


void CreateGraphByArray(Graph &G)
{
//数据例子取自课本Page168
    G.kind = UDG;

const int vn = 6;
    VerType V[vn + 1] = {"ABCDEF"};

const int en = 10;
    VerType V1[en + 1] = {"ADFEBADFEB"};
    VerType V2[en + 1] = {"CCCCCDFEBA"};
    ArcType E[en] = {1,5,4,6,5,5,2,6,3,6};


// 输入顶点 
    G.verNum = vn;
for(int i = 0; i < G.verNum; ++ i){
        G.vertex[i] = V[i];
    }

// 初始化邻接矩阵 
for(int vi = 0; vi < G.verNum; ++ vi){
for(int vj = 0; vj < G.verNum; ++ vj){
            G.arcs[vi][vj] = INT_MAX;
        }
    }

// 输入边 
    G.arcNum = en;
for(int i = 0; i < G.arcNum; ++ i){
        VerType &v1 = V1[i], &v2 = V2[i];
        ArcType &e = E[i];
int vi = VertexLoc(G, v1), vj = VertexLoc(G, v2);
if(vi == G.verNum || vj == G.verNum){
continue;
        }
if(UDG == G.kind){
            G.arcs[vi][vj] = G.arcs[vj][vi] = e;
        }else{
            G.arcs[vi][vj] = e;
        }
    }
}


void CreateGraph(Graph &G)
{
// 输入图类型 
int k;
cin >> k;
if(k == 0){
        G.kind = DG;
    }else{
        G.kind = UDG;
    }

// 输入顶点 
cin >> G.verNum;
for(int i = 0; i < G.verNum; ++ i){
cin >> G.vertex[i];
    }

// 初始化邻接矩阵 
for(int vi = 0; vi < G.verNum; ++ vi){
for(int vj = 0; vj < G.verNum; ++ vj){
            G.arcs[vi][vj] = INT_MAX;
        }
    }

// 输入边 
    VerType v1, v2; ArcType e;
cin >> G.arcNum;
for(int i = 0; i < G.arcNum; ++ i){
cin >> v1 >> v2 >> e;
int vi = VertexLoc(G, v1), vj = VertexLoc(G, v2);
if(vi == G.verNum || vj == G.verNum){
continue;
        }
if(UDG == G.kind){
            G.arcs[vi][vj] = G.arcs[vj][vi] = e;
        }else{
            G.arcs[vi][vj] = e;
        }
    }
}


int VertexLoc(const Graph &G, const VerType &v)
{
for(int i = 0; i < G.verNum; ++ i){
if(G.vertex[i] == v){
return i;
        }
    }
return G.verNum;
}


void PrintGraphArcs(const Graph &G)
{
for(int vi = 0; vi < G.verNum; ++ vi){
for(int vj = 0; vj < G.verNum; ++ vj){
if(G.arcs[vi][vj] == INT_MAX){
cout << setw(5) << "INF";
            }else{
cout << setw(5) << G.arcs[vi][vj];
            }
        }
cout << endl;
    }
}


void DFS(const Graph G, int vi, bool visited[])
{
cout << G.vertex[vi] << " ";
    visited[vi] = true;
for(int vj = 0; vj < G.verNum; ++ vj){
if(G.arcs[vi][vj] != INT_MAX && !visited[vj]){
            DFS(G, vj, visited);
        }
    }
}

void DFS_Traverse(const Graph &G)
{
bool visited[G.verNum];
for(int vi = 0; vi < G.verNum; ++ vi){
        visited[vi] = false;
    }

for(int vi = 0; vi < G.verNum; ++ vi){
if(!visited[vi]){
            DFS(G, vi, visited);
        }
    }
}


void BFS_Traverse(const Graph &G)
{
bool visited[G.verNum];
for(int i = 0; i < G.verNum; ++ i){
        visited[i] = false;
    }

for(int i = 0; i < G.verNum; ++ i){
if(!visited[i]){
queue<int> que;
            que.push(i);
            visited[i] = true;

while(!que.empty()){
int vi = que.front();
cout << G.vertex[vi] << " ";
for(int vj = 0; vj < G.verNum; ++ vj){
if(G.arcs[vi][vj] != INT_MAX && !visited[vj]){
                        que.push(vj);
                        visited[vj] = true;
                    }
                }
                que.pop();
            }
        }
    }
}

void MinSpanTree_Prim(const Graph &G)
{
//辅助结构, closeedge[i]={j, w}表示顶点vi权值最小的边，vj为边顶点, w为权值 
struct
    {
int adjvex;        // 最小边顶点 
        ArcType lowcost;   // 最小边上的权值 
    }closedge[G.verNum];

int k = 0;
for(int j = 0; j < G.verNum; ++ j){
if(j != k){
            closedge[j] = {k, G.arcs[k][j]};
        }
    }
    closedge[k].lowcost = 0;  //表示顶点已经被选入Enew 

for(int i = 1; i < G.verNum; ++ i){

/* 从Vnew选取权值最小的边 */
        k = -1;
for(int j = 0; j < G.verNum; ++ j){
if(closedge[j].lowcost != 0){
if(k == -1){
                    k = j;
                }else if(closedge[j].lowcost < closedge[k].lowcost){
                    k = j;
                }
            }
        }

int v0 = k, u0 = closedge[k].adjvex;
cout << G.vertex[u0] << " - " << G.vertex[v0] << endl;  //输出边 

        closedge[k].lowcost = 0;  //将该顶点选入Enew 

/* 更新与新顶点相连的顶点最小权值 */
for(int j = 0; j < G.verNum; ++ j){
if(G.arcs[k][j] < closedge[j].lowcost){
                closedge[j] = {k, G.arcs[k][j]};
            }
        }
    }
}


void MinSpanTree_Kruskal(const Graph &G)
{
//辅助数组 (kruskal算法)
struct
    {
int head;     // 边的起点 
int tail;     // 边的终点 
        ArcType lowcost;  // 边上的权值 
    }edge[G.arcNum], temp;

//初始化edge
if(UDG == G.kind){
for(int i = 0, vi = 0; vi < G.verNum; ++ vi){
for(int vj = 0; vj < vi; ++ vj){
if(G.arcs[vi][vj] != INT_MAX){
                    edge[i].head = vi;
                    edge[i].tail = vj;
                    edge[i ++].lowcost = G.arcs[vi][vj];
                }
            }
        }
    }else{
for(int i = 0, vi = 0; vi < G.verNum; ++ vi){
for(int vj = 0; vj < G.verNum; ++ vj){
if(G.arcs[vi][vj] != INT_MAX){
                    edge[i].head = vi;
                    edge[i].tail = vj;
                    edge[i ++].lowcost = G.arcs[vi][vj];
                }
            }
        }
    }

//并根据权值从小到大排序
for(int i = 1; i <= G.arcNum; ++ i){
for(int j = 0; j < G.arcNum - i; ++ j){
if(edge[j].lowcost > edge[j + 1].lowcost){
                temp = edge[j];
                edge[j] = edge[j + 1];
                edge[j + 1] = temp;
            }
        }
    }

int vexset[G.verNum];
for(int i = 0; i < G.verNum; ++ i){
        vexset[i] = i;
    }

for(int i = 0; i < G.arcNum; ++ i){
int vi = edge[i].head, vj = edge[i].tail;
int vs1 = vexset[vi], vs2 = vexset[vj];
if(vs1 != vs2){
cout << G.vertex[vi] << " - " << G.vertex[vj] << endl;
for(int j = 0; j < G.verNum; ++ j){
if(vexset[j] == vs2){
                    vexset[j] = vs1;
                }
            }
        }
    }
}

---

对于这个图：

最小生成树的图形为：

---

所运行的结果如下：