1、结构
（1）邻接矩阵法

#define MaxVertexNum 100		//顶点数目最大值
typedef char VertexType;		//顶点数据类型
typedef int EdgeType;			//带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum];					//顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum];		//邻接矩阵，边表int vexnum,arcnum;			//图的当前顶点数和弧数
}MGraph;

（2）邻接表法

#define MaxVertexNum 100		//顶点数目最大值
typedef struct ArcNode{			//边表结点int adjvex;					//该弧所指向的顶点位置struct ArcNode *next;		//指向下一条弧的指针//InfoType info;			//网的边权值
}ArcNode;
typedef struct VNode{			//顶点表结点VertexType data;			//顶点信息ArcNode *first;				//指向第一条依附该结点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{AdjList vertices;			//邻接表int vexnum,arcnum;			//图的顶点数和弧数
}ALGraph;

2、基本操作

Adjacent(G,x,y)				//判断图G是否存在边<x,y>
Neighbors(G,x)				//列出图G中与结点x邻接的边
InsertVertex(G,x)			//插入顶点x
DeletVertex(G,x)			//删除顶点x
AddEdge(G,x,y)				//若边<x,y>不存在，则添加
RemoveEdge(G,x,y)			//若边<x,y>不存在，则删除
FirstNeighbor(G,x)			//求顶点x的第一个邻接点，有则返回顶点号，否则返回-1
NextNeighbor(G,x,y)			//返回x的下一个顶点号（除y），若y是x的最后一个则返回-1
Get_edge_value(G,x,y)		//获得边(x,y)的权值
Set_edge_value(G,x,y,v)		//设置边(x,y)的权值

3、广度优先遍历（BFS)

bool visited[MAX_VERTEX_NUM]; 		//访问标记数组
void BFSTraverse(Graph G){ 			//对图G进行广度优先遍历for(i=0;i<G.vexnum;++i)visited[i]=FALSE； 			//访问标记数组初始化InitQueue(Q);					//初始化辅助队列Qfor(i=0;i<G.vexnum;++i) 		//从0号顶点开始遍历if(!visited[i]) 			//对每个连通分量调用一次BFSBFS(G,i);				//vi未访问过，从vi开始BFS
}
void BFS (Graph G,int v){			//从顶点v出发，广度优先遍历图Gvisit(v); 						//访问初始顶点vvisited[v]=TRUE; 				//对v做已访问标记Enqueue(Q,v); 					//顶点v入队列Qwhile(!isEmpty(Q))(DeQueue (Q,v); 				//顶点v出队列for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//检测v所有邻接点if(!visited[w]){			//w为v的尚未访问的邻接顶点visit(w); 				//访问顶点wvisited[w]=TRUE；		//对w做已访问标记EnQueue(Q,w); 			//顶点w入队列}//if}//while
}

4、深度优先遍历（DFS)

//递归
bool visited[MAX_VERTEX_NUM]; 		//访问标记数组
void DFSTraverse(Graph G){			//对图G进行深度优先遍历for(v=0;v<G.vexnum;++v)visited[v]=FALSE; 			//初始化已访问标记数据for(v=0;v<G.vexnum;++v) 		//本代码中是从v=0开始遍历if(!visited[v])DFS(G,v);
}
void DFS(Graph G,int v){			//从顶点v出发，深度优先遍历图Gvisit(v); 						//访问顶点vvisited[v]=TRUE; 				//设已访问标记for(w=FirstNeighbor(G,v)；w>=0；w=NextNeighor(G,v,w))if(!visited[w])				//w为u的尚未访问的邻接顶点DFS(G,w)；
}

//非递归
void DFS_Non_RC(AGraph& G,int v)(
//从顶点v开始进行深度优先搜索，一次遍历一个连通分量的所有顶点int w; 								//顶点序号InitStack(S); 						//初始化栈sfor(i=0;i<G.vexnum;i++)visited[i]=FALSE; 				//初始化visitedPush (S,v);   visited[v]=TRUE； 					//v入栈并置visited[v]while(!IsEmpty(S)){k=Pop(S)； 						//栈中退出一个顶点visit（k)； 						//先访问，再将其子结点入栈for(w=FirstNeighbor(G,k);w>=0；w=NextNeighor(G,k,w))	//k所有邻接点if(!visited[w]){			//未进过栈的顶点进栈Push(S,w)；visited[w]=true; 		//作标记，以免再次入栈}//if}//while
}//DES_Non_RC

