C语言图总结

#include 
#include

#define MaxVexNum 100
typedef struct {
	char Vex[MaxVexNum];//顶点表
	int Edge[MaxVexNum][MaxVexNum];//边表有边填1无边填0
	int vexnum, arcnum;//当前顶点数和边数
}MGraph;//邻接矩阵法存图
//出度行入度列求顶点的度时间复杂度O(|v|)
#define MaxVexNum 100
#define INFINITY 0x7fffffff//用int的上限值表示无穷
typedef struct {
	char Vex[MaxVexNum];//顶点表
	int Edge[MaxVexNum][MaxVexNum];//边表有边填权无边填无穷
	int vexnum, arcnum;//当前顶点数和边数
}MGraph;//邻接矩阵法存网;

typedef struct ArcNodde {
	int adjvex;//边（弧）指向那个结点
	struct ArcNode* next;//指针域
}ArcNode;//边结点
typedef struct VNode {
	int data;//顶点数据域
	ArcNode* first;//第一条边的指针
}VNode, AdjList[MaxVexNum];//顶点结点表
typedef struct ALGraph {
	AdjList vertices;
	int  vexnum, arcnum;//当前顶点数和边数
}ALGraph;//用邻接表法存图

typedef struct ArcNodde {
	int tailvex;//弧尾顶点编号
	int headvex;//弧头顶点编号
	int info;//权值
	struct ArcNode* tlink;//弧尾相同的下一条弧
	struct ArcNode* hlink;//弧头相同的下一条弧
}ArcNode;//弧结点
typedef struct VNode {
	int data;//顶点数据域
	ArcNode* firstout;//第一条以该结点作为弧尾边的指针
	ArcNode* firstin;//第一条以该结点作为弧头边的指针
}VNode, AdjList[MaxVexNum];//顶点结点表
//十字链表法存有向图空间复杂度O(|V|+|E|)
typedef struct ArcNodde {
	int i;//顶点编号i
	int j;//顶点编号j
	int info;//权值
	struct ArcNode* ilink;//顶点i的下一条边
	struct ArcNode* jlink;//顶点j的下一条边
}ArcNode;//边结点
typedef struct VNode {
	int data;//顶点数据域
	ArcNode* firstedg;//该顶点的第一条边
}VNode, AdjList[MaxVexNum];//顶点结点表
//邻接多重表法存无向图空间复杂度O(|V|+|E|)
bool visited[MaxVexNum];
void BFS(MGraph G, int v) {
	visit(v);
	visited[v] =true;
	//INqueue(Q, v);入队
	//while (!isEmpty(Q)) {
		//OUTqueue(Q, v);
		for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
			if (!visited[w]) {
				visit(w);
				visited[w] = true;
				//INqueue(Q, w);

			}
		}
	}
void BFSTraverse(MGraph G) {
	for (int i = 0; i < G.vexnum; i++) {
		visited[i] = false;
	}
	for (int i = 0; i < G.vexnum; i++) {
		if (!visited[i]) {
			BFS(G, i);
		}
	}
}//图的广度优先遍历空间复杂度最坏O(|v|)
     //             邻接矩阵 时间复杂度O(|v|2)
    //              邻接表   时间复杂度O(|v|+|E|)
//广度优先生成树
void DFS(MGraph G, int v) {
	visit(v);
	visited[v] = true;
	for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
		if (!visited[w]) {
			DFS(G, w);
		}
	}
}
void DFSTraverse(MGraph G) {
	for (int i = 0; i < G.vexnum; i++) {
		visited[i] = false;
	}
	for (int i = 0; i < G.vexnum; i++) {
		if (!visited[i]) {
			DFS(G, i);
		}
	}
}//图的深度优先遍历空间复杂度最坏O(|v|)
     //             邻接矩阵 时间复杂度O(|v|2)
    //              邻接表   时间复杂度O(|v|+|E|)
//深度优先生成树

void BFS_MIN_Distance(MGraph G, int u) {
	int d[MaxVexNum]; //距离数组
	int path[MaxVexNum];//前驱结点数组
	for (int i = 0; i < G.vexnum; i++) {
		d[i] = INFINITY;
		int path[8];
		path[i] = -1;
	}
	d[u] = 0;
	visited[u] = true;
	//INqueue(Q, u);入队
	//while (!isEmpty(Q)) {
		//OUTqueue(Q, u);
	for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w)) {
		if (!visited[w]) {
			d[w] = d[u] + 1;
			path[w] = u;
			visited[w] = true;
			//INqueue(Q, w);

		}
	}
}//BFS算法最短路径问题无向图单源最短路径
 //             邻接矩阵 时间复杂度O(|v|2)
	//              邻接表   时间复杂度O(|v|+|E|)
int final[MaxVexNum];//标记各顶点是否已找到最短路径
dist[MaxVexNum];//最短路径长度
path[MaxVexNum];//前驱结点
//每轮寻找final未确定且dist最小的顶点并修改dist path数组

int A[MaxVexNum][MaxVexNum];//目前各顶点间最短距离
int path[MaxVexNum][MaxVexNum];//两个顶点间的中转点

void Floyd_MIN_Distance(A, path) {
	for (int k = 0; k < MaxVexNum; k++) {
		for (int i = 0; i < MaxVexNum; i++) {
			for (int j = 0; j < MaxVexNum; j++) {
				//if (A[i][j] > A[i][k] + A[k][j]) {
					//A[i][j] = A[i][k] + A[k][j];
					//path[i][j] = k;
				//}
			}
		}
	}
}//Floyd算法最短路径问题求有向图无向图皆可的各顶点间最短路径时间复杂度O(|v|3)不适用于带有负权值回路的带权图