e以邻接表存储
⑴ 为什么当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为O(n+e)
n是因为要对每一个节点都做dfs,e是因为dfs只要把所有的边都走到了,就跳出了.
⑵ 如题，以邻接表存储图，并对图进行深度优先遍历
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXVEX 100
typedef char VertexType[3];/*定义VertexType为char数组类型*/
typedef struct vertex
{int adjvex; /*顶点编号*/VertexType data; /*顶点的信息*/ } VType;/*顶点类型*/
typedef struct graph
{int n,e;/*n为实际顶点数,e为实际边数*/
VType vexs[MAXVEX];/*顶点集合*/
int edges[MAXVEX][MAXVEX];/*边的集合*/
} AdjMatix;/*图的邻接矩阵类型*/
typedef struct edgenode
{int adjvex; /*邻接点序号*/ int value;/*边的权值*/struct edgenode *next;/*下一顶点*/
} ArcNode;/*每个顶点建立的单链表中结点的类型*/
typedef struct vexnode
{VertexType data; /*结点信息*/ArcNode *firstarc;/*指向第一条边结点*/
} VHeadNode;/*单链表的头结点类型*/
typedef struct
{int n,e;/*n为实际顶点数,e为实际边数*/
VHeadNode adjlist[MAXVEX];/*单链表头结点数组*/
} AdjList; /*图的邻接表类型*/
void DispAdjList(AdjList *G)
{int i;
ArcNode *p;
printf("图的邻接表表示如下:\n");
for (i=0;i<G->n;i++)
{printf(" [%d,%3s]=>",i,G->adjlist[i].data);
p=G->adjlist[i].firstarc;
while (p!=NULL)
{printf("(%d,%d)->",p->adjvex,p->value);p=p->next;}printf("∧\n");
}
}
void MatToList(AdjMatix g,AdjList *&G) /*将邻接矩阵g转换成邻接表G*/
{int i,j;ArcNode *p;
G=(AdjList *)malloc(sizeof(AdjList));
for (i=0;i<g.n;i++)/*给邻接表中所有头结点的指针域置初值*/
{G->adjlist[i].firstarc=NULL;strcpy(G->adjlist[i].data,g.vexs[i].data);}
for (i=0;i<g.n;i++)/*检查邻接矩阵中每个元素*/
for (j=g.n-1;j>=0;j--)
if (g.edges[i][j]!=0)/*邻接矩阵的当前元素不为0*/
{p=(ArcNode *)malloc(sizeof(ArcNode));/*创建一个结点*p*/
p->value=g.edges[i][j];p->adjvex=j;
p->next=G->adjlist[i].firstarc; G->adjlist[i].firstarc=p;}
G->n=g.n;G->e=g.e;
}
int visited[MAXVEX];
void DFS(AdjList *g,int vi)/*对邻接表G从顶点vi开始进行深度优先遍历*/
{ArcNode *p;printf("%d ",vi);/*访问vi顶点*/ visited[vi]=1;/*置已访问标识*/
p=g->adjlist[vi].firstarc;/*找vi的第一个邻接点*/
while (p!=NULL)/*找vi的所有邻接点*/
{if (visited[p->adjvex]==0)DFS(g,p->adjvex);p=p->next; }
}
void main()
{int i,j,k,a[9][9];AdjMatix g;AdjList *G;
char *vname[MAXVEX]={"a","b","c","d","e","f","g","h","i"};
printf("输入定点数(<10)，边数");
scanf("%d,%d",&i,&k);
g.n=i;g.e=2*k;
for (i=0;i<g.n;i++)strcpy(g.vexs[i].data,vname[i]);
for (i=0;i<g.n;i++)
for (j=0;j<g.e;j++)g.edges[i][j]=0; /*a[i][j];*/
for(k=0;k<g.e/2;k++)
{printf("请输入第%d条边的起点和终点序号(逗点分隔)",k);scanf("%d,%d",&i,&j);
g.edges[i][j]=g.edges[j][i]=1;}
MatToList(g,G);/*生成邻接表*/ DispAdjList(G);/*输出邻接表*/
for (i=0;i<g.n;i++)visited[i]=0; /*顶点标识置初值*/
printf("从顶点0的深度优先遍历序列:\n");printf(" 递归算法:");DFS(G,0);printf("\n");
}
⑶ 设G=(V,E)以邻接表储存,如图所示,试画出从顶点1出发所得到的深度优先生成树
深度优先生成树
1-2-3-4-5
广度优先生成树
1
/|\
/ | \
2 3 4
|
5
⑷ 实验题目： 以邻接表储存图并对图进行遍历（写出流程图及程序） 大神们 帮帮忙吧！！！
#include "stdlib.h"
#include "stdio.h"
#define N 6
#define e 4
typedef int vextype;
typedef struct node
{
int adjvex; /*邻接点域*/
struct node *next; /*链域*/
}edgenode; /*边表结点*/
typedef struct
{
vextype vertex; /*顶点信息*/
edgenode *link; /*边表头指针*/
}vexnode; /*顶点表结点*/
void CREATADJLIST(vexnode *ga)
{
int i,j,k;
edgenode *s;
for (i=0;i<N;i++) //输入顶点信息；
{
ga[i].vertex=i+1;
ga[i].link=NULL; //边表头指针初始化；
}
printf("please enter the (i,j):");
for (k=0;k<e;k++) //建立边表；
{
scanf("%d%d",&i,&j); //读入边（VI，VJ）的顶点对序号；
s=(edgenode*)malloc(sizeof(edgenode)); //生成邻接点序号为J的表结点S；
s->adjvex=j;
s->next=ga[i-1].link;
ga[i-1].link=s; //将S插入顶点VI的边表头部；
s=(edgenode*)malloc(sizeof(edgenode)); ////生成邻接点序号为I的表结点S；
s->adjvex=i;
s->next=ga[j-1].link;
ga[j-1].link=s; //将S插入顶点VJ的边表头部；
}
}
bool visited[N];
void DFSL(int i,vexnode *ga) //从VI出发深度优先搜索图ga，；
{
edgenode *p;
printf("node:%d\n",ga[i-1].vertex);
visited[i-1]=true;
p=ga[i-1].link;
while (p!=NULL)
{
if (visited[p->adjvex-1]!=true)
{
DFSL(p->adjvex,ga);
}
p=p->next;
}
}
int head;
int tail;
int body[100];
void makeq()
{
head = 0;
tail = 0;
}
void inq(int a)
{
body[tail] = a;
tail++;
}
int outq()
{
int a;
a = body[head];
head++;
return a;
}
void BFSL(int i,vexnode *ga)
{
makeq();
int a;
for (a = 0; a < N; a++)
{
visited[a] = false;
}
edgenode *p;
printf("node:%d\n",ga[i-1].vertex);
visited[i-1]=true;
inq(i);
while (head != tail)
{
a = outq();
p=ga[a-1].link;
while (p!=NULL)
{
if (visited[p->adjvex-1]!=true)
{
printf("node:%d\n",ga[p->adjvex-1].vertex);
visited[p->adjvex-1] = true;
inq(p->adjvex);
}
p=p->next;
}
}
}
int main()
{
vexnode ga[N];
CREATADJLIST(ga);
int i;
printf("please enter the node which is start(1-6):");
scanf("%d",&i);
printf("DFSL:\n");
DFSL(i,ga);
printf("BFSL:\n");
BFSL(i,ga);
return 0;
}
⑸ 如何用邻接表存储图结构
我看不太懂这个程序，不过我有些过图的邻接表表示，看对你有没有帮助吧。
#include <iostream>
#include <fstream>
#include <vector>
typedef int QElemTyep;
#include "queue.h"
using namespace std;
typedef int Status;
#define MAX_VERTEX_NUM 30 //图的最大顶点数
enum BOOL {False,True};
BOOL visited[MAX_VERTEX_NUM]; //全局变量--访问标志数组
typedef struct ArcNode{
//弧结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
InfoType *info; //保存边的信息，可以简单的改为 int w;
}ArcNode;
typedef struct VNode{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
class Graph{
public: AdjList vertices; //记录顶点信息，指向第一条依附该顶点的弧的指针
int vexnum,arcnum; //图的当前顶点和弧数
int GraphKind; //图的种类，0---无向图，1---有向图
Graph(int vexnum,int arcnum,int kind)
{
this->vexnum=vexnum;
this->arcnum=arcnum;
this->GraphKind=kind;
}
};
void CreateGraph(Graph &G,VertexType *V,ArcType *VR){
//构造邻接表结构的图G
int i;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) //初始化指针数组
{
G.vertices[i].data=V[i];
G.vertices[i].firstarc=NULL;
}
for(i=1;i<=G.arcnum;i++)
{
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个弧结点
s->nextarc=G.vertices[VR[i].start].firstarc; //插入到邻接表中
s->adjvex=VR[i].end;
G.vertices[VR[i].start].firstarc=s;
if(G.GraphKind==0) {
//若是无向图，再插入到终点的弧链中
s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.vertices[VR[i].end].firstarc;
s->adjvex=VR[i].start;
G.vertices[VR[i].end].firstarc=s;
}
}
}
⑹ 数据结构 设G=(V,E)以邻接表存储,试写出深度优先和广度优先序列.
深度优先序列：1-2-3-4-5
广度优先序列：1-2-3-4-5
⑺ 邻接表存储时，空间复杂度O( n+e)，还是O(n)
O(n+e)，取n次最小权，每次取完会进行n次更新。如果能达到o（n+e），就不需要O(n)。
在有向图中，描述每个点向别的节点连的边（点a->点b这种情况）。在无向图中，描述每个点所有的边。与邻接表相对应的存图方式叫做边集表，这种方法用一个容器存储所有的边。
对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。
(7)e以邻接表存储扩展阅读：
n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。（因为有向图是单向的）
在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。
n个顶点e条边的有向图，它的逆邻接表表示中有n个顶点表结点和e个边表结点。
⑻ 采用邻接表存储，拓扑排序算法的时间复杂度为多少
要看使用什么样的拓扑排序，最好的方法是输出DFS的逆序，这样的算法复杂度是O(V+L),V是顶点个数，L是边个数。