5、prim算法

int cost[MAX_V][MAX_V]; 	//cost [u][v]表示边e=(u，v)的衩值（不存在的情况下设为INF）
int mincost[MAX_V]; 		//从集合X出发的边到每个顶点的最小权值
bool used[MAX_V];			//顶点i是否包含在集合X中
int V; 						//顶点数int prim(){for(int i=0; i<V ; ++i){mincost[i] = INF;used[i] = false;}mincost[0]=0；int res =0；while(true){int v=-1;					//从不属于X的顶点中选取从X到其权值最小的顶点for (int u=0; u< V； u++){if(!used[u] && (v ==-1 || mincost[u]< mincost[v]))	v=u；}if (v ==-1) break;used[v] = true;				// 把顶点v加入Xres += mincost[v]; 			//把边的长度加到结果里for(int u=0；u< V； u++){mincost [u］ = min(mincost[u], cost[v][u]);}}return res;
}

6、kruskal算法

struct edge{int u,v,cost；}；
bool comp(const edge& e1, const edge& e2){return e1.cost < e2.cost;
}edge es[MAX_E];
int V, E; 				//顶点数和边数int kruskal(){sort(es, es+ E, comp); 		//按照edge.cost的顺序从小到大排列init_union_find(V)； 		//并查集的初始化int res=0;for(int i=0；i<E； i++){edge e = es[i];if (!same(e.u, e.v)){unite(e.u, e.v);res+= e.cost;}}return res;
}

7、Dijkstra算法

int cost[MAX_V][MAX_V]； 	//cost[u][v]表示边e=(u，v)的权值(不存在这条边时设INF)
int d[MAX_V]； 				//顶点s出发的最短距离
bool used[MAX_V]; 			//已经使用过的图
int V; 						//顶点数//求从起点s出发到各个顶点的最短距离
void dijkstra(int s){fill(d, d+V, INF)；fill(used, used+V, false);d[s］=0；while(true){int v=-1;//从尚未使用过的顶点中选择一个距离最小的顶点for(int u=0; u< V; u++){if (!used[u] && (v ==-1 || d[u]<d[v]))	v=u;}if (v == -1) break;used[v] = true;for(int u=0 ; u<V ; u++){d[u] = min(d[u], d[v]+cost[v][u]);}}
}

8、Floyd算法

int i, j, k;
int d[MAXSIZE MAXSIZE), path[MAXSIZE][MAXSIZE]
//先把图的邻接矩阵复制到d
for( i=0; i<n; i++){for(=0; j<n; j++){d[i][j]=G.edge[i][j];path[i]=-1;}
}for(k=0; k<n; k++){for(i=0; i<n; i++){for(j=0; j<n; j++){if(d[i][j]> d[i][k]+d[k][j])d[i][j]> d[i][k]+d[k][j];path[i][j]= k;}}}
}

9、拓扑排序

bool TopologicalSort (Graph G) {InitStack(S) ;				//初始化栈，存储入度为0的项点for(int i=0;i<G. vexnum;i++)if (indegree[i]==0)Push(S,i) ;			//将所有入度为0的顶点进栈int count=0;				//计数，记录当前已经输出的项点数while (!IsEmpty(S)) {		//栈不空，则存在入度为0的顶点Pop(S,i) ;				//栈顶元素出栈print [count++]=i;		//输出顶点ifor(p=G.vertices[i].firstarc;p;p=p->nextarc) {//将所有i指向的顶点的入度减1,并且将入度减为0的顶点压入栈sv=p->adjvex;if(! (--indegree[v])Push(S,v); 		//入度为0， 则入栈}}//whileif (count<G. vexnum)return false;			//排序失败，有向图中有回路elsereturn true;			//拓扑排序成功
}