图习题一、1.下列说法错误的是( )。
A.一个图的邻接矩阵表示是唯一的B.一个图的邻接表表示是不唯一的C.一个图的生成树必为该图的极小连通子图D.一个无环有向图的拓扑排序序列必唯一2.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.83.DFS算法的时间复杂度为( )A. O(n)B. O(n3)C. O(n2)D. O(n+e)4.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )A.nB.n+1C.n-1D.n+边数5.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。
A.nB.n+1C.n-1D.n/2 6．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e二、1.图的主要存储结构有两种，分别为：_________和_________。
(1)邻接矩阵(2)邻接表。
2.在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于________。
13．已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为。
a b e f c d g三、1.请画出下面无向图的邻接矩阵和邻接表。
接矩阵为：0 1 1 1 01 0 1 0 11 1 0 1 11 0 1 0 10 1 1 1 0邻接表为：2.求出下图的一棵最小生成树。
3. 已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示0100110010000110110110110⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥(1)画出该图的图形；（2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
．该图的图形为：深度优先遍历序列为：abdce广度优先遍历序列为：abedcab c de4.以邻接表为存储结构，写出连通图的深度优先搜索算法。
include <stdio.h>#include <alloc.h>#define M 10typedef struct node{ int adjvex;struct node *next;}JD;typedef struct tnode{ int vexdata;struct node *firstarc;}TD;void bfs(TD g[],int v,int visited[]){ int qu[M],f=0,r=0;JD *p;printf("%d ",v);visited[v]=1;qu[0]=v;while(f<=r){ v=qu[f++];p=g[v].firstarc;while(p!=NULL){ v=p->adjvex;if(visited[v]==0){ visited[v]=1;printf("%d ",v);qu[++r]=v;}p=p->next;}}void traver(TD g[],int n){ int i;static int visited[M];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)bfs(g,i,visited);}void traver(TD g[],int n){ int i;static int visited[M];for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0)dfs(g,i,visited);}void dfs(TD g[],int v,int visited[]) { JD *w;int i;printf("%d ",v);visited[v]=1;w=g[v].firstarc;while(w!=NULL){ i=w->adjvex;if(visited[i]==0)dfs(g,i,visited);w=w->next;}int loc_vertex(TD g[],int vex,int n){ int i,j;for(i=1;i<=n;i++)if(g[i].vexdata==vex)return(i);return(0);}int crt_linklist(TD g[]){ int n,e,i,j,k,vt,vh,flag;JD *p;printf("Input flag and the number of node,arc:");scanf("%d,%d,%d",&flag,&n,&e);for(i=1;i<=n;i++){ printf("g[%d].vexdata=",i);scanf("%d",&g[i].vexdata);g[i].firstarc=NULL;}for(k=1;k<=e;k++){ printf("Vt,Vh:");scanf("%d,%d",&vt,&vh);i=loc_vertex(g,vt,n);j=loc_vertex(g,vh,n);if(flag){ p=(JD *)malloc(sizeof(JD));p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;}else{ p=(JD *)malloc(sizeof(JD));p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;p=(JD *)malloc(sizeof(JD));p->adjvex=i;p->next=g[j].firstarc;g[j].firstarc=p;}}return(n);}void main(){ int n;TD g[M];n=crt_linklist(g);traver(g,n);}5.已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：#define MaxNum50 //图的最大顶点数#define INFINITY INT_MAX//INT_MAX为最大整数，表示∞typedef struct{char vexs[MaxNum]; //字符类型的顶点表int edges[MaxNum][MaxMum]; //权值为整型的邻接矩阵int n,e; //图中当前的顶点数和边数}MGraph; //邻接矩阵结构描述typedef struct node{int adjvex; //邻接点域int weight; //边的权值struct node*next; //链指针域}EdgeNode; //边表结点结构描述typedef struct{char vertex; //顶点域EdgeNode*firstedge; //边表头指针}VertexNode; //顶点表结点结构描述typedef struct{VertexNode adjlist[MaxNum];//邻接表int n,e;//图中当前的顶点数和边数}ALGraph; //邻接表结构描述下列算法是根据一个带权图的邻接矩阵存储结构G1建立该图的邻接表存储结构G2，请填入合适的内容，使其成为一个完整的算法。
