图论学习报告报告内容:一．基本概念：1.叙述图：所谓图G是一个三元组，记做G=<V(G),E(G), ψ(G)>,其中V(G)={v1,v2,v3,…,vn},V(G)≠∅，称为图G的结点集合；E（G）=（e1，e2,…,en），是G的边的集合。
ψ(G)称为关联函数。
2.有向图：每一条边都是有向边的图称为有向图。
3.无向图：每一条边都是无向边的图称为有向图。
4.欧拉图：含欧拉回路的无向连通图与含有有向欧拉回路的弱连通有向图统称为欧拉图。
5.哈密顿图：具有哈密顿回路的无向图，与具有哈密顿有向回路的有向图统称为哈密顿图。
6.最短路径：在加权图中找出二个指定点之间的最短路叫做最短路径。
7.树：无圈连通无向图叫做树。
8.二叉树：每个节点最多只有二个子树的树叫做二叉树。
9.最小支撑树：连通加权图里权和最小的支撑树称为最小支撑树。
10.最优二叉树：在所有的带权w1,w2,w3,…,wt的二叉树中，带权最小的二叉树称为最优二叉树。
11.平面图：如果图G能够示画在曲面S上，且使得它的边近在断点处相交，则称G可嵌入曲面S。
如果图G可以嵌入平面上，则称G是可平面图，已经嵌入平面上的图g称为G 的平面表示。
G与g都简称为平面图。
二．算法设计1：写出Dijkstra算法{G带有顶点a=v0,v1,…,vn=z和权w（vi，vj），若{vi，vj}不是G中的边，则w(vi,vj)=∞} For i:=1 to nL(vi): ∞L(a):=0S:= ¢{初始化标记，a的标记为0，其余结点标记为∞，S是空集}While z∉SBeginu:=不属于S的L（u）最小的一个顶点S：=S∪{u}For所有不属于S的顶点vIf L(u)+w(u,v)<L(v)Then L(v):=L(u)+w(u,v){这样就给S中添加带最小标记点并且更新不在S中的顶点的标记}End{L（z）=从a到z的最短路长度}2：写出Floyd算法把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表示该路的长度；否则G [i,j]=空值。
定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。
把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值变小，则D[i,j]=k。
在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。
根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。
3：写出求最小支撑树的算法普林算法：(G:带n个顶点的连通无向图)T：=权最小的边For i:=1 to n-2Begine :=与T里顶点相关联的权最小的边，并且若添加到T里则不形成圈T：=添加e之后的TEnd{T是G的最小支撑树}普林算法的另一种形式（G：加权连通图）Forj :=1 to n dobeginLj :=w(s,j){临时标号}B（j）：=s；EndLs :=0设置Ls为固定的While 遗留临时标号doBegin选择最小临时标号Li设置Li为固定的边{i，B（i）}加入T结点i加入Tfor每个临时标号Lk doIf w（i，k）＜Lk thenBeginLk：=w（i，k）B（k）：=iEndEndReturnEnd{T为G的最小支撑树}克鲁斯卡尔算法（G：n个顶点的连通加权无向图）T：=空图For i：=1 to n-1Begine ：=当添加到T里时不形成圈的G里权最小的边T：=添加e之后的TEnd{T是G的最小支撑树}三：程序实现1：写出Warshall算法的C语言程序#include<stdio.h>#include<math.h>Void mian(){Int A[10][10];Int n,I,j,k;Printf(“输入关系矩阵的维数n（n<10）\n”);Scanf(“%d”,&n);Printf(“输入n*n个数据（0 or 1）\n”);For(i=1;i<=n;i++){For(j=1;j<=n;j++){Scanf(“%d”,&A[i][j]);If(A[i][j]!=1&&A[i][j])Printf(“there is a error”);}}For(i=1;i<=n;i++){For(j=1;j<=n;j++){For(k=1;k<=n;k++){If(A[i][j]&&(A[i][k]||A[j][k]))A[i][k]=1;}}}Printf(“传递闭包的关系矩阵：\n”);For(i=1;i<=n;i++){For(j=1;j<=n;j++)Printf(“%2d”,A[i][j]);Printf(“\n”);}}2：写出深度优先搜索算法的C语言程序#include <iostream>#define INFINITY 32767#define MAX_VEX 20 //最大顶点个数#define QUEUE_SIZE (MAX_VEX+1) //队列长度using namespace std;bool *visited; //访问标志数组//图的邻接矩阵存储结构typedef struct{char *vexs; //顶点向量int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和弧数}Graph;//队列类class Queue{public:void InitQueue(){base=(int *)malloc(QUEUE_SIZE*sizeof(int));front=rear=0;}void EnQueue(int e){base[rear]=e;rear=(rear+1)%QUEUE_SIZE;}void DeQueue(int &e){e=base[front];front=(front+1)%QUEUE_SIZE;}public:int *base;int front;int rear;};//图G中查找元素c的位置int Locate(Graph G,char c){for(int i=0;i<G.vexnum;i++)if(G.vexs[i]==c) return i;return -1;}//创建无向网void CreateUDN(Graph &G){int i,j,w,s1,s2;char a,b,temp;printf("输入顶点数和弧数:");scanf("%d%d",&G.vexnum,&G.arcnum);temp=getchar(); //接收回车G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目printf("输入%d个顶点.\n",G.vexnum);for(i=0;i<G.vexnum;i++){ //初始化顶点printf("输入顶点%d:",i);scanf("%c",&G.vexs[i]);temp=getchar(); //接收回车}for(i=0;i<G.vexnum;i++) //初始化邻接矩阵for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;printf("输入%d条弧.\n",G.arcnum);for(i=0;i<G.arcnum;i++){ //初始化弧printf("输入弧%d:",i);scanf("%c %c %d",&a,&b,&w); //输入一条边依附的顶点和权值temp=getchar(); //接收回车s1=Locate(G,a);s2=Locate(G,b);G.arcs[s1][s2]=G.arcs[s2][s1]=w;}}//图G中顶点k的第一个邻接顶点int FirstVex(Graph G,int k){if(k>=0 && k<G.vexnum){ //k合理for(int i=0;i<G.vexnum;i++)if(G.arcs[k][i]!=INFINITY) return i;}return -1;}//图G中顶点i的第j个邻接顶点的下一个邻接顶点int NextVex(Graph G,int i,int j){if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理for(int k=j+1;k<G.vexnum;k++)if(G.arcs[i][k]!=INFINITY) return k;}return -1;}//深度优先遍历void DFS(Graph G,int k){int i;if(k==-1){ //第一次执行DFS时,k为-1for(i=0;i<G.vexnum;i++)if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS}else{visited[k]=true;printf("%c ",G.vexs[k]); //访问第k个顶点for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS }}//主函数void main(){int i;Graph G;CreateUDN(G);visited=(bool *)malloc(G.vexnum*sizeof(bool));printf("\n深度优先遍历: ");for(i=0;i<G.vexnum;i++)visited[i]=false;BFS(G);printf("\n程序结束.\n");}。