当前位置： >
&下图是带权的有向图G的邻接表表示法。从节点V1到节点V8的最短路径是（）；
所属学科：
试题类型：客观题
所属知识点：
试题分数：1.0 分
暂未组卷。
用户编号：255187笔记时间： 14:58
笔记内容：本笔记为私密内容。
用户编号：195889笔记时间： 10:12
笔记内容：本笔记为私密内容。
用户编号：367216笔记时间： 07:49
笔记内容：本笔记为私密内容。
&&&&&&&&&&&&&&&希赛网 版权所有 & &&&&湘教QS2-164&&增值电信业务经营许可证湘B2-你的位置： &&
图的存储形式——邻接表
图的存储形式——邻接表
邻接表：邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。每个结点有三个域组成，其中邻接点域指示与顶点vi邻接的点在途中的位置，链域指示下一条边或者弧的结点；数据域存储和边或者弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设置链域指向链表第一个结点之外，还设置有存储顶点vi的名。如下所示：实现：/**************************************
图的存储之邻接表
by Rowandjj
**************************************/
#include&iostream&
#define MAX_VERTEX_NUM 20//最大顶点数
typedef enum{DG,DN,AG,AN}GraphK//有向图、有向网、无向图、无向网
typedef struct _ARCNODE_//表节点(弧)
//邻接点序号
struct _ARCNODE_ *//指向下一条弧
//信息(权值)
typedef struct _VNODE_//头结点
ArcNode *//指向第一条弧
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct _ALGRAPH_//邻接表
AdjL//邻接表
GraphK//图的种类
void (*VisitFunc)(char);
//全局函数指针
bool visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
void Visit(char p)
cout&&p&&" ";
//-----------------操作-------------------------------------
int LocateVex(ALGraph G,char u);//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1
bool CreateGraph(ALGraph* G);//采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)
void DestroyGraph(ALGraph* G);//销毁图G
char GetVex(ALGraph G,int v);//通过序号v得到顶点名
bool PutVex(ALGraph* G,char v,char value);//对v赋新值value
int FirstAdjVex(ALGraph G,char v);//返回顶点v的第一个邻接顶点的序号
int NextAdjVex(ALGraph G,char v,char w);//返回v的(相对于w的)下一个邻接顶点的序号,若w是v的最后一个邻接点,则返回-1
void InsertVex(ALGraph* G,char v);//在图G中增添新顶点v(不增添与顶点相关的弧,留待InsertArc()去做)
bool DeleteVex(ALGraph* G,char v);//删除G中顶点v及其相关的弧
bool InsertArc(ALGraph* G,char v,char w);//在G中增添弧&v,w&,若G是无向的,则还增添对称弧&w,v&
bool DeleteArc(ALGraph* G,char v,char w);//在G中删除弧&v,w&,若G是无向的,则还删除对称弧&w,v&
void DFSTravel(ALGraph* G,void (*Visit)(char));//深度优先
void DFS(ALGraph G,int v);
void BFSTravel(ALGraph G,void (*Visit)(char));//广度优先
void Display(ALGraph G);//打印图
//----------------辅助队列------------------------------------------
#define MAX_QUEUE_SIZE 20
typedef struct _QUEUENODE_
struct _QUEUENODE_ *
typedef struct _QUEUE_
QueueNode *pH
QueueNode *pT
bool InitQueue(Queue *Q);
bool DestroyQueue(Queue *Q);
bool DeQueue(Queue *Q,int* e);
bool EnQueue(Queue *Q, int e);
bool QueueEmpty(Queue Q);
//------------------------------------------------------------------
bool InitQueue(Queue *Q)
Q-&pHead = Q-&pTail = (QueueNode *)malloc(sizeof(QueueNode));
if(!Q-&pHead)
Q-&pHead-&next = NULL;
Q-&size = 0;
bool EnQueue(Queue *Q, int e)
QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode));
node-&data =
node-&next = NULL;
Q-&pTail-&next =
Q-&pTail =
Q-&size++;
bool DeQueue(Queue *Q,int* e)
QueueNode *node = Q-&pHead-&
*e = node-&
Q-&pHead-&next = node-&
if(Q-&pTail == node)
Q-&pTail = Q-&pH
free(node);
Q-&size--;
bool QueueEmpty(Queue Q)
return Q.size == 0;
bool DestroyQueue(Queue *Q)
QueueNode *pTemp = Q-&pHead-&
while(pTemp != NULL)
Q-&pHead-&next = pTemp-&
free(pTemp);
pTemp = Q-&pHead-&
free(Q-&pHead);
Q-&size = 0;
//------------------------------------------------------------------
int LocateVex(ALGraph G,char u)
for(i = 0; i & G. i++)
if(u == G.vertices[i].data)
return -1;
bool CreateGraph(ALGraph* G)
int i,j,k;
char va,//弧尾、弧头
ArcNode *p;//弧
cout&&"请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3): ";
scanf("%d",&(*G).kind);
cout&&"请输入图的顶点数,边数: ";
cout&&"请输入顶点值:"&&
//构造顶点
for(i = 0; i & G-& i++)
cin&&G-&vertices[i].
G-&vertices[i].firstarc = NULL;
if(G-&kind == 1 || G-&kind == 3)//网
cout&&"请顺序输入每条弧(边)的权值、弧尾和弧头:n";
cout&&"请顺序输入每条弧(边)的弧尾和弧头n";
//构造表节点链表
for(k = 0; k & G-& k++)
if(G-&kind == 1 || G-&kind == 3)//网
//定位弧尾弧头的位置
i = LocateVex(*G,va);
j = LocateVex(*G,vb);
p = (ArcNode *)malloc(sizeof(ArcNode));
p-&adjvex =
if(G-&kind == 1 || G-&kind == 3)//网
p-&info =//权值
p-&info = NULL;
p-&nextarc = G-&vertices[i].//插在表头
G-&vertices[i].firstarc =
//如果是无向图或者无向网，还需要增加对称结点
if(G-&kind == 2 || G-&kind == 3)
p = (ArcNode *)malloc(sizeof(ArcNode));
p-&adjvex =
if(G-&kind == 3)//若是无向网，还需要权值
p-&info = NULL;
p-&nextarc = G-&vertices[j].
G-&vertices[j].firstarc =
void Display(ALGraph G)
ArcNode *p;
switch(G.kind)
cout&&"有向图";
cout&&"无向图";
cout&&"有向网";
cout&&"无向网";
cout&&"顶点:"&&
for(i = 0; i & G. i++)
cout&&G.vertices[i].data&&" ";
cout&&"边:"&&
for(i = 0; i & G. i++)
p = G.vertices[i].
if(G.kind == 0 || G.kind == 1)//有向
cout&&G.vertices[i].data&&" "&&G.vertices[p-&adjvex].
if(G.kind == 1)//有向网
cout&&" "&&p-&
}else//无向
if(i & p-&adjvex)//不重复打印
cout&&G.vertices[i].data&&" "&&G.vertices[p-&adjvex].
if(G.kind == 3)//无向网
cout&&" "&&p-&
void DestroyGraph(ALGraph* G)
ArcNode *p,*q;
for(i = 0; i & G-& i++)
p = G-&vertices[i].
G-&arcnum = 0;
G-&vexnum = 0;
char GetVex(ALGraph G,int v)
if(v&=G.vexnum || v&0)
return G.vertices[v].
bool PutVex(ALGraph* G,char v,char value)
int i = LocateVex(*G,v);
if(i == -1)
G-&vertices[i].data =
int FirstAdjVex(ALGraph G,char v)
int i = LocateVex(G,v);
return -1;
ArcNode *arcNode = G.vertices[i].
if(arcNode == NULL)
return -1;
return arcNode-&
int NextAdjVex(ALGraph G,char v,char w)
i = LocateVex(G,v);
j = LocateVex(G,w);
ArcNode *p = G.vertices[i].
while(p && p-&adjvex != j)
if(!p || !p-&nextarc)//没找到w或w是最后一个邻接点
return -1;
return p-&nextarc-&
void InsertVex(ALGraph* G,char v)
G-&vertices[G-&vexnum].data =
G-&vertices[G-&vexnum].firstarc = NULL;
G-&vexnum++;
bool DeleteVex(ALGraph* G,char v)
ArcNode *p,*q;
//1.删除邻接表中顶点为v的那一行所有数据，更改弧总数,顶点总数
i = LocateVex(*G,v);
if(i & 0 || i &= G-&vexnum)//不合法的位置
p = G-&vertices[i].
while(p)//依次删除弧
G-&arcnum--;
G-&vexnum--;
//2.更改顶点v之后的顶点在数组中的位置（前移一位）
for(j = j & G-& j++)
G-&vertices[j] = G-&vertices[j+1];
//3.遍历剩下的邻接表,找到包含顶点v的弧或者边，删除之。另外需要注意，对遍历的每个弧/边，视情况更新序号
for(j = 0; j & G-& j++)
p = G-&vertices[j].//p指向遍历的顶点的第一条弧或者边
if(p-&adjvex == i)//如果找到指向已删除顶点的弧或者边
if(p == G-&vertices[j].firstarc)//如果待删除的结点是第一个结点
G-&vertices[j].firstarc = p-&
p = G-&vertices[j].
if(G-&kind &= 1)//如果是有向的，则还需更改弧数
G-&arcnum--;
}else//不是第一个结点
q-&nextarc = p-&
if(G-&kind &= 1)//如果是有向的，则还需更改弧数
G-&arcnum--;
}else//如果当前弧并不是要找的弧，那么继续向后遍历
if(p-&adjvex & i)//(很关键)更新序号
p-&adjvex--;
p = p-&//指向下一条弧
bool InsertArc(ALGraph* G,char v,char w)
ArcNode *arcN
//1.得到v、w的在邻接表中的序号
i = LocateVex(*G,v);
j = LocateVex(*G,w);
if(i&0 || j&0)
G-&arcnum++;
if(G-&kind == 1 || G-&kind == 3)
cout&&"输入权值:";
cin&&//输入权值
//2.生成一个弧结点，插入到顶点v的第一个邻接点的位置（如果是网的话，需要用户输入权值）
arcNode = (ArcNode*)malloc(sizeof(ArcNode));
arcNode-&adjvex =
if(G-&kind == 1 || G-&kind == 3)
arcNode-&info =
arcNode-&info = NULL;
arcNode-&nextarc = G-&vertices[i].
G-&vertices[i].firstarc = arcN
//3.如果是无向的，那么还需生成对称节点，并插到合适位置
if(G-&kind &= 2)
arcNode = (ArcNode *)malloc(sizeof(ArcNode));
arcNode-&adjvex =
if(G-&kind == 3)//无向网
arcNode-&info =
arcNode-&info = NULL;
arcNode-&nextarc = G-&vertices[j].
G-&vertices[j].firstarc = arcN
bool DeleteArc(ALGraph* G,char v,char w)
ArcNode *p,*q;
//1.得到v、w的在邻接表中的序号
i = LocateVex(*G,v);
j = LocateVex(*G,w);
if(i & 0 || j & 0)
//2.删除v-w
p = G-&vertices[i].
while(p && p-&adjvex!=j)
if(p && p-&adjvex==j)//找到弧&v-w&
if(p == G-&vertices[i].firstarc)//p指的是第一条弧
G-&vertices[i].firstarc = p-&
q-&nextarc = p-&
G-&arcnum--;
//3.若是无向，则还删除w-v
if(G-&kind &= 2)
p = G-&vertices[j].
while(p && p-&adjvex!=i)
if(p && p-&adjvex==i)//找到弧&w-v&
if(p == G-&vertices[j].firstarc)//p指的是第一条弧
G-&vertices[j].firstarc = p-&
q-&nextarc = p-&
void DFSTravel(ALGraph* G,void (*Visit)(char))
VisitFunc = V
for(i = 0; i & G-& i++)
visited[i] =
for(i = 0; i & G-& i++)
if(!visited[i])
DFS(*G,i);
void DFS(ALGraph G,int v)
char v1,w1;
v1 = GetVex(G,v);
visited[v] =
VisitFunc(G.vertices[v].data);
for(i = FirstAdjVex(G,v1);i&=0; i = NextAdjVex(G,v1,w1 = GetVex(G,i)))
if(!visited[i])
void BFSTravel(ALGraph G,void (*Visit)(char))
InitQueue(&q);
char w1,u1;
int i,u,w;
for(i = 0; i & G. i++)
visited[i] =
for(i = 0; i & G. i++)
if(!visited[i])
visited[i] =
Visit(G.vertices[i].data);
EnQueue(&q,i);
while(!QueueEmpty(q))
DeQueue(&q,&u);
u1 = GetVex(G,u);
for(w = FirstAdjVex(G,u1);w&=0;w = NextAdjVex(G,u1,w1=GetVex(G,w)))
if(!visited[w])
visited[w] =
Visit(G.vertices[w].data);
EnQueue(&q,w);
DestroyQueue(&q);
int main()
CreateGraph(&graph);
Display(graph);
cout&&"深度优先:"&&
DFSTravel(&graph,Visit);
cout&&"广度优先:"&&
BFSTravel(graph,Visit);
DestroyGraph(&graph);
}测试：考虑以下有向图：
&&作者：RowandJJ &&
最新热门tag（急）试写出程序判别以邻接表方式存储的有向图G中是否存在由顶点vi到顶点vj的路径(i≠j).算法如下：int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i_百度作业帮
（急）试写出程序判别以邻接表方式存储的有向图G中是否存在由顶点vi到顶点vj的路径(i≠j).算法如下：int visited[MAXSIZE]; //指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j) return 1; //i就是jelse{visited[i]=1;for(p=G.vertices[i].p;p=p->nextarc){k=p->if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS void find(int A[][],int m,int n)//求矩阵A中的马鞍点{int i,j,min,for(i=0; } else{ r->next=q; r=r-> q=q-> } } r->next=(p!=NULL?p:q);free(B);}
tyrt6uyiuyjkhjkyuujhkuftywemcnwqwnhecvsyhgynsvsehvysdnfxdnvhbmndhnfdhuuvbvhdfbvhjbvn dfjbgvhadlfbgkjazsnzjd1fn4ghmj68d1fm4f2h4gj4m981xd4m194g9h16gv54h56g4mh141jk87gj1,8+05x684e684mnszweuh61li81,7u8j9fg741n987es9gvw提问回答都赚钱
> 问题详情
己知某带权图G的邻接表如下所示，其中表结点的结构为：则图G是______。A．无向图B．完全图C．有向图D．
悬赏：0&&答案豆&&&&提问人：匿名网友&&&&提问收益：0.00答案豆&&&&&&
己知某带权图G的邻接表如下所示，其中表结点的结构为：则图G是______。A．无向图B．完全图C．有向图D．强连通图
发布时间：&&截止时间：
网友回答&(共0条)
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&10.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&4.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&6.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&3.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&5.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
回答悬赏问题预计能赚取&1.00元收益
为你请到的专家
&&&&采纳率：76%&&&
&&采纳率：97%&&&
&&采纳率：88%&&&
&&&&采纳率：25%&&&
&&采纳率：90%&&&
[] [] [] [] [] [] [] [] [] [] [] []
请先输入下方的验证码查看最佳答案第七章　图练习题（一）
1、有n个顶点的无向完全图具有(&&&&
A、n(n+1)/2&&&&&&
&B、n-1&&&&&&
C、n&&&&&&&&&&
2、有向图中一个顶点i的出度等于其邻接矩阵中第i列的非零元素的个数(&
3、有向图中一个顶点i的入度等于其邻接矩阵中第i列的非零元素的个数(&
4、一个具有n个顶点的连通有向图至多有_________条弧.
5、一个具有n个顶点的连通有向图至少有________条弧.
6、已知图G如下:
　求(1) 图G的邻接矩阵
　(2) 图G的最小生成树
7、网是带_&&&&
8、连通图G的生成树是G的极小连通子图(& )
9、连通网络的最小生成树是唯一的(&&&
10、连通图是有向图(&&
11、连通图的邻接矩阵是对称的,有向图的邻接矩阵是不对称的(&
12、有n个顶点,n-1条边的图一定是生成树(& )
13、已知图G的邻接矩阵为
问(1)该图是有向图还是无向图?为什么?
(2)各结点的度是多少?
14、已知某有向图的邻接表如下:
求出每个顶点的入度和出度.
15、图的常用存储结构有________和________.
16、图的遍历方法一般有________和_________两种.
17、何为子图?
18、何为连通图?
19、树是一种特殊形式的图(& )
20、　从邻接矩阵│0 1
0│可以看出,该图共有____个顶点,
&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&
如果是有向图,该图共有___条弧;如果是无向图则共有____条边.
21、有向图中,所有的顶点的入度之和与出度之和的关系_________
22、无向图G是连通的无回路图,有且仅有_______条边.
23、何为网络?
24、已知如下图所示的有向图,请给出该图的
(1) 每个顶点的入度/出度
25、试利用dijkstra算法求右图中从顶点a到其它各顶点间的最短路径长度,写出执行算法过程中各步的状态.
26、试给出以邻接矩阵表示无向图的深度优先搜索算法
27、试给出此邻接表表示有向图的广度优先搜索算法
28、设有无向图G,从顶点V1出发,对它进行深度优先遍历得到的顶点序列是______;而进行广度优先遍历得到的顶点序列是_____.
一个图中，所有顶点的度数之和等于图的边数的(&&&&&
A、1/2&&&&&&&&&&&
B、 1&&&&&&&&&&&&
C、 2&&&&&&&&&&&&
30、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的(&&&&
&&&&&&&&&&B、
1&&&&&&&&&&&&
C、 2&&&&&&&&&&&&
31、有8个结点的无向图最多有(&&&&&
A、14&&&&&&&&&&&
B、 28&&&&&&&&&&&&
56&&&&&&&&&&&&
32、有8个结点的无向连通图最少有(&&&&&
A、5&&&&&&&&&&&
B、 6&&&&&&&&&&&&
C、 7&&&&&&&&&&&&
33、有8个结点的有向完全图有(&&&&&
A、14&&&&&&&&&&&
B、 28&&&&&&&&&&&&
C、 56&&&&&&&&&&&&
34、用邻接表表示图进行广度优先遍历时，通常是采用(&&&&&&&
)来实现算法的。
A、栈&&&&&&&&&&&
B、队列&&&&&&&&&&&
C、 树&&&&&&&&&&&&
35、用邻接表表示图进行深度优先遍历时，通常是采用(&&&&&&&&
)来实现算法的。
A、栈&&&&&&&&&&&
B、队列&&&&&&&&&&&
C、 树&&&&&&&&&&&&
36、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是(&&&&&
37、已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是(&&&&&
38、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是(&&&&&
39、深度优先遍历类似于二叉树的(&&&&&
A、先序遍历&&&&&
B、中序遍历&&&&
C、 后序遍历&&&
D、 层次遍历
40、广度优先遍历类似于二叉树的(&&&&&
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。