略
图的储存结构 邻接矩阵图的邻接矩阵用两个数组表示：
1、一位数组储存顶点信息
2、二位数组储存边信息
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100
#define INFINITY 65535
typedef int Status;
typedef char VertexType;
typedef int EdgeType;
typedef struct
{
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numNodes, numEdges;
}MGraph;
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("输入顶点数和边数:n");
scanf("%d,%d",&G->numNodes,&G->numEdges);
for(i = 0;i numNodes;i++)
scanf(&G->vexs[i]);
for(i = 0;i numNodes;i++)
for(j = 0;j numNodes;j++)
G->arc[i][j]=INFINITY;
for(k = 0;k numEdges;k++)
{
printf("输入边(vi,vj)上的下标i，下标j和权w:n");
scanf("%d,%d,%d",&i,&j,&w);
G->arc[i][j]=w;
G->arc[j][i]= G->arc[i][j];
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
return 0;
}
时间复杂度：
邻接矩阵O（n^2）
整体：O（n+n^2+e）
邻接表对于边数相对较少的图，邻接矩阵十分浪费。
回忆在树的章节，有一种孩子表示法：将结点存入数组，无论有多少孩子，都用链式存储存在后面。这样不会造成空间的浪费。这种方法同样适用于图的存储。
邻接表——数组与链表相结合的储存方式称之为邻接表。
无向图的邻接表
有向图
带权图
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100
typedef int Status;
typedef char VertexType;
typedef int EdgeType;
typedef struct EdgeNode
{
int adjvex;
EdgeType info;
struct EdgeNode *next;
}EdgeNode;
typedef struct VertexNode
{
VertexType data;
EdgeNode *firstedge;
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numNodes,numEdges;
}GraphAdjList;
void CreateALGraph(GraphAdjList *G)
{
int i,j,k;
EdgeNode *e;
printf("输入顶点数和边数:n");
scanf("%d,%d",&G->numNodes,&G->numEdges);
for(i = 0;i < G->numNodes;i++)
{
scanf(&G->adjList[i].data);
G->adjList[i].firstedge=NULL;
}
for(k = 0;k < G->numEdges;k++)
{
printf("输入边(vi,vj)上的顶点序号:n");
scanf("%d,%d",&i,&j);
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=j;
e->next=G->adjList[i].firstedge;
G->adjList[i].firstedge=e;
e=(EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex=i;
e->next=G->adjList[j].firstedge;
G->adjList[j].firstedge=e;
}
}
int main(void)
{
GraphAdjList G;
CreateALGraph(&G);
return 0;
}
在插入的时候适用了“头插法”
时间复杂度：O（n+e）
十字链表 邻接多重表 边集数组 图的抽象数据类型图的基本操作要一个一个实现一下
图的遍历 深度优先遍历 DFS 广度优先遍历 BFS 最小生成树 普里姆算法 Prim 克鲁斯卡尔算法 KruskalPrim算法是以某结点为起点，逐步寻找顶点上的最小权值来构造最小生成树。
但事实上，还有另一种思考方式：
就像我们去迪士尼游玩，会先挑选出自己想玩的项目再确定路线，
同样，我们也可以以边为目标来构造，这就是Kruskal算法。
所以现在要构造一棵最小生成树，我们的思路就是先把边按照权值排序（就像游玩的期待值），
之后把它们依次选中（在不会与之前的边生成环的情况下），这样循环完整个图，就可以得到一棵树（不含有环）。
所以我们要解决的主要问题有两个：
1.排序
2.判断是否会形成环
我们一个一个解决：
1.排序
这一步比较简单，程序中通过建立一个数组来完成edges；同时构造了两个辅助函数swap，sort；
2.判断是否会形成环
这是整个算法很重要的部分
设定parent数组，帮助判断，构造Find函数。while循环判断条件为 parent[f] > 0，也就是说直到找到小于0的值，即端点才会停止。
（这里不需要担心边方向问题，因为虽然是无向图，但是在定义边结点时事实上是有默认方向的）
（给出一个例子）
int Find(int *parent, int f)
{
while ( parent[f] > 0)//一直到找到端点为止
{
f = parent[f];
}
return f;
}
完整代码：
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef struct
{
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef struct
{
int begin;
int end;
int weight;
}Edge;
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=15;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=10;
G->arc[0][5]=11;
G->arc[1][2]=18;
G->arc[1][8]=12;
G->arc[1][6]=16;
G->arc[2][8]=8;
G->arc[2][3]=22;
G->arc[3][8]=21;
G->arc[3][6]=24;
G->arc[3][7]=16;
G->arc[3][4]=20;
G->arc[4][7]=7;
G->arc[4][5]=26;
G->arc[5][6]=17;
G->arc[6][7]=19;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
void Swapn(Edge *edges,int i, int j)
{
int temp;
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
void sort(Edge edges[],MGraph *G)
{
int i, j;
for ( i = 0; i < G->numEdges; i++)
{
for ( j = i + 1; j < G->numEdges; j++)
{
if (edges[i].weight > edges[j].weight)
{
Swapn(edges, i, j);
}
}
}
printf("权排序之后的为:n");
for (i = 0; i < G->numEdges; i++)
{
printf("(%d, %d) %dn", edges[i].begin, edges[i].end, edges[i].weight);
}
}
int Find(int *parent, int f)
{
while ( parent[f] > 0)//一直到找到端点为止
{
f = parent[f];
}
return f;
}
void MiniSpanTree_Kruskal(MGraph G)
{
int i, j, n, m;
int k = 0;
int parent[MAXVEX];
Edge edges[MAXEDGE];
for ( i = 0; i < G.numVertexes-1; i++)
{
for (j = i + 1; j < G.numVertexes; j++)
{
if (G.arc[i][j]
最短路径
在有权图和无权图之中，最短路径的含义不同。
无权图：经过边数最少的路径；
有权图： 两顶点经过边上权值和最小；
显然研究有权图更具有实用价值。（无权图可以转化为权值为1的有权图）
迪杰斯特拉（Dijkstra）算法
Dijkstra算法大致的思路：
1、准备工作
（1）设立两个数组保存结果 P[ ] D[ ]
P[v]的值是v的前驱顶底下标
D[v]表示v0（可以改为其他节点）到v的最短路径长度
（2）设置一个辅助数组final[ ]
final[v]==0表示该点还未确定路径；==1表示已经确定路径；
（3）将他们全部初始化，D[ v ] 导入G.matirx[ v0 ][ v ]， P[ v ] 全部设为0 ，final[ ]全部设为0；
2、主要实现
主循环，每次都求得v0到某个点v的最短路径，这就是为什么我们要执行v
主循环里面的第一个循环找到还未确定路径中的最短路径。（因为这一段是所剩最短的，是可以确定下来的）
一定要注意，由于上一句话我们是默认的，所以Dijkstra算法是不适用与权值为负的情况的。
主循环内第二个循环，是用新确定的最短路径去更新其他未确定的路径。
如何更新？
假设在第一个循环找到的最短路径长min，顶点为k，到m顶点的路径还未确定。
则我们要比较以k为跳板，即先从v0走目前的最小路径到k，再从k直接到m，与原本的路径相比是否会更小，若更小，则替换。（D[ ] ,P [ ]都要替换）
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status;
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX];
typedef int ShortPathTable[MAXVEX];
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
void ShortestPath_Dijkstra(MGraph G, int v0, Patharc *P, ShortPathTable *D)
{
int v,w,k,min;
int final[MAXVEX];
for(v=0; v
弗洛伊德（Floyd）算法
先举一个简单 的例子：
初始化
三层循环
输出
时间复杂度
使用条件（权值有负值的情况）
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 20
#define INFINITY 65535
typedef int Status;
typedef struct
{
int vexs[MAXVEX];
int arc[MAXVEX][MAXVEX];
int numVertexes, numEdges;
}MGraph;
typedef int Patharc[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];
void CreateMGraph(MGraph *G)
{
int i, j;
G->numEdges=16;
G->numVertexes=9;
for (i = 0; i < G->numVertexes; i++)
{
G->vexs[i]=i;
}
for (i = 0; i < G->numVertexes; i++)
{
for ( j = 0; j < G->numVertexes; j++)
{
if (i==j)
G->arc[i][j]=0;
else
G->arc[i][j] = G->arc[j][i] = INFINITY;
}
}
G->arc[0][1]=1;
G->arc[0][2]=5;
G->arc[1][2]=3;
G->arc[1][3]=7;
G->arc[1][4]=5;
G->arc[2][4]=1;
G->arc[2][5]=7;
G->arc[3][4]=2;
G->arc[3][6]=3;
G->arc[4][5]=3;
G->arc[4][6]=6;
G->arc[4][7]=9;
G->arc[5][7]=5;
G->arc[6][7]=2;
G->arc[6][8]=7;
G->arc[7][8]=4;
for(i = 0; i < G->numVertexes; i++)
{
for(j = i; j < G->numVertexes; j++)
{
G->arc[j][i] =G->arc[i][j];
}
}
}
void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D)
{
int v,w,k;
for(v=0; v(*D)[v][k]+(*D)[k][w])
{
(*D)[v][w]=(*D)[v][k]+(*D)[k][w];
(*P)[v][w]=(*P)[v][k];
}
}
}
}
}
int main(void)
{
int v,w,k;
MGraph G;
Patharc P;
ShortPathTable D;
CreateMGraph(&G);
ShortestPath_Floyd(G,&P,&D);
printf("各顶点间最短路径如下:n");
for(v=0; v %d",k);
k=P[k][w];
}
printf(" -> %dn",w);
}
printf("n");
}
printf("最短路径Dn");
for(v=0; v
未完待续。。。
