数据结构编程——求无向图连通子图

#include<iostream>#include<vector>using namespace std;#define INFINITY 0 //最大值为无限大#define MAX_VERTEX_NUM 20 //最大顶点个数bool visited[MAX_VERTEX_NUM]={false}; //数组的遍历标志//typedef enum{DG,DN,UDG,UDN} GraphKind; //{有向图，有向网，无向图，无向网} typedef struct ArcCell{int adj; //对无权图，用1或0表示是否相邻;对带权图，则为权值int* info; //边的信息} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct{int vexs[MAX_VERTEX_NUM]; //顶点向量AdjMatrix arcs; //邻接矩阵int vexnum,arcnum; //图的当前顶点数和弧数int kind; //图的类型}MGraph;int CreateUDN(MGraph &G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for( i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;G.arcs[v2-1][v1-1].adj=w;}return 1;int CreateUDG(MGraph& G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for(i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;G.arcs[v2-1][v1-1].adj=w;}return 1;}int CreateDN(MGraph& G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for( i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;}return 1;}int CreateDG(MGraph& G){cout<<"请输入顶点个数和弧数:";cin>>G.vexnum>>G.arcnum;int i;for( i=0; i<G.vexnum; i++)G.vexs[i]=i+1;for( i=0; i<G.vexnum; i++){for(int j=0; j<G.vexnum; j++){G.arcs[i][j].adj=INFINITY;G.arcs[i][j].info=NULL;}}for( i=0; i<G.arcnum; i++){cout<<"请输入两个顶点和权值:";int v1,v2,w;cin>>v1>>v2>>w;G.arcs[v1-1][v2-1].adj=w;}return 1;}int CreateGraph(MGraph& G){cout<<"请输入你想要的图的类型：";cin>>G.kind;switch(G.kind){case 0:return CreateDG(G); //构造有向图case 1:return CreateDN(G); //构造有向网case 2:return CreateUDG(G); //构造无向图case 3:return CreateUDN(G); //构造无向网default:return 0;}}int FirstAdjVex(MGraph& G,int i){for(int j=0; j<G.vexnum; j++){if(G.arcs[i][j].adj!=0)return j;}return -1;}int NextAdjVex(MGraph& G,int i,int w){for(int j=w+1; j<G.vexnum; ++j){if(G.arcs[i][j].adj!=0)return j;}return -1;}void DFS(MGraph& G,int i){visited[i]=true;cout<<G.vexs[i]<<" "<<endl;for(int w=FirstAdjVex(G,i); w>=0; w=NextAdjVex(G,i,w)){ if(!visited[w])DFS(G,w);}}void DFSTraverse(MGraph& G){int number=0;for(int i=0; i<G.vexnum; i++){if(!visited[i]){number++;DFS(G,i);}}cout<<"图的连通分量有"<<number<<"个"<<endl;}int main(){MGraph G;CreateGraph(G);for(int i=0; i<G.vexnum;i++){for(int j=0; j<G.vexnum; j++)cout<<G.arcs[i][j].adj<<" ";cout<<endl;}cout<<endl;DFSTraverse(G);return 0;}。

求无向连通图‎的最小生成树‎算法——Prim与K‎r uskal‎及相关优化最小生成树是‎图论里很重要‎的部分。

但是由于它属‎于图论所以N‎O IP基本不‎考，对于NOI又‎太基础，所以竞赛中出‎现的几率比较‎小，即使要考也不‎可能考裸的生‎成树算法= =最小生成树就‎P rim和K‎r uskal‎两个算法，又没有多大的‎优化余地，所以学习起来‎还是很简单的‎。

一.Prim算法‎1.算法思想对于图G=(V,E)，用Prim算‎法求最小生成‎树T=(S,TE)的流程如下① 初始化：设S、TE为空集，任选节点K加‎入S。

