总结一下图论的一些知识点 1．邻接矩阵 1．1 有向图的邻接矩阵 具有n个顶点的有向图可以用一个n×n的方形矩阵表示。假设该矩阵的名称为M，则当<vi,vj>是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。 1．2 无向图的邻接矩阵 具有n个顶点的无向图也可以用一个n×n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i 行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半，这是因为每条边在矩阵中描述了两次 创建有向图和无向图邻接表的算法实现： （1） 创建有向图邻接表 void Create_adj(AdjList adj, int n) { for (i=0;i<n;i++){ //初始化顶点数组 scanf(&adj[i].elem); adj[i].firstedge=NULL; } scanf(&i,&j); //输入弧 while (i) { s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); //创建新的弧结点 s->adgvex=j-1; s->next=adj[i-1].firstedge; //将新的弧结点插入到相应的位置 adj[i-1].firstegde=s; scanf(&i,&j); //输入下一条弧 } } （2）创建无向图的邻接表 void Create_adj(AdjList adj, int n) { for (i=0;i<n;i++){ //初始化邻接表 scanf(&adj[i].elem); adj[i].firstedge=NULL; } scanf(&i,&j); //输入边 while (i) { s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); s1->adgvex=j-1; s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); s2->adgvex=i-1; s1->next=adj[i-1].firstedge; adj[i-1].firstegde=s1; s2->next=adj[j-1].firstedge; adj[j-1].firstegde=s2; scanf(&i,&j); } } 2．图的生成树和森林 对于一个拥有n个顶点的无向连通图，它的边数一定多余n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边（弧）组成的图被称为原无向图的生成树。显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。 3.最小生成树 在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。 图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边 构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。 算法实现: void Mini_SpanTree(Graph G,int k,int n) {//G是网的邻接矩阵，k是生成树根结点的序号，n是网的顶点数目 for (j=0;j<n;j++) if (j!=k) closedge[j]={k,G[k][j]}; closedge[k].lowcost=0; for (i=1;i<n;i++) { k=minmun(closedge); printf(k,closedge[k].adjvex); closedge[k].lowcost=0; //将顶点加入U集合中 for (j=0;j<n;j++) if (closedge[i]&&G[k][j]<closedge[j].lowcost) closedge[j]={k,G[k][j]}; } }
