内含完整程序和几组测试数据 /* 输入第一行： 顶点数 边 起点 接下来E行 起点 终点 权重 5 8 0 0 1 1 0 2 5 1 2 1 1 3 8 1 4 3 2 4 1 3 4 6 4 3 1 其中5表示有五个顶点； 8表示有八条边 0表示以0为起点 测试数据：见txt */ #include #include #define INF -1 long long** newMat(long long V); void printMat(long long** mat, long long length); void readMat(long long** mat, long long num); long long* dijkstra(long long** mat, long long length, long long r); int main(int argc, char const* argv[]) { long long V, E, r; long long i, j; scanf("%lld%lld%lld", &V, &E, &r); //初始化数组 long long** weight_mat = newMat(V); readMat(weight_mat, E); // printMat(weight_mat, V); dijkstra(weight_mat, V, r); return 0; } void printMat(long long** mat, long long length) { long long i, j; for (i = 0; i < length; i++) { for (j = 0; j < length; j++) { printf("%lld\t", mat[i][j]); } printf("\n"); } printf("\n"); } long long** newMat(long long V) { long long i, j; long long** mat = (long long**)malloc(sizeof(long long*) * V); for (i = 0; i < V; i++) { mat[i] = (long long*)malloc(sizeof(long long) * V); for (j = 0; j < V; j++) { mat[i][j] = INF; } mat[i][i] = 0; } return mat; } void readMat(long long** mat, long long num) { long long s, t, d; long long i; for (i = 0; i < num; i++) { scanf("%lld%lld%lld", &s, &t, &d); mat[s][t] = d; } } long long* dijkstra(long long** mat, long long length, long long r) { long long* distance = (long long*)malloc(sizeof(long long) * length); char mark[100000]; long long i, j, k, l, min; for (i = 0; i < length; i++) { distance[i] = mat[r][i]; mark[i] = 0; } mark[r] = 1; for (i = 1; i < length; i++) { //找到一个未使用的节点 min = length; for (j = 0; j < length; j++) { if (mark[j] || distance[j] == INF) { continue; } else {

两个表格，一个地理位置矩阵和处理好了的0-1矩阵，矩阵表格中，sheet1是邻接矩阵，sheet3是空间地理位置矩阵，都是处理过了可以直接用的

图的基本操作 1）理解邻接矩阵和邻接表的概念 2）任选一种存储方式实现以下操作：图的构造、深度优先遍历以及广度优先遍历

无向图的邻接矩阵表示

for (j = 1; j <= Pub.Vertexnum; j++) { if (Pub.color[j] == -1) Pub.color[j] = 0; for (i = 1; i <= Pub.Vertexnum; i++) { if (Pub.graphs[j, i] == 1) { if (Pub.color[i] == -1) { Pub.color[i] = 1 - Pub.color[j]; } else if (Pub.color[j] == Pub.color[i]) { return false; } } } } if (Pub.Vertexnum != 0 &&j==Pub.Vertexnum + 1) { return true; } else return false;

大学生，算法与数据结构的里的课后实验。

适合正在准备毕业论文或是相关学术研究的人员

图的遍历（包括深度 广度遍历 利用邻接矩阵 利用邻接表）

代码里有详细的介绍，代码能跑起来，能模拟出在障碍的情况下的寻路过程

自行实现图的邻接矩阵和邻接表存储结构 邻接矩阵类和邻接表类的实现及测试函数 功能全 代码易理解 可直接运行