有向权图的邻接矩阵的存储结构

图：图是由顶点集合V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为G=（V，E）。

有向图：如果用箭头标明了边是有方向性的，则这样的图称为有向图。

弧：有向边也称为弧。<x，y>表示从顶点x发向顶点y的边。

权：在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离，费用等，带权图一般称为网。

 

下面是一个示例的有向权图：

 

 

这是有向权图的顶点存储数组和邻接矩阵：

 

 

下面是C语言的代码，把这个有向权图存储了起来：

 

#include <stdio.h>
#define N 5 // 图中的顶点数
#define E 9 // 图中的边数

struct graph {
	int V[N]; // 存放顶点的信息
	int arcs[N][N]; // 邻接矩阵
};

void main() {

	int i, j;
	struct graph g = {
		{ 0, 1, 2, 3, 4 },
		{ 0 }
	};

	// 初始化所有顶点之间都没有弧，权都为-1
	for(i = 0; i < N; i++) {
		for(j = 0; j < N; j++) {
			if(i != j) {
				g.arcs[i][j] = -1;	
			}
		}
	}

	// 存储图中的9条边
	g.arcs[0][1] = 3;
	g.arcs[0][4] = 5;

	g.arcs[1][2] = 25;
	g.arcs[1][3] = 8;
	
	g.arcs[2][4] = 10;
	
	g.arcs[3][0] = 20;
	g.arcs[3][2] = 4;
	g.arcs[3][4] = 12;

	g.arcs[4][0] = 30;

	// 输出矩阵
	for(i = 0; i < N; i++) {
		for(j = 0; j < N; j++) {
			printf("%d\t", g.arcs[i][j]);
		}
		printf("\n");
	}
}

 

 

评论

1 楼 油炸大龙虾 2010-07-21  

头大- -！