②选取一条权值‎最小的边（X,Y），其中X∈S，且not (Y∈S）即，选取一条权值‎最小的、连接着S中一‎点与S外一点‎的边。

将Y加入S中‎，边（X，Y）加入TE中重复② 直到V=S即所有G中‎的点都在S中‎，此时的T为G‎的最小生成树‎。

由此流程可见‎，Prim算法‎求最小生成树‎时任何时候的‎T都是一颗树‎。

2.实现显然，Prim算法‎的主要运行时‎间花在过程②的选边中。

看起来复杂度‎是O(VE)=O(V^3)不是么，效率也太低了‎吧……为了比较快速‎地选边，我们用两个数‎组lowco‎s t、closes‎t动态地维护‎每一个点到S‎的最短距离。

在某一状态下‎，lowcos‎t[i]表示所有与i‎相连且另一端‎点在S中的边‎中的权值最小‎值，closes‎t[i]表示在S中且‎与i相连的点‎中与i之间距‎离最小的点。

显然，lowcos‎t[i]=w(i,closes‎t[i])。

需要注意的是‎两个数组记录‎的都是边而不‎是路径。

若i没有边直‎接连向S，则lowco‎s t[i]=∞。

另外，若i已在S中‎，则lowco‎s t[i]=0。

设出发点为x‎。

初始时对于任‎意k∈V，closes‎t[k]=x，lowcos‎t[k]=w（k,x）【w（i，j）表示i、j间的距离。

初始化时，若两点间没有‎边则w（i，j）赋为一个足够‎大的整数（如maxin‎t），并且所有点到‎自身的距离赋‎为0，即w（i，i）=0】每一次找出l‎o wcost‎中不为0的最‎小值lowc‎o st[i]，然后把i加入‎S（即lowco‎s t[i]:=0），然后对于图中‎所有点k，若w(k,i)<lowcos‎t[k]，则把lowc‎o st[k]赋为w(k,i)，把close‎s t[k]赋为i。

无向图的连通分支问题
«问题描述：
试设计用并查集来计算一个无向图的连通分支的算法。

«编程任务：
对于给定的无向图G，用并查集编程计算无向图G的连通分支。

«数据输入：
由文件input.txt给出输入数据。

第一行有3个正整数n，k和m，分别表示无向图G有n个顶点和k条边，m是查询顶点对个数。

接下来的k+m行，每行有2个正整数。

前k行给出图G的k条边（可能重复）；后m行是查询顶点对。

«结果输出:
对于每个查询顶点对(i,j)，将计算结果依次输出到文件output.txt。

如果顶点i和顶点j 属于图G的同一连通分支，则输出“Yes”，否则输出“No”。

输入文件示例输出文件示例
input.txt output.txt
10 3 3 1 2
3 4
1 3
2 3
1 4
5 6 Yes Yes No。

【图论基础】求连通子图的个数Time Limit:10000MS Memory Limit:65536KTotal Submit:42 Accepted:30Description求一个无向图中连通子图的个数。

Input第一行一个数n，表示无向图的顶点的数量（n<=5000），接下来从第2行到第n+1行，每行有n个数（1表示相应点有直接通路，0表示无直接通路），形成一个n*n的矩阵，用以表示这个无向图。

示例：Output输出一个数，表示这个图含有连通子图的个数。

Sample Input51 0 1 0 00 1 1 1 01 1 1 1 00 1 1 1 00 0 0 0 1Sample Output自己算吧！Source∙var∙ i,j,n,ans,x:longint;∙ a:array[1..5000,0..5000] of longint;∙ b:array[1..5000] of boolean;∙procedure dfs(x:longint);∙var i:longint;∙begin∙ b[x]:=false;∙ for i:=1 to a[x,0] do if b[a[x,i]] then ∙ dfs(a[x,i]);∙end;∙∙begin∙ readln(n);∙ for i:=1 to n do∙ for j:=1 to n do begin∙ read(x);∙ if x=1 then begin∙ inc(a[i,0]); a[i,a[i,0]]:=j; ∙ end;∙ end;∙ fillchar(b,sizeof(b),true);∙ for i:=1 to n do if b[i] then begin∙ inc(ans);∙ dfs(i);∙ end;∙ writeln(ans);∙end.【图论基础】求最小生成树（prim）Time Limit:10000MS Memory Limit:65536KTotal Submit:119 Accepted:58Description求一个图的最小生成树。

华北水利水电学院数据结构实验报告2010～2011学年第二学期2010 级计算机专业班级：177 学号：201017724 姓名：靳清瑞一、实验题目：图遍历二、实验内容：编写程序，实现连通无向图的遍历。

实现提示：设图的顶点不超过20个，每个顶点用一个编号表示（如果一个图有n个顶点，则它们的编号分别为1,2，…，n）。

通过输入图的全部边输入一个图，每条边为一对整数，可以对边的输入顺序作某种限制。

注意，生成树的边是有向边，端点顺序不能颠倒。

三、程序源代码：#include <stdio.h>#include <stdlib.h>#define MAX_VERTEX_NUM 20typedef struct EBox{int mark;//访问标记,0未访问,1访问过int ivex,jvex;struct EBox *ilink,*jlink;}EBox;typedef struct VexBox{int data;EBox *firstedge;}VexBox;typedef struct{VexBox adjmulist[MAX_VERTEX_NUM];//0号单元未用int vexnum,edgenum;}MALGraph;int LocateVex(MALGraph &mg,int num){int i;for(i=1;i<mg.vexnum;i++){if(mg.adjmulist[i].data==num) break;}return i;}MALGraph mg;void createGraph(){printf("请分别输入图中的结点数、边数:\n");int num1,num2,lt1,lt2;scanf("%d %d",&mg.vexnum,&mg.edgenum);for(int i=1;i<=mg.vexnum;i++){mg.adjmulist[i].data=i; mg.adjmulist[i].firstedge=NULL;}for(int k=1;k<=mg.edgenum;k++){printf("请输入这个边的两个顶点:\n");scanf("%d %d",&num1,&num2); int flag=0;for(i=1;i<=mg.vexnum;i++){EBox *eb=mg.adjmulist[i].firstedge;while(eb!=NULL)if(eb->mark==1) break;eb->mark=1;if((eb->jvex==num1&&eb->ivex==num2)||(eb->jvex==num2&&eb->ivex==num1)){printf("!!!!!!!!!!这条边已经存在\n"); flag=1; break;}else{eb=eb->ilink;}if(flag==1)break;}}if(flag==1){k--; continue;}lt1=LocateVex(mg,num1); lt2=LocateVex(mg,num2);EBox *p=(EBox *)malloc(sizeof(EBox)); p->mark=0;p->ivex=lt1; p->jvex=lt2; p->ilink=NULL; p->jlink=NULL;if(mg.adjmulist[lt1].firstedge==NULL)mg.adjmulist[lt1].firstedge=p;else{EBox *q=mg.adjmulist[lt1].firstedge;if(q->jvex>p->jvex){mg.adjmulist[lt1].firstedge=p; p->ilink=q;else{EBox *r=q->ilink;while(r!=NULL){if(p->jvex<r->jvex){q->ilink=p; p->ilink=r; break;}else{q=r; r=r->ilink;}}if(r==NULL) q->ilink=p;}}if(mg.adjmulist[lt2].firstedge==NULL)mg.adjmulist[lt2].firstedge=p;else{EBox *q=mg.adjmulist[lt2].firstedge;if(q->ivex>p->ivex){mg.adjmulist[lt2].firstedge=p; p->jlink=q;}else{EBox *r=q->jlink;while(r!=NULL){if(p->ivex<r->ivex){q->jlink=p; p->jlink=r; break;}else{q=r; r=r->jlink;}}if(r==NULL) q->jlink=p;}}printf("%d-%d边创建成功!\n",num1,num2);}}typedef struct myStack{VexBox *top;VexBox *base;}myStack;int end(int a[]){int flag=0;for(int i=1;i<=mg.vexnum;i++){if(a[i]==0){flag=1; break;}}if(flag==0) return 0;if(flag==1) return 1;}void DFS(int value){for(int i=1;i<=mg.vexnum;i++){EBox *eb=mg.adjmulist[i].firstedge;while(eb!=NULL){if(eb->mark==1) eb->mark=0;eb=eb->ilink;}}myStack ms; int visited[20]; int lt;for(i=0;i<20;i++) visited[i]=0;ms.base=(VexBox *)malloc(sizeof(VexBox));ms.top=ms.base;lt=LocateVex(mg,value);EBox *p; visited[lt]=1;p=mg.adjmulist[lt].firstedge;ms.top->data=mg.adjmulist[lt].data;ms.top->firstedge=mg.adjmulist[lt].firstedge; ms.top++; VexBox *pp=NULL;while(end(visited)){printf("%d",end(visited));if(p==NULL&&pp==NULL){pp=ms.top; pp--; pp--; p=pp->firstedge;}if(p==NULL&&pp!=NULL){pp--; p=pp->firstedge;}if(p->ivex==lt){if(visited[p->jvex]==0) lt=p->jvex;else{ms.top--; p=ms.top->firstedge->ilink; ms.top++; continue;}}if(p->jvex==lt){if(visited[p->ivex]==0) lt=p->ivex;else{ms.top--; p=p->jlink; ms.top++; continue;}}ms.top->data=mg.adjmulist[lt].data;ms.top->firstedge=mg.adjmulist[lt].firstedge;visited[lt]=1; p=ms.top->firstedge; ms.top++;}int num[20];for(i=0;i<mg.vexnum;i++){ms.top--; ms.top->data=num[i];}printf("深度遍历的次序为:");for(i=mg.vexnum-1;i>=0;i--){ if(i=mg.vexnum-1) printf("%d",num[i]);else printf("->%d",num[i]);}}void main(){createGraph(); DFS(1);}三、测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）这次实验遇到很多问题，利用栈或队列进行图的遍历，我显得无所适从，由于整体思路不清晰，许多判断条件不是特别明确，因此分的情况很多，实验的重复代码很多，包括用邻接多重表去建图，在添加一条边的时候，是否还应该再去判断其在链表中的位置，是插入表头，还是链表中，还是表尾。

数据结构求无向图连通子图问题输入多组数据，输入数据第一行为整数t，表示有几组测试数据。

每组测试数据由m+1行构成，第一行为两个正整数n（1<n<20）和m（1<m<100），分别表示顶点数（顶点编号为1,2,…,n）和边数，其后是m行数据，每行数据是一条边的信息，包括两个个数字，分别表示该边关联的两个顶点。

问题输出对每组测试数据输出两行信息，第一行输出该图中连通子图的个数。

第二行按照升序输出每个连通子图中顶点个数。

输入样例19 81 21 32 43 45 75 66 78 9输出样例32 3 4C语言实现求无向图连通子图个数及每个连通子图中顶点个数源代码#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX_VERTEX_NUM 20#define TRUE 1#define FALSE -1int visited[MAX_VERTEX_NUM];typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{int data;ArcNode *firstarc;}VNode,AdjList[ MAX_VERTEX_NUM];typedef struct{AdjList vertices;//头结点数组int vexnum,arcnum;}ALGraph;void CreateDG(ALGraph &G){int i,j,k,v1,v2;ArcNode *p,*q;scanf("%d%d",&G.vexnum,&G.arcnum);for(i=1;i<=G.vexnum;i++){G.vertices[i].data=i;G.vertices[i].firstarc=NULL;} for(k=0;k<G.arcnum;k++){scanf("%d%d",&v1,&v2);i=v1;j=v2;p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->nextarc = G.vertices[i].firstarc; // 插在表头G.vertices[i].firstarc = p;// 无向图产生第二个表结点p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = i;p->nextarc = G.vertices[j].firstarc; // 插在表头G.vertices[j].firstarc = p;}}int vs;void DFS(ALGraph G,int v){visited[v]=TRUE;vs++;//printf("true:%d ",v);ArcNode *p;for(p=G.vertices[v].firstarc;p;p=p->nextarc)if(visited[p->adjvex]==FALSE){// printf("v:%d",p->adjvex);DFS(G,p->adjvex);}}void DFSTraverse(ALGraph G){int v,i,j,among,count=0,vsum[MAX_VERTEX_NUM];for(v=1;v<=G.vexnum;v++)visited[v]=FALSE;for(v=1;v<=G.vexnum;v++){vs=0;if(visited[v]==FALSE){printf("lian:%d\n",v);DFS(G,v);vsum[count++]=vs; } }printf("%d\n",count);for(i=0;i<=count-1;i++)for(j=i+1;j<=count-1;j++)if(vsum[i]>vsum[j]){among=vsum[i];vsum[i]=vsum[j];vsum[j]=among;}for(i=0;i<count;i++)printf("%d ",vsum[i]);}int main(){int g;ALGraph G;scanf("%d",G);for(int i=0;i<g;i++){CreateDG(G);DFSTraverse(G);putchar('\n');}system("pause");return 0;}。

dfs判断连通图（⽆向）在中，连通图基于连通的概念。

在⼀个 G 中，若从vi到顶点vj有路径相连（当然从vj到vi也⼀定有路径），则称vi和vj是连通的。

如果 G 是，那么连接vi和vj的路径中所有的边都必须同向。

如果图中任意两点都是连通的，那么图被称作连通图。

如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。

图的是图的基本性质。

严格定义（摘抄）：对⼀个图G=(V,E) 中的两点x和y，若存在交替的和边的序列Γ=(x=v0-e1-v1-e2-...-ek-(vk+1)=y) (在中要求有向边vi−( vi+1)属于E )，则两点x和y是连通的。

Γ是⼀条x到y的连通路径，x和y分别是起点和终点。

当x = y时，Γ被称为回路。

如果通路Γ中的边两两不同，则Γ是⼀条简单通路，否则为⼀条复杂通路。

如果图G中每两点间皆连通，则G是连通图。

基本⽅法：简单的随便从⼀个点开始bfs，每遍历到⼀个点都将那个点打好标记，并且统计个数，在dfs退出以后⽐较统计的连通的点的个数是否等于我们的节点个数，等于则是连通图，不等则不是连通图。

代码如下：1 #include <iostream>2 #include <cstdio>3 #include <vector>4using namespace std;56const int maxn = 1000 + 5;78int n,m;9int my_index;1011 vector<int >G[maxn];12bool vis[maxn];1314void dfs(int u){15 my_index++;16 vis[u] = true;17for(int i = 0;i < G[u].size(); i++){18int v = G[u][i];19if(!vis[v])dfs(v);20 }21 }2223int main(){24 scanf("%d%d",&n,&m);25for(int i = 1;i <= m; i++){26int a,b;27 scanf("%d%d",&a,&b);28 G[a].push_back(b);29 G[b].push_back(a);30 }31 dfs(1);32if(n == my_index)printf("Yes\n");33else printf("No\n");34 }。

【数据结构】有向图、⽆向图以及最短路（Dijkstra）算法的C#实现（Template模式）为了写个“运筹学”的⼩⼯具，发现必须⽤到数据结构中的图。

找了⼀圈没有找到⾃⼰满意的，只能⾃⼰写⼀个。

所有代码基于C#，完全模板实现。

⾸先是顶点的定义，顶点可以是任意类型，但其ID为Int32，该ID只是Graph内部使⽤。

public sealed class GraphVertex<M>{#region Constructorpublic GraphVertex(){}#endregion#region Fieldsprivate Int32 nID = default(Int32);private M objData = default(M);#endregion#region Propertiespublic Int32 ID{get { return nID; }set { nID = value; }}public M Data{get { return objData; }set { objData = value; }}#endregion}然后是Edge的定义，这⾥有⼀个辅助的Struct：GraphEdgeCore，其负责真正的边的识别：：public struct GraphEdgeCore : IEquatable<GraphEdgeCore>{public GraphEdgeCore(Int32 i1, Int32 i2){ID1 = i1;ID2 = i2;}public Int32 ID1;public Int32 ID2;public Boolean IsValidated(){if (ID1 == -1 || ID2 == -1)return false;if (ID1 == ID2)return false;return true;}#region IEquatable<GraphEdgeCore> Memberspublic bool Equals(GraphEdgeCore other){if (ID1 != other.ID1) return false;if (ID2 != other.ID2) return false;return true;}#endregion#region Operatorspublic static Boolean operator == (GraphEdgeCore ec1, GraphEdgeCore ec2){return ec1.Equals(ec2);}public static Boolean operator != (GraphEdgeCore ec1, GraphEdgeCore ec2){return !(ec1 == ec2);}#endregionpublic override int GetHashCode(){return base.GetHashCode();}public override bool Equals(object obj){return (this == (GraphEdgeCore)obj);}}public sealed class GraphEdge<N>{#region Constructorpublic GraphEdge(Int32 n1, Int32 n2, N obj){edge.ID1 = n1;edge.ID2 = n2;objData = obj;}#endregion#region Fieldsprivate GraphEdgeCore edge;private N objData = default(N);#endregion#region Propertiespublic GraphEdgeCore EdgeCore{get { return edge; }}public N Data{get { return objData; }set { objData = value; }}#endregion}最⼤的难点来了：既然全部是模板，就不可避免会遇到权重的⽐较，因为是模板，所以必须定义⼀个额外的辅助类来实现：public abstract class ACGraphEdgeWeightAssistant<N> //: IComparable, IComparable<ACGraphEdgeWeightAssistant<N>>{#region Propertiespublic abstract N MinimumValue { get; }public abstract N MaximumValue { get; }#endregion#region Abstract methodspublic abstract N Add(N n1, N n2);public abstract N Subtract(N n1, N n2);public abstract Boolean Equals(N n1, N n2);public abstract Int32 Compare(N n1, N n2);public abstract Boolean IsMaximumValue(N nVal);#endregion//#region IComparable<ACGraphEdgeWeightAssistant<N>> Members//public int CompareTo(ACGraphEdgeWeightAssistant<N> other)//{// throw new NotImplementedException();//}//#endregion//#region IComparable Members//public int CompareTo(object obj)//{// return CompareTo(obj as ACGraphEdgeWeightAssistant<N>);//}//#endregion}最后是图的定义：public sealed class Graph<M, N> // where N : ValueType{#region Constructorpublic Graph(ACGraphEdgeWeightAssistant<N> objAss){System.Diagnostics.Debug.Assert(objAss != null);pAssist = objAss;}#endregion#region Fieldsprivate Dictionary<Int32, GraphVertex<M>> dictNodes = new Dictionary<int, GraphVertex<M>>();private List<GraphEdge<N>> listEdges = new List<GraphEdge<N>>();private Int32 nVertexID = 0;// Assistant for working for Nprivate ACGraphEdgeWeightAssistant<N> pAssist = null;#endregion#region Propertiespublic Int32 NodesAmount{get { return dictNodes.Count; }}public Int32 EdgesAmount{get { return listEdges.Count; }}#endregion#region Public methodspublic void InsertVertex(GraphVertex<M> objVertex){System.Diagnostics.Debug.Assert(objVertex != null);objVertex.ID = nVertexID++;dictNodes.Add(objVertex.ID, objVertex);}public void InsertEdge(GraphEdge<N> objEdge){System.Diagnostics.Debug.Assert(objEdge != null);if (!objEdge.EdgeCore.IsValidated())return;if (!dictNodes.ContainsKey(objEdge.EdgeCore.ID1))return;if (!dictNodes.ContainsKey(objEdge.EdgeCore.ID2))return;listEdges.Add(objEdge);}public GraphEdge<N>[] GetEdges(GraphEdgeCore objEdgeCore){List<GraphEdge<N>> lists = new List<GraphEdge<N>>();foreach (GraphEdge<N> ge in listEdges){if (ge.EdgeCore == objEdgeCore)lists.Add(ge);}return lists.ToArray();}public GraphEdge<N>[] GetEdges(Int32 nID, Boolean bSource){List<GraphEdge<N>> lists = new List<GraphEdge<N>>();foreach (GraphEdge<N> ge in listEdges){if (bSource){if (ge.EdgeCore.ID1 == nID)lists.Add(ge);}else{if (ge.EdgeCore.ID2 == nID)lists.Add(ge);}return lists.ToArray();}public GraphEdge<N>[] GetAllEdges(){return listEdges.ToArray();}public GraphVertex<M>[] GetAllVerteics(){List<GraphVertex<M>> listVer = new List<GraphVertex<M>>();foreach (GraphVertex<M> gv in dictNodes.Values)listVer.Add(gv);return listVer.ToArray();}// Get shortest path// Note: call this method before you make sure that the weight should not negative.public void DijkstraShortestPath(Int32 nSource, Int32 nTarget, List<GraphPath<N>> listPaths) {System.Diagnostics.Debug.Assert(listPaths != null);listPaths.Clear();GraphPath<N> gp = null;if (!dictNodes.ContainsKey(nSource))return;if (!dictNodes.ContainsKey(nTarget))return;if (nSource == nTarget){gp = new GraphPath<N>();gp.CurrentCost = pAssist.MinimumValue;gp.PathNodes.Add(nSource);listPaths.Add(gp);return;}Dictionary<Int32, N> dictPSet = new Dictionary<Int32, N>();Dictionary<Int32, N> dictTSet = new Dictionary<Int32, N>();// InitializedictPSet.Add(nSource, pAssist.MinimumValue);foreach (Int32 nVer in dictNodes.Keys){if (nVer != nSource)dictTSet.Add(nVer, pAssist.MaximumValue);}while (!dictPSet.ContainsKey(nTarget)){// Go through each item in P Setforeach (Int32 nID in dictPSet.Keys){foreach (GraphEdge<N> ge in GetEdges(nID, true)){if (dictTSet.ContainsKey(ge.EdgeCore.ID2)){// Update the T value: min { P(X) + W, T(X) }N nTValue = dictTSet[ge.EdgeCore.ID2];N nPValue = dictPSet[nID];N nVal = pAssist.Add(nPValue, ge.Data);if (pAssist.IsMaximumValue(nTValue)){dictTSet[ge.EdgeCore.ID2] = nVal;}else{if (pare(nTValue, nVal) > 0){dictTSet[ge.EdgeCore.ID2] = nVal;}}}}}// Get the minimum of TSetInt32 nTID = default(Int32);N ntmp = pAssist.MaximumValue;foreach (KeyValuePair<Int32, N> kvp in dictTSet)if (pare(kvp.Value, ntmp) < 0){ntmp = kvp.Value;nTID = kvp.Key;}}if (nTID == default(Int32))break;dictTSet.Remove(nTID);dictPSet.Add(nTID, ntmp);}// OKay, we get the final result, parse the result outgp = new GraphPath<N>();gp.CurrentID = nTarget;gp.CurrentCost = dictPSet[nTarget];gp.PathNodes.Add(nTarget);listPaths.Add(gp);Boolean bEnd = false;Boolean bExisted = false;List<GraphPath<N>> listTempPaths = new List<GraphPath<N>>();while (!bEnd){bExisted = false;listTempPaths.Clear();foreach (GraphPath<N> gpath in listPaths){if (gpath.DeadPath)continue;foreach (GraphEdge<N> ge in GetEdges(gpath.CurrentID, false)){//dictPSet[ge.Data]if (dictPSet.ContainsKey(ge.EdgeCore.ID1)&&pare(gpath.CurrentCost, pAssist.Add(ge.Data, dictPSet[ge.EdgeCore.ID1])) == 0) {if (!bExisted){gpath.CurrentID = ge.EdgeCore.ID1;gpath.PathNodes.Add(ge.EdgeCore.ID1);gpath.CurrentCost = dictPSet[ge.EdgeCore.ID1];bExisted = true;}else{// Existed already in currentGraphPath<N> gp2 = new GraphPath<N>(gpath);gp2.CurrentID = ge.EdgeCore.ID1;gp2.PathNodes.Add(ge.EdgeCore.ID1);gp2.CurrentCost = dictPSet[ge.EdgeCore.ID1];listTempPaths.Add(gp2);}}}if (!bExisted){gpath.DeadPath = true;}}foreach (GraphPath<N> gpath in listTempPaths)listPaths.Add(gpath);foreach (GraphPath<N> gpath in listPaths){if ((!gpath.DeadPath) && gpath.PathNodes.Contains(nSource)){bEnd = true;break;}}}// Finalize the result outputforeach (GraphPath<N> gpth in listPaths){if (gpth.DeadPath)listPaths.Remove(gpth);elsegpth.CurrentCost = dictPSet[nTarget];}}#endregion}其中，代表路径使⽤了另外⼀个类：public sealed class GraphPath<N> : ICloneable{#region Constructorpublic GraphPath() { }public GraphPath(GraphPath<N> other): this(){if (other != null){nCurID = other.nCurID;curCost = other.curCost;foreach (Int32 n in other.listPath)listPath.Add(n);}}#endregion#region Fieldsprivate List<Int32> listPath = new List<Int32>();private Int32 nCurID = default(Int32);private N curCost = default(N);private Boolean bDeadPath = false;#endregion#region Propertiespublic List<Int32> PathNodes{get { return listPath; }}public Int32 CurrentID{get { return nCurID; }set { nCurID = value; }}public N CurrentCost{get { return curCost; }set { curCost = value; }}public Boolean DeadPath{get { return bDeadPath; }set { bDeadPath = value; }}#endregion#region ICloneable Memberspublic object Clone(){return new GraphPath<N>(this);}#endregion}使⽤实例：public sealed class ACGraphEdgeWeightSingleAssistant : ACGraphEdgeWeightAssistant<Single> {public override float MinimumValue{get { return0; }}public override float MaximumValue{get { return Single.MaxValue; }}public override float Add(float n1, float n2){return n1 + n2;}public override float Subtract(float n1, float n2){return n1 - n2;}public override bool Equals(float n1, float n2){return n1 == n2;}public override int Compare(float n1, float n2){if (n1 > n2) return1;if (n1 < n2) return -1;return0;}public override bool IsMaximumValue(float nVal){return nVal == Single.MaxValue;}}ACGraphEdgeWeightSingleAssistant objWSA = new ACGraphEdgeWeightSingleAssistant();Dictionary<Char, Int32> dictVer = new Dictionary<Char, Int32>();Graph<Char, Single> gph = new Graph<Char, Single>(objWSA);GraphVertex<Char> gv = new GraphVertex<char>();gv.Data = '1'; gph.InsertVertex(gv);dictVer.Add('1', gv.ID);gv = new GraphVertex<char>(); gv.Data = '2'; gph.InsertVertex(gv); dictVer.Add('2', gv.ID);gv = new GraphVertex<char>(); gv.Data = '3'; gph.InsertVertex(gv); dictVer.Add('3', gv.ID);gv = new GraphVertex<char>(); gv.Data = '4'; gph.InsertVertex(gv); dictVer.Add('4', gv.ID);gv = new GraphVertex<char>(); gv.Data = '5'; gph.InsertVertex(gv); dictVer.Add('5', gv.ID);gv = new GraphVertex<char>(); gv.Data = '6'; gph.InsertVertex(gv); dictVer.Add('6', gv.ID);GraphEdge<Single> ge = new GraphEdge<float>(dictVer['1'], dictVer['2'], 4);gph.InsertEdge(ge);ge = new GraphEdge<float>(dictVer['1'], dictVer['3'], 3);gph.InsertEdge(ge);ge = new GraphEdge<float>(dictVer['2'], dictVer['4'], 3);gph.InsertEdge(ge);ge = new GraphEdge<float>(dictVer['2'], dictVer['5'], 2);gph.InsertEdge(ge);ge = new GraphEdge<float>(dictVer['3'], dictVer['5'], 3);gph.InsertEdge(ge);ge = new GraphEdge<float>(dictVer['4'], dictVer['6'], 2);gph.InsertEdge(ge);ge = new GraphEdge<float>(dictVer['5'], dictVer['6'], 2);gph.InsertEdge(ge);List<GraphPath<Single>> listPaths = new List<GraphPath<Single>>();gph.DijkstraShortestPath(dictVer['1'], dictVer['6'], listPaths);注意：对Dijkstra算法来说，其基本要求权重必须⾮负！根据上述代码可以轻易的实现对权重⽆要求的Floyd算法。

用python实现无向图的连通性判断import numpy as npimport networkx as nximport matplotlib.pyplot as pltfrom random import random,choice'''算法描述：在用Fleury方法寻找欧拉回路的时候需要判断一条边删除之后余下的部分是否为连通图这个程序用来判断一个图形是否为连通图1.如果邻接矩阵中有零行，则可直接判断此图不联通2.如果不联通就收缩一条边，将两个端点合并3.持续进行2操作，如果最后所有的点都能收缩到一起，说明连通，如果不能收缩到一起，说明不联通程序会按照你的输入生成一个随机的图形，并打印判断结果和画出图像算法来自《关于Fleury算法的一点注记》（吕义忠）'''n=int(input('input node number: ')) #输入节点数目m=int(input('input edge number: ')) #输入边数while m>((n-1)*n/2):print ('too many edges,input again')n=int(input('input node number: ')) #输入节点数目m=int(input('input edge number: ')) #输入边数G = nx.Graph() #实例化nxfor i in range(n): #添加点G.add_node(i)counter=0while counter < m: #添加9条边a=choice(range(n))b=choice(range(n))if ((a,b) not in G.edges()) and (a!=b) and ((b,a) not in G.edges()):G.add_edge(a,b)counter+=1def drawit(): #画图方法pos=nx.spring_layout(G) #散点的排列模式为spring模式nx.draw(G,pos)plt.show()def xor(a,b): #定义一个向量的亦或方法，返回异或运算后的向量la=len(a)lb=len(b)c=zip(a,b)L=[]try:for ai,bi in c:if ai==bi:L.append(0)else:L.append(1)return Lexcept Exception as e:print(e)returnM=np.zeros((n,m)) #创建邻接矩阵的雏形eds=G.edges()eds=dict(map(lambda i,j:[i,j],list(range(m)),eds)) #将边编号，用字典表示def connA(): #建立邻接矩阵for i in range(m):for j in range(n):if (eds[i][0]==j) or (eds[i][1])==j:M[j][i]=1def inspectzeros(): #检查是否有零行for i in range(len(M)):if sum(M[i])==0:flag=Falsereturn ireturndef delline(Flag): #删除一行M1=M[:Flag]M2=M[Flag+1:]Mc=np.vstack((M1,M2))return Mcif __name__=='__main__': #主函数try:connA()Flag=inspectzeros()#print(M)if Flag is not None:#delline(Flag)print('it has at least two parts') else:while len(M)>1:for j in range(m):if M[0][j]!=0:for i in range (1,n):if M[i][j]!=0:#print (i,j)M[0]=xor(M[0],M[i])M=delline(i)breakbreakif sum(M[0])==0 and len(M)>1: print ('it has at least two parts') breakelse:print('it is connected')drawit()except Exception as e:print(e)。

C#图表算法之⽆向图⽬录1.相关术语2.表⽰⽆向图的数据结构3.图的处理算法的设计模式4.深度优先搜索5.寻找路径实现6.⼴度优先搜索实现7.连通分量实现union-find 算法8.符号图实现间隔的度数总结图是由⼀组顶点和⼀组能够将两个顶点相连的边组成。

顶点叫什么名字并不重要，但我们需要⼀个⽅法来指代这些顶点。

⼀般使⽤ 0 ⾄ V-1 来表⽰⼀张含有 V 个顶点的图中的各个顶点。

这样约定是为了⽅便使⽤数组的索引来编写能够⾼效访问各个顶点信息的代码。

⽤⼀张符号表来为顶点的名字和 0 到 V-1 的整数值建⽴⼀⼀对应的关系并不困难，因此直接使⽤数组索引作为结点的名称更⽅便且不失⼀般性，也不会损失什么效率。

我们⽤ v-w 的记法来表⽰连接 v 和 w 的边， w-v 是这条边的另⼀种表⽰⽅法。

在绘制⼀幅图时，⽤圆圈表⽰顶点，⽤连接两个顶点的线段表⽰边，这样就能直观地看出图地结构。

但这种直觉有时可能会误导我们，因为图地定义和绘制地图像是⽆关的，⼀组数据可以绘制不同形态的图像。

特殊的图⾃环：即⼀条连接⼀个顶点和其⾃⾝的边；多重图：连接同⼀对顶点的两条边成为平⾏边，含有平⾏边的图称为多重图。

没有平⾏边的图称为简单图。

1.相关术语当两个顶点通过⼀条边相连时，称这两个顶点是相邻得，并称这条边依附于这两个顶点。

某个顶点的度数即为依附于它的边的总数。

⼦图是由⼀幅图的所有边的⼀个⼦集（以及它们所依附的所有顶点）组成的图。

许多计算问题都需要识别各种类型的⼦图，特别是由能够顺序连接⼀系列顶点的边所组成的⼦图。

在图中，路径是由边顺序连接的⼀系列顶点。

简单路径是⼀条没有重复顶点的路径。

环是⼀条⾄少含有⼀条边且起点和终点相同的路径。

简单环是⼀条（除了起点和终点必须相同之外）不含有重复顶点和边的环。

路径或环的长度为其中所包含的边数。

当两个顶点之间存在⼀条连接双⽅的路径时，我们称⼀个顶点和另⼀个顶点是连通的。

如果从任意⼀个顶点都存在⼀条路径到达另⼀个任意顶点，我们称这副图是连通图。

#include<>#include<>#include<>#define M 50typedef char vextype;exdata=ch;irstarc=NULL;irstarc;ag[i].firstarc=p;irstarc;ag[j].firstarc=p;exdata=ch;irstarc=NULL;irstarc;ag[i].firstarc=p;exdata<<" ";p=ag[v].firstarc;exdata<<" ";q[0]=v;w hile(f<=r){v=q[f++];p=g[v].firstarc;while(p!=NULL){v=p->adjvex;if(c[v]==0){c[v]=1;cout<<g[v].vexdata<<" ";q[++r]=v;}p=p->link;}}}/*BFS*/void main(){i nt n=0,j,k,kind,i;c har flag='y';int f[M];v exnode v1[M],v2[M];while(flag=='y'){cout<<"请选择图的种类(1代表有向图，2代表无向图)"<<endl;cin>>kind;//输入图的种类switch(kind){case 1:cout<<"---------------创建有向图---------------"<<endl;creatlist1(v1,n);//创建有向图cout<<"开始遍历的结点序号为:";cin>>j;for(i=0;i<M;i++)f[i]=0;cout<<"深度遍历为:";DFS(v1,j,f);//深度遍历cout<<endl;for(i=0;i<M;i++)f[i]=0;cout<<"广度遍历为:";BFS(v1,j,f);//广度遍历break;case 2:cout<<"---------------创建无向图----------------"<<endl;creatlist2(v2,n);//创建无向图cout<<"开始遍历的结点序号为:";cin>>k;for(i=0;i<M;i++)f[i]=0;cout<<"深度遍历为:";DFS(v2,k,f);//深度遍历cout<<endl;for(i=0;i<M;i++)f[i]=0;cout<<"广度遍历为:";BFS(v2,k,f);//广度遍历break;default:cout<<"输入错误,程序结束!"<<endl;return;}cout<<endl;cout<<"是不是继续?(输入n结束,输入y有效!)"<<endl;cin>>flag;}cout<<"程序结束，再会!"<<endl;}。

求无向连通图的生成树一、实验目的⑴掌握图的逻辑结构⑵掌握图的邻接矩阵存储结构⑶验证图的邻接矩阵存储及其遍历操作的实现二、实验内容(1)建立无向图的邻接矩阵存储(2)对建立的无向图,进行深度优先遍历(3)对建立的无向图进行广度优先遍历三、设计与编码(1)本实验用到的理论知识(2)算法设计(3)编码// 图抽象类型及其实现、cpp : Defines the entry point for the console application、//#include"stdafx、h"#include"Graph、h"#include"iostream、h"int Graph::Find(int key,int &k){int flag=0;for(int i=0;i<VertexLen;i++)if(A[i]、data、key==key){k=i;flag=1;break;};return flag;};int Graph::CreateGraph(int vertexnum,Edge *E,int edgenum) { //由边的集合E(E[0]~E[VertexNum-1]),生成该图的邻接表表示if(vertexnum<1)return(-1);//参数vertexnum非法int i,front,rear,k;Enode *q;//先生成不带边表的顶点表--即顶点为孤立顶点集A=new Vnode[vertexnum];if(!A)return(0);//堆耗尽for(i=0;i<vertexnum;i++){A[i]、data、key=i;A[i]、tag=0;A[i]、data、InDegree=A[i]、data、OutDegree=A[i]、tag=0;A[i]、first=0;};VertexLen=vertexnum;//在生成边表if(edgenum<0)return(1);//无边的图for(i=0;i<edgenum;i++){front=E[i]、Head;rear=E[i]、Tail;if(!Find(rear,k) || !Find(front,k))return(-2);//参数E非法q=new Enode;if(!q)return(0);q->key=front;q->Weight=E[i]、weight;q->next=A[rear]、first;A[rear]、first=q;A[rear]、data、OutDegree++;A[front]、data、InDegree++;if(Type>2){q=new Enode;if(!q)return(0);q->key=rear;q->next=A[front]、first;A[front]、first=q;q->Weight=E[i]、weight;};};return(1);};void Graph::Dfs(int key,int &flag){//static run=1;Enode *w;A[key]、tag=flag;if(Type>2)cout<<"连通分量="<<flag<<'\t';cout<<"顶点键值="<<key<<endl;for(w=A[key]、first;w ;w=w->next)if(!A[w->key]、tag)Dfs(w->key,flag);};int Graph::DfsDravers(int v0) //从指定顶点深度遍历{int i,k,componentnum=1;//if(Type<3)return(-1);//不考虑由向图//cout<<"begain、、、、\n";if(!(Find(v0,k))){cout<<"find=="<<k<<endl;return(0);};//初始结点v0不存在if(Type>2)cout<<"---连通分量"<<componentnum<<"---"<<endl;Dfs(k,componentnum);componentnum++;for(i=0;i<VertexLen;i++){if(!A[i]、tag){if(Type>2)cout<<"---连通分量"<<componentnum<<"---"<<endl;Dfs(i,componentnum);componentnum++;};};return(componentnum-1);};int Graph::Bfs(){int i,comp=1; //comp=连通分量的标记,、、、、、struct queue{int key;queue * next;};Enode *pe;queue *f,*r,*q,*p=new queue;if(!p)return(-1); //堆耗尽p->next=0;f=r=p; //生成空队列for(i=0;i<VertexLen;i++)A[i]、tag=0;//初始化已访问标志for(i=0;i<VertexLen;i++){if(A[i]、tag==0){A[i]、tag=comp;//入队该顶点的keyp=new queue;if(!p)return(-1);p->key=A[i]、data、key;p->next=0;f->next=p;r=p;while(f->next)//当队非空时{//出队一顶点q=f->next;if(Type>2)cout<<"连通分量"<<comp<<'\t';cout<<"顶点键值="<<q->key<<endl;f->next=q->next;if(q==r)r=f; //与q连接的未访问的顶点入队pe=A[q->key]、first;while(pe){if(A[pe->key]、tag==0){//入队if(!(p=new queue))return(-1);A[pe->key]、tag=comp;p->key=pe->key;p->next=0;if(f==r)f->next=p;r->next=p;r=p;};pe=pe->next;};//end of (pe)delete q;};//end of (f->next)comp++;};//enf of if};//释放队列while(f){p=f->next;delete f;f=p;};return comp-1; //返回连通分量数};/*int Graph::TopoSort(int *que,int &num){ //que顺序队列保存了拓扑排序的结果,f与r为que的头尾指示;loop用于判有无环int i,f=0,r=0,index,loop=1;Enode *pe;num=0;for(i=0;i<VertexLen;i++)A[i]、tag=A[i]、data、InDegree;//初始化入度到tag域for(i=0;i<VertexLen;i++)if(A[i]、tag==0){que[r++]=i;A[i]、tag=-1;loop=0;};if(loop)return(0);while(f<r){//栈未处理完index=que[f++];for(pe=A[index]、first;pe;pe=pe->next){A[pe->key]、tag--;if(A[pe->key]、tag==0){que[r++]=pe->key;A[pe->key]、tag=-1;};};};num=r;if(r<VertexLen)return(0);//存在环return 1;};int main(int argc, char* argv[]){ Graph g1(1);int num=5,temp=1;int *stack=new int[5];Edge b[12];b[0]、Head=1;b[0]、Tail=0;b[0]、weight=1;b[1]、Head=3;b[1]、Tail=1;b[1]、weight=1;b[2]、Head=0;b[2]、Tail=2;b[2]、weight=1;b[3]、Head=1;b[3]、Tail=4;b[3]、weight=1;b[4]、Head=4;b[4]、Tail=2;b[4]、weight=1;b[5]、Head=4;b[5]、Tail=3;b[5]、weight=1;//b[6]、Head=0;b[6]、Tail=1;b[6]、weight=1;b[7]、Head=1;b[7]、Tail=3;b[7]、weight=1;b[8]、Head=2;b[8]、Tail=0;b[8]、weight=1;b[9]、Head=4;b[9]、Tail=1;b[9]、weight=1;b[10]、Head=2;b[10]、Tail=4;b[10]、weight=1;b[11]、Head=3;b[11]、Tail=2;b[11]、weight=1;//b=={{1,0,1},{3,1,1},{0,2,1},(1,4,1},{4,2,1},{2,3,1}};g1、CreateGraph(num,b,6);if(g1、GetType()>2)cout<<"连通分量数="<<g1、DfsDravers(2)<<endl;cout<<"--------------"<<endl;if(g1、GetType()>2)cout<<"连通分量数="<<g1、Bfs()<<endl;if(g1、GetType()<3){if(g1、TopoSort(stack,temp))cout<<"拓扑排序成功！\n";else cout<<"该图有环！\n";cout<<"部分或全部的拓扑序列为:(顶点总数="<<g1、GetLen()<<")\n";for(int i=0;i<temp;i++)cout<<stack[i]<<'\t';cout<<"已排序顶点数目="<<temp<<endl;};delete[5]stack;//printf("Hello World!\n");return 0;}四、运行与调试运行结果为:该图有环！部分或全部拓扑序列为:<顶点总数=5>2 0 已排序顶点数目=2 Press any key to continue五、总结与心得。

CHAPTER 6GRAPHS, DIRECTED GRAPHS, AND TREESGlossarygraph：（无向）图vertex set：顶点集edge set：边集endpoint：端点incident on：关联于adjacent：邻接simple graph：简单（无向）图loop：自回路，环multigraph：多（重）图labeled graph：标号图pseudograph：伪图utility：公用事业designing a chip：设计芯片planar graph：平面图degree：度isolated vertex：孤立结点subgraph：子图path：通路，路径simple path：基本路径connected：连通的component：连通分支cycle：回路simple cycle：基本回路complete graph：完全图bipartite graph：二部图，偶图complete bipartite graph：完全二部图directed graph(digraph)：有向图directed edge：有向边initial vertex：起点terminal vertex：终点outdegree：出度indegree：入度source：源sink：汇directed multigraph：有向多重图labeled directed graph：有向标记图directed subgraph：有向子图directed path：有向通路（路径）underlying graph：底图strongly connected：强连通tree：树directed tree：有向树asymmetric：非对称的leaf：叶（结点）internal vertex：分支结点root：根结点rooted tree：（有）根树level：级height：高度parent：父结点child：子结点siblings：兄弟结点ancestor：祖先descendant：后代binary tree：二元（叉）树m-ary tree：m元（叉）树spanning tree：生成树，支撑树Euler cycle：欧拉回路Euler path：欧拉通路incidence matrix：关联矩阵adjacency matrix：邻接矩阵representation matrix：表示矩阵Warshall’s algorithm：Warshall算法adjacency list representation：邻接链表表示本章内容及教学要点：Graphs教学内容：graph，vertex，edge，adjacent，incident，endpoints，loop，multigraph，pseudograph，degree，isolated vertex，subgraph，path，simple path，connected，component，cycle，simple cycle，complete graph，bipartite graphDirected Graphs教学内容：directed graph，directed edge，outdegree，indegree，directed path，underlying graph，strongly connectedTrees教学内容：tree，directed tree，leaf，internal vertex，root，rooted tree，binary tree，m-ary tree，spanning treeEuler Paths and Cycles教学内容：Euler cycle，Euler pathIncidence and Adjacency Matrices教学内容：adjacency matrix定理证明及例题解答Graph theory is an old subject with many modern applications. Its basic ideas were introduced in the eighteenth century by the great Swiss mathematician Leonard Euler. He used graphs to solve the famous Konisberg bridge problem.Graphs are used to solve problems in many fields. For instance, graphs can be used to determine whether a circuit can be implemented on a planar board. Graphs can be used to study the structure of the WWW. We can determine whether two computers are connected by a communications link using graph models of computer networks. Weighted graphs can be used to solve problems such as finding the shortest path between two cities in a transportation network. We can also use graphs to schedule exams and assign channels to television stations.图论是以图为研究对象的数学分支. 图论中的图指的是一些点以及连接这些点的线的总体. 通常用点代表事物，用连接两点的线代表事物间的关系. 图论则是研究事物对象在上述表示法中具有的特征与性质的学科.在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观. 例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了. 另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系(芯片设计)等等.事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟. 由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要. 由此经数学抽象产生了图的概念. 研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容.计算机中数据结构离不开数组、串、链表、树和图. 图是计算机中数据表示、存储和运算的基础.图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：第一阶段是从1736年到19世纪中叶. 当时的图论问题是盛行的迷宫问题和游戏问题. 最有代表性的工作是著名数学家Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem).东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被这条河、它的分支和岛分成了四个部分，各部分通过7座桥彼此相通. 该城的居民喜欢在星期日绕城散步. 久而久之就产生了这样一个问题：能不能设计一条散步的路线，使得一个人从家里（或从四部分陆地任一块）出发，经过每座桥恰好一次再回到家里这就是有名的哥尼斯堡七桥问题.哥尼斯堡七桥问题看起来并不复杂，因此立刻吸引所有人的注意，但是实际上很难解决.瑞士数学家(Leonhard Euler)注意到了这个问题，并在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题. 这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父.欧拉把七桥问题抽象成数学问题—一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解. Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在Euler证明这样的回路是不存在的.第二阶段是从19世纪中叶到1936年. 一开始，图论的理论价值似乎不大，因为图论主要研究一些娱乐性的游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题. 但是随着一些图论中的著名问题如四色问题(1852年)和Hamilton 环游世界问题(1856年)的出现，出现了以图为工具去解决其它领域中一些问题的成果. 1847年德国的克希霍夫将树的概念和理论应用于工程技术的电网络研究. 1857年英国的凯莱也独立地提出了树的概念，并应用于有机化合物分子结构（C2H2n+2的同分异构物数目）的研究中. 1936年匈牙利的数学家哥尼格写出了第一本图论专著《有限图与无限图的理论》(Theory of directed and Undirected Graphs). 标志着图论成为一门独立学科.第三阶段是1936年以后. 由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展. 特别是电子计算机的大量应用，使大规模问题的求解成为可能. 实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决. 目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用.Graphs定义6.1.1 A graph(无向图，图) is a finite set V called the vertex set(顶点集) and a collection E of two-element subsets of V called the edge set(边集). An element of E is called an edge(边). A graph is denoted by G(V,E). The elements a and b of V are joined or connected(连接) by the edge{a,b} if {a,b}∈E.Graphs are usually represented by diagrams using dots for vertices and lines between their dots for edges.定义6.1.2If {a,b}∈E is an edge in a graph G(V,E), then the vertices a and b are called the endpoints(终点) of the edge{a,b}. The edge {a,b} is also said to be incident on(关联于) the vertices a and b. Conversely, the vertices a and b are said to be incident on(关联于) the edge {a,b}. Two vertices a and b are adjacent(邻接结点) if they are endpoints of an edge. Two edges are adjacent(邻接边) if they are incident on a common vertex.例6.1.1The graph G with V={a,b,c} and E={{a,b},{b,c}}.例 6.1.2The graph G with V={a,b,c,d,e} and E={{a,b},{a,e},{b,e},{b,d},{b,c},{c,d)}}.定义6.1.3The graph G(V,E) is called a simple graph(简单图)if there is at most one edge between any two vertices and no edge from a vertex to itself. An edge from a vertex to itself is called a loop(自回路，环). Edges between two vertices are called parallel edges(平行边，多重边). In a multigrpah(多重图，多图), there may be parallel edges between two vertices. In a pseudograph(伪图), there may include parallel edges between twovertices and loops.定义6.1.4The degree(度数)of a vertex v, denoted by deg(v), is the number of edges that are incident on the vertex. A vertex with degree 0 is called isolated(孤立的).在一个图中，以v为端点的边数称为v的度数，记为deg(v), 度数为0的顶点称为孤立结点.Euler握手定理定理6.1.1 (The Handshaking Theorem) Let G(V,E) be a graph. Then∑∈Vvdeg(v)=2|E|.That is, the sum of the degrees of the vertices of a graph is always even.一个图的所有结点的度数之和是边数的两倍，从而是偶数.定理6.1.2 In any graph, there is an even number of vertices whose degree is odd.在任何图中，度数为奇数的结点为偶数个.证明定理定义6.1.5 A graph G’(V’,E’) is a subgraph(子图) of a graph G(V,E), denoted by G’(V’,E’) G(V,E), if V’⊆V and E’⊆E.定义6.1.6Let G(V,E) be a graph with vertices v0,vk∈V. A path (通路，路径) of length k from v0to vkor between vand vkis a sequencev 0e1v1e2v2e3v3…vk-1ekvksuch that v,v1,…,vk∈V, e1,e2,…,ek∈E and ei={vi-1,vi}.For simplicity, we denote this path as v0v1v2v3…vk-1vk. A simple path(基本路径) from v0 to vkis a path in which no vertex is repeated.在图G(V,E)中，设v0,v1,…,vk∈V，e1,e2,…,e k∈E，其中v i-1，v i是边e i的端点(i=1,2,…,k). 称v0e1v1e2v2e3v3…vk-1ekvk为从顶点v到vk的通路(路径)，v和v分别称为该通路的起点和终点；称通路上的边数k为该通路的长度.若通路经过m的顶点各不相同，则称该通路为基本通路.例6.1.3求下图的通路、基本通路.解例定义6.1.7 A graph G is called connected(连通的) if there is a pathfrom any vertex to any other vertex in the graph. Otherwise, the graph isdisconnected(不连通的).给定无向图G(V,E)且u,v V. 若存在从u到v的通路，则称从u到v是可达的或称u可达v. 若G的任何两个顶点是相互可达的，则称G是连通图，否则称G是不连通图.定理6.1.3 Let G(V,E) be a graph. If there is a path from a vertex u toa vertex v, then there is a simple path from u to v.证明定理事实上，在一个具有n 个顶点的无向图中，任何基本通路的长度均不大于n-1.推论 A graph G is connected if and only if there is a simple path betweenany two vertices in G.定义6.1.8Let G(V,E) be a graph. A subgraph G’ of G is a component (连通分支) of G if(1) G’ is a nonempty connected graph and(2) if G” is a connected subgraph of G and G’ G” then G’=G”.当G是一个非连通图时，它的独立的不同连通部分称为它的连通分支.定义6.1.9Let G(V,E) be a graph. A cycle(回路)is a path of length greaterthan zero from a vertex to itself with no repeated edges. A simple cycle(基本回路)is a cycle from a vertex v to itself such that v is the only vertexthat is repeated.例6.1.4求下图的回路、基本回路.解例定义6.1.10 A graph is a complete graph(无向完全图) if there is anedge between every two distinct vertices. A complete graph with n verticesis denoted by Kn.例6.1.5K2，K3，K4，K5.解例定义6.1.11Let G(V,E) be a graph. G is called a bipartite graph (二部图，偶图) if its vertex set V can be partitioned into two disjoint sets A and B such that every edge in the graph connects a vertex in A and a vertex in B(so that no edge in G connects either two vertices in A or two vertices in B).A bipartite graph is called a complete bipartite graph(完全二部图) Km,n if A contain m vertices, B contains n vertices, and for every a∈A,b∈B, {a,b}∈E. Thus, for every a∈A and b∈B, there is an edge connecting them.给定简单无向图G(V，E)，V= A⋃B，A⋂B=Φ. 若G中任一条边的两个端点，一个属于A，另一个属于B，则称G为二部图(偶图) . 若|A|=m，|B|=n，且对任意u∈A，v∈B，u与v有边相连，则称G为完全二部图，记为Km,n. ASSIGNMENTS：PP140：2，4，6，8，10，12，18，20，24，26，28，30Directed Graphs定义6.2.1 A directed graph or digraph(有向图) G(V,E), consists of a set V of vertices, together with a set E of ordered pairs of V called the set of directed edges(有向边). If (a,b) ∈E, then a is called the initial vertex(起点) of (a,b) and b is called the terminal vertex(终点).The edge (a,b) of a digraph is denoted on the diagram by an arrow from a to b.例6.2.1 The digraph G with V={a,b,c} and E={(a,b),(b,c),(c,b),(c,a)}.例 6.2.2The digraph G with V={a,b,c,d} and E={(a,b),(b,c),(c,c),(b,d),(d,b),(c,d),(d,a)}.定义6.2.2 The outdegree(出度) of a vertex v, denoted by outdeg(v), is the number of edges for which v is the initial vertex. The indegree(入度) of a vertex v, denoted by indeg(v), is the number of edges for which v is the terminal vertex. If indeg(v)=0, then v is called a source(源). If outdeg(v)=0, then v is called a sink(汇).例 6.2.3The digraph G with V={a,b,c,d,e} and E={(a,b),(a,b),(a,c),(b,c),(b,e),(c,d),(c,e),(d,e)}.indeg(a)=0, indeg(b)=1, indeg(c)=2, indeg(d)=2, indeg(e)=3outdeg(a)=3, outdeg(b)=2, outdeg(c)=2, outdeg(d)=1, outdeg(e)=0a is a source and e is a sink.Similar to graphs, directed multigraphs, labeled digraphs and directed subgraphs can be defined.定义6.2.3 A directed path(有向通路)of length k from a to b is describedby a sequence of vertices v0v1v2v3…vk-1vkwhere v=a and vk=b, and (vi-1,vi) isa directed edge for 1≤i≤k.例 6.2.4The digraph G with V={a,b,c,d,e} and E={(a,b),(a,b),(a,c),(b,c),(b,e),(c,d),(c,e),(d,e)}.定义6.2.4 Let G(V,E) be a digraph and G’(V,E’) be a directed subdigraph of G with the loops removed,. E’=E-{(v,v): v∈V}. Let E”be the symmetric closure of E’ and E s be the set of edges representing the relation E”. Then the graph G s(V,E s) is called the underlying graph(底图) of G.定义 6.2.5 A digraph G(V,E) is connected(弱连通的) if its underlying graph is connected. A digraph G(V,E) is strongly connected(强连通的) if for every pair of vertices a,b∈V, there is a directed path from a to b.例6.2.5 PP144-145: 19, 21,27,29.定理6.2.1 (The Handshaking Theorem) Let G(V,E) be a digraph. Then ∑deg(v)=2|E|,v∈V∑outdeg(v)=|E|,v∈V∑indeg(v)=|E|.∈VvASSIGNMENTS：PP143-145：4，6，8，20，22，24，26，28，34Trees树是图论中一个既简单又非常重要的概念，在计算机科学中应用很广泛，是一种基本的数据结构和表示方法. 1847年德国的克希霍夫将树的概念和理论应用于工程技术的电网络研究. 1857年英国的凯莱也独立地提出了树的概念，并应用于有机化合物分子结构（C2H2n+2的同分异构物数目）的研究中.定义6.3.1 A tree(无向树，树) is a connected graph that has no cycles. The vertices of degree 1 are called leaves(叶结点) and other vertices are called internal vertices(分支结点).树是一个没有回路的连通无向图. 若一个不连通的无向图的所有连通分支都是树，则称该无向图为森林.定义 6.3.2 A directed tree(有向树) is a loop-free digraph, whose underlying graph is a tree.In a directed tree, if there is a path from a vertex a to a vertex b, it is unique.例6.3.1无向树.解例定理6.3.1 For any two vertices a and b of a tree T, there is a unique simple path from a to b.定理6.3.2 If for any two vertices a and b in a graph G there is a unique simple path from a to b, then G is a tree.We can select a vertex as the root(根) of the tree. Then the tree has become a rooted tree(根树). We can also change a rooted tree to a directed tree, called the rooted directed tree derived from the rooted tree(从一棵根树导出的有向根树).定义6.3.3In a rooted tree T, the level(级) of a vertex v is the lengthof the unique path from the root to v. The height(树高) of a tree is the length of the longest path from the root to a leaf.In a rooted directed tree, if there is a directed edge from u to v, then the vertex u is the parent(父结点) of v and v is the child(子结点) of u. If u is the parent of v and v’, then v and v’are called siblings(兄弟结点). If there is a directed path from vertex u to vertex v, then u is called an ancestor(祖先结点) of v and v is called a descendant(后代结点) of u. If the largest outdegree for any vertex of the tree is m, then the tree is called an m-ary tree(m叉树). In particular, if m=2, then the tree is called a binary tree(二叉树).定理6.3.3 A tree with v vertices has v-1 edges.定理6.3.4 If a connected graph G has e edges and v vertices and v=e+1, then G is a tree.定理6.3.5 A tree with at least one edge has at least two vertices with degree 1.定义6.3.4 A tree T is a spanning tree for a graph G, if T is a subgraph of G, if every vertex in G is a vertex in T.定理6.3.6Every connected graph has a spanning tree.ASSIGNMENTS：PP148-150：2，4，10，12，18，20，22，24，26，28，30，42，44，46Euler Paths and Cycles定义6.4.1Let G(V,E) be a graph. A cycle that includes all of the edges and the vertices of G is called an Euler cycle(欧拉回路). When this occurs, we say that the graph G has an Euler cycle.给定无向图G(V,E)，通过G中的所有边和顶点的回路称为欧拉回路. 存在欧拉回路的图称为欧拉图.例6.4.1哥尼斯堡七桥问题: 这是否是一个欧拉图例6.4.2 一笔画问题.定理6.4.1 A graph with more than one vertex has an Euler cycle if and only if it is connected and every vertex has even degree.至少有两个顶点的无向图G是欧拉图⇔G连通且所有结点的度数都是偶数.证明定理例6.4.3这些图是否是欧拉图解例例6.4.4 下列图形是否可以一笔画成.解例定义6.4.2Let G(V,E) be a graph. A path that includes each of the edges of G exactly once is called an Euler path(欧拉通路). When this occurs, we say that the graph G has an Euler path.给定无向图G(V,E)，通过G中的所有边恰好一次的通路称为欧拉通路. 我们称该图存在欧拉通路.定理6.4.2 A connected graph has an Euler path if and only if exactly two vertices have odd degree.无向连通图G有欧拉通路⇔G恰好只有两个结点的度数是奇数.定义6.4.3Let G(V,E) be a digraph. A directed cycle that includes all of the edges and the vertices of G is called an Euler cycle(欧拉回路). When this occurs, we say that the graph G has an Euler cycle.给定有向图G(V,E)，通过G中的所有边和顶点的有向回路称为欧拉回路. 存在欧拉回路的图称为欧拉图.定理 6.4.3 A digraph has an Euler cycle if and only if it is strongly connected and the indegree of every vertex is equal to its outdegree.有向图G是欧拉图⇔G强连通且所有顶点的出度等于入度.定理6.4.4 A strongly connected digraph has an Euler path if and only if there is a vertex whose indegree is equal to its outdegree+1, and there is a vertex whose indegree is equal to its outdegree-1, and the indegree of all other vertices is equal to its outdegree.强连通的有向图G有欧拉通路⇔G恰有一个顶点其出度比入度多1，另一个顶点其出度比入度少1，且所有其他顶点的出度等于入度.ASSIGNMENTS：PP148-150：2，6，10，12Incidence and Adjacency MatricesHow to represent a graph in a computer定义6.5.1 Let G(V,E) be a graph(digraph). Let B be a matrix whose rows are labeled by the vertices of G and whose columns are labeled by the same vertices in the same order. B ij =1 or 0 whether there is an edge from the ith vertex to the jth vertex. The matrix B is called the adjacency matrix(邻接矩阵) of G.邻接矩阵的一个重要应用是寻图中固定长度的通路. 例6.5.1 求下列图的邻接矩阵.解 例 matrix operations(布尔矩阵运算)A Boolean matrix is an m ×n matrix whose entries are either zero or one.Let A=[a ij ] and B=[b ij ] be m ×n Boolean matrices. We define A ∨B=C=[c ij ], the join of A and B(布尔矩阵的并), by⎩⎨⎧=====000111ij ij ij ij ij b and a if b or a if c and A ∧B=C=[d ij ], the meet of A and B(布尔矩阵的交), by⎩⎨⎧=====000111ij ij ij ij ij b or a if b and a if d 例6.5.2 Let A=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡000011010101 and B=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡011100101011. We have A ∧B=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡000000000001 , A ∨B=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡011111111111Let A=[a ij ] is an m ×p Boolean matrix and B=[b ij ] is a p ×n Boolean matrix.The Boolean product of A and B, denoted by A ⊙B, is the Boolean matrix C=[cij] defined by⎩⎨⎧≤≤===.1,,111otherwise pk k some for b and a ifc kj ik ij例6.5.3 Let A=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡000011010101and B=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡110101100001.Then A ⊙B=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000011101101101定理6.5.1 Let G be a (di)graph with vertices v 1,v 2,v 3,…,v n and adjacency matrix A. There is a k-path from v i to v j for 1≤k ≤n if and only if A ⊙k ij =1. 定理6.5.2 Let G be a (di)graph with vertices v 1,v 2,v 3,…,v n and adjacency matrix A. There is m k-paths from v i to v j for 1≤k ≤n if and only if A k ij =m. 定理6.5.3 Let G be a (di)graph with vertices v 1,v 2,v 3,…,v n and adjacencymatrix A. Let Aˆ=A ∨A ⊙2∨A ⊙3∨…∨A ⊙n . Then A ˆij =1 if and only if there is a path form v i to v j .定理6.5.4 Let G be a (di)graph with vertices v 1,v 2,v 3,…,v n and adjacencymatrix A. Let AˆI =I ∨A ∨A ⊙2∨A ⊙3∨…∨A ⊙n . Then all entries of A ˆI are 1 if and only if G is (strongly) connected.ASSIGNMENTS ：PP148-150：12，16，20，22，24，26定理证明及例题解答定理在图G(V,E)中, 设度数为偶数的顶点组成集合VE，度数为奇数的顶点组成集合VO . 则V=VE∪VO，VE∩VO=φ，所以由欧拉握手定理得∑∈Vvdeg(v)= ∑∈E Vvdeg(v)+ ∑∈OVvdeg(v)=2|E|因为∑∈E Vv deg(v)是一个偶数，故∑∈OVvdeg(v)=2|E|-∑∈E Vvdeg(v)也是偶数. 而VO中的每个顶点的度数都是奇数，故|VO|一定是偶数.例定理设v0e1v1e2v2…vm-1emvm是从v=u到vm=v的长为m的通路.若v0,v1,v2,…,vm-1,vm两两不同，则该通路就是一条基本通路，故结论成立.否则若该通路通过某个顶点vi两次，则我们可从通路中去除它以及它再次出现之间的所有顶点，仍然得到一条从u到v的通路. 若这条新通路是一条基本通路，则结论成立. 否则可对这条新通路进行同样的处理，直到得到一条基本通路为止.例例2K1: v1v2K3v32K43v42K543定理⇒ 设G 有欧拉回路. 则由欧拉回路的定义，它经过G 的所有顶点. 故G 是连通的. 又因为该回路经过G 的所有边恰好一次且每经过一个顶点一次都需要两条边，故G 中所有顶点的度数都为偶数.⇐若G 中所有顶点的度数都是偶数. 因为G 是连通图，故从G 的任一顶点v 出发一定存在G 的一条回路C. 若C 经过G 的所有边，则C 就是一条欧拉回路. 否则在G 中删去C 经过的所有边及由此而产生的孤立顶点得到一个新图G 1，且G 1中每个顶点的度数都是大于0的偶数. 则G 1中一定存在一个u ，C 经过它（否则G 1中的顶点与C 经过的顶点之间无边相连，从而与G 是连通图矛盾）. 类似地从u 出发，G 1中u 所在的连通分支内存在一条经过u 的回路C 1. 显然C 和C 1合并而得仍然是G 的一条回路C 2，但它经过的边比C 多.继续对C重复上述构造过程，最终一定可得到一条G的欧拉回路.2例例例。

求解连通无向简图的所有连通子图的算法及其应用
胡广朋
【期刊名称】《计算机工程》
【年(卷),期】2003(029)013
【摘要】讨论了求解连通无向简图的所有连通子图的算法,并将其应用于化学领域:如何将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的概率.
【总页数】2页(P101-102)
【作者】胡广朋
【作者单位】华东船舶工业学院电子信息学院,镇江,212003
【正文语种】中文
【中图分类】TP36
【相关文献】
1.连通子图算法在GSM网络优化中的应用 [J], 杨明帅;邱杰
2.基于k边连通最小生成子图的网络拓扑管理算法 [J], 孙延维;周谦
3.一种大规模双网络中k-连通Truss子图发现算法 [J], 李源;盛飞;孙晶;赵宇海;王国仁
4.基于图连通支配集的子图匹配优化算法 [J], 孙云浩;韩冰;李冠宇;邢维康;李逢雨
5.基于Tarjan算法的极大点连通子图研究 [J], 付海奎;陈国军;王文波
因版权原因，仅展示原文概要，查看原文内容请购买。