图的建立——邻接矩阵

通过邻接矩阵的方式建立图

邻接矩阵(Adjacency Matrix)的存储结构就是通过一维数组存储图中顶点的信息，用矩阵表示图中各个顶点的的临界关系，而矩阵通过一个二维数组表示。

图的分类

在矩阵中的表示方法

在无向图中矩阵的表示

无向网中矩阵的表示

存储顶点信息的结构

存储图的信息时，要通过结构体来定义数据类型，以无向网为例定义如下：

	#define MAX_VEX 100            // 图中含有顶点的最多个数
	#define INF 65535              //如果两个顶点之间不可达，用无穷表示距离
	struct Graph{
	    char vexs[MAX_VEX];        //代表顶点信息的名称
	    int arc[MAX_VEX][MAX_VEX]; //两个顶点之间的权值
	    int numvex;			       // 表示顶点的个数
		int	numarc;		           // 边的个数
	};

图信息的初始化

	void CreateGraph(Graph &G){
	    int vi, vj, w;
	    cout << "please enter the number of vertexes and arcs : \n";
	    cin >> G.numvex >> G.numarc;                       //输入顶点与边的个数
	    for(int i = 0; i < G.numvex; i++){			      //为每个顶点初始化信息
	        printf("Please enter the NO.%d name of vex : ",i+1);
	        cin >> G.vexs[i];
	    }
	    for(int i = 0; i < G.numvex; i++){			     //初始化顶点之间的权值 默认为无穷
	        for(int j = 0; j < G.numvex ;j++){
	            G.arc[i][j] = INF;
	        }
	    }
	    cout << endl;
	    for(int i = 0; i < G.numarc; i++){			    //根据边的条数，为每一条边赋值
	        cout<< "Enter the subscripts and weights from vertex vi to vertex vj : ";
	        cin >> vi >> vj >> w;
	        G.arc[vi][vj] = w;					       //在无向网中满足图对称性，即Vi-Vj 和Vj-Vi的距离相等，实际就是一条路径
	        G.arc[vj][vi] = w;
	    }
	}

完整实现过程：

	#include <iostream>
	#include <cstdio>
	#define MAX_VEX 100
	#define INF 65535
	
	using namespace std;
	struct Graph{
	    char vexs[MAX_VEX];
	    int arc[MAX_VEX][MAX_VEX];
	    int numvex,numarc;
	};
	void CreateGraph(Graph &G){
	    int vi, vj, w;
	    cout << "please enter the number of vertexes and arcs : \n";
	    cin >> G.numvex >> G.numarc;
	    for(int i = 0; i < G.numvex; i++){
	        printf("Please enter the NO.%d name of vex : ",i+1);
	        cin >> G.vexs[i];
	    }
	    for(int i = 0; i < G.numvex; i++){
	        for(int j = 0; j < G.numvex ;j++){
	            G.arc[i][j] = INF;
	        }
	    }
	    cout << endl;
	    for(int i = 0; i < G.numarc; i++){
	        cout<< "Enter the subscripts and weights from vertex vi to vertex vj : ";
	        cin >> vi >> vj >> w;
	        G.arc[vi][vj] = w;
	        G.arc[vj][vi] = w;
	    }
	}
	void DispalyGraph(Graph G){
	    for(int i = 0; i < G.numvex; i++) cout << G.vexs[i] << " ";
	    cout << endl;
	    for(int i = 0; i < G.numvex; i++){
	        for(int j = 0; j < G.numvex; j++){
	            if(G.arc[i][j] == INF) printf("%6s", "∞");
	            else printf("%6d", G.arc[i][j]);
	        }
	        cout << endl;
	    }
	}
	int main(){
	    Graph G;
	    CreateGraph(G);
	    DispalyGraph(G);
	    return 0;
	}

实现结果

以下面的无向网为例：

• 所有的顶点信息
  顶点个数为9 边数为 16
  边信息：
  0 1 1
  0 2 5
  1 3 7
  1 4 5
  4 2 1
  2 3 7
  3 6 3
  6 4 6
  4 7 9
  7 5 5
  6 8 7
  7 8 4
  1 2 3
  3 4 2
  4 5 3
  6 7 2