⑴ 《数据结构》以邻接表位存储，写出连通图的深度优先搜索法。
深度优先搜索法遍历图
template <class T1, class T2>
void Link_GP<T1,T2> :: bfs_GP()
{ int *mark, k;
sq_Queue<int> q(nn); //建立循环队列
node<T1> *p;
mark=new int[nn]; //申请标志数组
for (k=0; k<nn; k++) mark[k]=0;
for (k=0; k<nn; k++) //对每个图结点横向优先搜索
{ if ( mark[k] == 0) //当前结点未查访过
{ mark[k] = 1; //置已查访标志
cout <<gp->data <<" "; //输出当前结点值
q.ins_sq_Queue(k); //当前结点编号入队
while (q.flag_sq_Queue()) //队列不空
{ k=q.del_sq_Queue();
//从队列中退出一个结点作为当前结点
p = (gp+k)->link; //置编号k的结点单链表指针
while (p!=NULL) //还有后件
{ k = p->num-1;
if (mark[k]==0) //该结点未查访过
{ cout <<(gp+k)->data <<" "; //输出该结点值
mark[k]=1; //置已访问标志
q.ins_sq_Queue(k); //该结点编号入队
}
p=p->next; //下一个后件
}
}
}
}
cout <<endl; delete mark;
}
⑵ 数据结构实验——连通图的实现（C语言）
这个你应该去找你的师兄师姐们，或者上网搜，在这里问，谁帮你整这么麻烦的事情，而且你应该自己动手实现，抄这种行为是很不好的
⑶ 以邻接多重表为存储结构，实现连通无向图的深度优先遍历和广度优先遍历。
没有现成的，自己看看套用一下吧。
邻接多重表
/*********************************************************
Title : graph-multiadjacentlist.c
Author :
Time :
Purpose : 图的多重邻接链表表示法
Thread :
Comment :
Usage :
**********************************************************/
#include "stdio.h"
#include "stdlib.h"
/*=====================变量声明--variable declaration=================*/
struct edge /* 图形边线结构声明 */
{
int vertex1; /* 顶点1资料 */
int vertex2; /* 顶点2资料 */
struct edge *edge1; /* 顶点1下一边线 */
struct edge *edge2; /* 顶点2下一边线 */
};
typedef struct edge *nextedge; /* 图形的边线新型态 */
struct node /* 图形顶点结构宣告 */
{
int vertex; /* 顶点资料 */
struct edge *edge; /* 顶点下一边线 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[6]; /* 图形顶点结构数组 */
/*=====================函数声明--function declaration=================*/
void creategraph(int *node,int num);
/*====================函数实现--function implementation================*/
/* --------------------------------------------------
Function : void creategraph()
Purpose :
Arguments :
Returns :
------------------------------------------------- */
void creategraph(int *node,int num)
{
nextedge newnode; /* 新边线指标 */
nextedge previous; /* 前一边线指标 */
nextedge ptr; /* 目前边线指标 */
int from; /* 边线的起点 */
int to; /* 边线的终点 */
int i;
for ( i = 0; i < num; i++ ) { /* 读取边线的回路 */
from = node[i*2]; /* 边线的起点 */
to = node[i*2+1]; /* 边线的终点 */
/* 建立新边线记忆体 */
newnode = ( nextedge ) malloc(sizeof(struct edge));
newnode->vertex1 = from; /* 建立顶点内容 */
newnode->vertex2 = to; /* 建立顶点内容 */
newnode->edge1 = NULL; /* 设定指标初值 */
newnode->edge2 = NULL; /* 设定指标初值 */
previous = NULL; /* 前一边线指标 */
ptr = head[from].edge; /* 目前边线指标 */
while ( ptr != NULL ) { /* 遍历到最后边线 */
previous = ptr; /* 保留前一边线 */
if ( ptr->vertex1 == from ) /* 决定走的边线 */
ptr = ptr->edge1; /* 下一边线 */
else
ptr = ptr->edge2; /* 下一边线 */
}
if ( previous == NULL )
head[from].edge = newnode; /* 设定顶点边线指标 */
else
if ( previous->vertex1 == from ) /* 决定走的边线 */
previous->edge1 = newnode; /* 连接下一边线 */
else
previous->edge2 = newnode; /* 连接下一边线 */
previous = NULL; /* 前一边线指标 */
ptr = head[to].edge; /* 目前边线指标 */
while ( ptr != NULL ) { /* 遍历到最后边线 */
previous = ptr; /* 保留前一边线 */
if ( ptr->vertex1 == to ) /* 决定走的边线 */
ptr = ptr->edge1; /* 下一边线 */
else
ptr = ptr->edge2; /* 下一边线 */
}
if ( previous == NULL )
head[to].edge = newnode; /* 设定顶点边线指标 */
else
if ( previous->vertex1 == to ) /* 决定走的边线 */
previous->edge1 = newnode; /* 连接下一边线 */
else
previous->edge2 = newnode; /* 连接下一边线 */
}
}
/*======================主函数--main function--建立图形后,将边线打印出========================*/
int main(int argc, char* argv[])
{
nextedge ptr;
int node[6][2] = { {1, 2}, /* 边线数组 */
{1, 3},
{2, 3},
{2, 4},
{3, 5},
{4, 5}, };
int i;
for ( i = 1; i <= 5; i++ ) {
head.vertex = i; /* 设定顶点值 */
head.edge = NULL; /* 清除图形指标 */
}
creategraph(node,6); /* 建立图形 */
printf("图形的多重邻接链表内容:\n");
for ( i = 1; i <= 5; i++ ) {
printf("顶点%d =>",head.vertex); /* 顶点值 */
ptr = head.edge;
/* 边线位置 */
while ( ptr != NULL ) { /* 遍历至链表尾 */
/* 印出边线 */
printf("(%d,%d)",ptr->vertex1,ptr->vertex2);
/* 决定下一边线指标 */
if ( head.vertex == ptr->vertex1 )
ptr = ptr->edge1; /* 下一个边线 */
else
ptr = ptr->edge2; /* 下一个边线 */
}
printf("\n"); /* 换行 */
}
return 1;
}
// 图的遍历 *
// 生成，深度、广度优先遍历 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 20 //图的最大顶点数
#define MAXQSIZE 30 //队列的最大容量
enum BOOL {False,True};
typedef struct ArcNode
{int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode; //弧结点
typedef struct
{ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针
int vexnum,arcnum; //图的当前顶点和弧数
int GraphKind; //图的种类，0---无向图，1---有向图
}Graph;
typedef struct //队列结构
{int elem[MAXQSIZE]; //数据域
int front; //队头指针
int rear; //队尾指针
}SqQueue;
BOOL visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组
void CreateGraph(Graph &); //生成图的邻接表
void DFSTraverse(Graph); //深度优先搜索遍历图
void DFS(Graph,int);
void BFSTraverse(Graph); //广度优先搜索遍历图
void Initial(SqQueue &); //初始化一个队列
BOOL QueueEmpty(SqQueue); //判断队列是否空
BOOL EnQueue(SqQueue &,int); //将一个元素入队列
BOOL DeQueue(SqQueue &,int &); //将一个元素出队列
int FirstAdjVex(Graph,int); //求图中某一顶点的第一个邻接顶点
int NextAdjVex(Graph,int,int); //求某一顶点的下一个邻接顶点
void main()
{Graph G; //采用邻接表结构的图
char j='y';
//------------------程序解说----------------------------
printf("本程序将演示生成一个图，并对它进行遍历.
");
printf("首先输入要生成的图的种类.
");
printf("0---无向图, 1--有向图
");
printf("之后输入图的顶点数和弧数。
格式：顶点数，弧数；例如:4,3
");
printf("接着输入各边(弧尾，弧头).
例如:
1,2
1,3
2,4
");
printf("程序会生成一个图，并对它进行深度和广度遍历.
");
printf("深度遍历:1->2->4->3
广度遍历:1->2->3->4
");
//------------------------------------------------------
while(j!='N'&&j!='n')
{printf("请输入要生成的图的种类(0/1):");
scanf("%d",&G.GraphKind); //输入图的种类
printf("请输入顶点数和弧数：");
scanf("%d,%d",&G.vexnum,&G.arcnum); //输入图的顶点数和弧数
CreateGraph(G); //生成邻接表结构的图
DFSTraverse(G); //深度优先搜索遍历图
BFSTraverse(G); //广度优先搜索遍历图
printf("图遍历完毕，继续进行吗?(Y/N)");
scanf(" %c",&j);
}
}
void CreateGraph(Graph &G)
{//构造邻接表结构的图G
int i;
int start,end;
ArcNode *s;
for(i=1;i<=G.vexnum;i++) G.AdjList=NULL; //初始化指针数组
for(i=1;i<=G.arcnum;i++)
{scanf("%d,%d",&start,&end); //输入弧的起点和终点
s=(ArcNode *)malloc(sizeof(ArcNode)); //生成一个弧结点
s->nextarc=G.AdjList[start]; //插入到邻接表中
s->adjvex=end;
G.AdjList[start]=s;
if(G.GraphKind==0) //若是无向图，再插入到终点的弧链中
{s=(ArcNode *)malloc(sizeof(ArcNode));
s->nextarc=G.AdjList[end];
s->adjvex=start;
G.AdjList[end]=s;
}
}
}
void DFSTraverse(Graph G)
{//深度优先遍历图G
int i;
printf("DFSTraverse:");
for(i=1;i<=G.vexnum;i++) visited=False; //访问标志数组初始化
for(i=1;i<=G.vexnum;i++)
if(!visited) DFS(G,i); //对尚未访问的顶点调用DFS
printf("\b\b
");
}
void DFS(Graph G,int i)
{//从第i个顶点出发递归地深度遍历图G
int w;
visited=True; //访问第i个顶点
printf("%d->",i);
for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w))
if(!visited[w]) DFS(G,w); //对尚未访问的邻接顶点w调用DFS
}
void BFSTraverse(Graph G)
{//按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited
int i,u,w;
SqQueue Q;
printf("BFSTreverse:");
for(i=1;i<= G.vexnum;i++) visited=False; //访问标志数组初始化
Initial(Q); //初始化队列
for(i=1;i<=G.vexnum;i++)
if(!visited)
{visited=True; //访问顶点i
printf("%d->",i);
EnQueue(Q,i); //将序号i入队列
while(!QueueEmpty(Q)) //若队列不空，继续
{DeQueue(Q,u); //将队头元素出队列并置为u
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if(!visited[w]) //对u的尚未访问的邻接顶点w进行访问并入队列
{visited[w]=True;
printf("%d->",w);
EnQueue(Q,w);
}
}
}
printf("\b\b
");
}
int FirstAdjVex(Graph G,int v)
{//在图G中寻找第v个顶点的第一个邻接顶点
if(!G.AdjList[v]) return 0;
else return(G.AdjList[v]->adjvex);
}
int NextAdjVex(Graph G,int v,int u)
{//在图G中寻找第v个顶点的相对于u的下一个邻接顶点
ArcNode *p;
p=G.AdjList[v];
while(p->adjvex!=u) p=p->nextarc; //在顶点v的弧链中找到顶点u
if(p->nextarc==NULL) return 0; //若已是最后一个顶点，返回0
else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号
}
void Initial(SqQueue &Q)
{//队列初始化
Q.front=Q.rear=0;
}
BOOL QueueEmpty(SqQueue Q)
{//判断队列是否已空，若空返回True,否则返回False
if(Q.front==Q.rear) return True;
else return False;
}
BOOL EnQueue(SqQueue &Q,int ch)
{//入队列，成功返回True，失败返回False
if((Q.rear+1)%MAXQSIZE==Q.front) return False;
Q.elem[Q.rear]=ch;
Q.rear=(Q.rear+1)%MAXQSIZE;
return True;
}
BOOL DeQueue(SqQueue &Q,int &ch)
{//出队列,成功返回True，并用ch返回该元素值，失败返回False
if(Q.front==Q.rear) return False;
ch=Q.elem[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
return True; //成功出队列，返回True
}
转载
⑷ 数据结构：图的邻接表实现
有的时候我并不能一口吃一个胖子，不是吗？编程也是一样，如果都让别人来帮助你，那么自己永远也难有提高的，其实要想编写好你提出图的问题首先要有一些基础才可以的。只有在基本概念非常熟悉的情况之下，我们才可能自己编写出真正属于自己的程序，而且会让我们的编程变得从容自如。
首先，我们要知道什么是邻接表，说简单点，邻接表是一个特殊数组，数组中的每个非空元素代表一个图的节点，且存放的是一个链表（如果不清楚什么是链表的话，那就看看清华大学严蔚敏版的《数据结构》）的头指针，这个链表是所有与此节点联通的节点的集合。如果还不太清楚的话看看下面的图片
左边的数组，就是所有定点列表啦，右边有6个链表
比如A节点与B，E节点相连，所以第一个链表里分别存放B，E节点（注意这里的B,E节点在邻接表中不直接用字母标出，而是使用B,E节点所在数组的下标表示，故分别为1节点和4节点，这样便于编程）
好啦，如果你明白了什么是邻接表，那么已经成功一半啦，对于图的操作都要修改这个抽象的邻接表。
其次，我们要懂得链表这样的数据结构的操作以及以上这些对于图的操作基本概念（可以看看严蔚敏版的《数据结构》），如果要讲清楚这些可能要讲到第二天的天亮。在这里请原谅我不能够一一讲解，不过你要求的这些基本程序在严蔚敏的那本书中都有源码的（建议不要看别人的源码，看如别人的会很痛苦，自己写反而很轻松的）。如果对链表的操作（主要是指针）还不熟悉，那么请先好好地学习一下链表的编程吧，链表比邻接表要简单得多，可以先简单后复杂，你会在编程的过程之中得到无穷的乐趣。
希望我的这点经验能够对你有些许帮助。
⑸ 无向连通图的邻接表的存储
最近在看这部分，可惜没记住无向连通图邻接表的定义。
你的程序，我看看出了1点问题：
1、typedef struct ArcNode{ //边（表结点）
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条弧的指针
int info; //该弧相关信息的指针
};
缺东西呢，typedef 是要给 struct ArcNode 起个别名，但是你并没有做。
可改成 typedef struct ArcNode {.....} ArcNode, *pArcNode; 之类的。或者把 typedef 去了
===============================================
void buildhead(ALGraph &G) //创建一个头结点表
{
int i=65;
while(i < G.vernum+65)
{
G.vertices[i].data = (char)i;
G.vertices[i].firstarc->nextarc=NULL;
i++;
} // 这个过程为什么要从65 开始呢？不是最大有20个节点吗？G.vernum的下标应该是 0 - 19 猜对吧？
}
⑹ 无向图采用邻接表存储结构,编写算法输出图中各连通分量的节点序列
//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited.仅适用于邻接表结构
void BFSTraverse1(ALGraph G,void(* Visit)(char *))
{
int v,u;
ArcNode * p;//p指向表结点
LinkQueue Q;//链队列类型
for (v=0; v<G.vexnum; ++v)
{
visited[v] = FALSE;//置初值为未被访问
}
InitQueue(&Q);//初始化辅助队列Q
for (v=0; v<G.vexnum; ++v)//如果是连通图，只v=0就遍历全图
{
if (! visited[v])//v尚未被访问
{
visited[v] = TRUE;//设v为已被访问
Visit(G.vertices[v].data);//访问v
EnQueue(&Q,v);//v入队
while (! QueueEmpty(Q))//队列不空
{
DeQueue(&Q,&u);//队头元素出队并置为u
for (p=G.vertices[u].firstarc; p; p=p->next)//p依次指向u的邻接顶点
{
if (! visited[p->data.adjvex])//u的邻接顶点尚未被访问
{
visited[p->data.adjvex] = TRUE;//该邻接顶点设为已被访问
Visit(G.vertices[p->data.adjvex].data);//访问该邻接顶点
EnQueue(&Q,p->data.adjvex);//入队该邻接顶点序号
}
}
}//while
}//if
}//for(v=......)
printf("\n");
}
⑺ 一个连通图采用邻接表作为储存结构，设计一个算法～实现从顶点v出发的深度优先遍历的非递归过程
递归转非递归的常用方法是自己用栈来模拟，比较容易得到的方法是：
#include<iostream>
#include<vector>
#include<stack>
#include<cstring>
usingnamespacestd;
constintmaxn=1000000;
vector<int>G[maxn];
inte[maxn];
boolvisit[maxn];
voiddfs(intu)
{
visit[u]=true;
cout<<u<<endl;
for(inti=0;i<(int)G[u].size();++i){
if(!visit[G[u][i]])dfs(G[u][i]);
}
}
intn,s;//结点数,起点编号
intmain()
{
cin>>n;
for(inti=1;i<=n;++i){
intsz;
cin>>sz;
for(intj=0;j<sz;++j){
intv;
cin>>v;
G[i].push_back(v);
}
}
cin>>s;
dfs(s);
cout<<endl;
memset(visit,0,sizeof(visit));
stack<int>stk;
stk.push(s);
while(!stk.empty()){
intu=stk.top();stk.pop();
if(!visit[u]){
cout<<u<<endl;
visit[u]=true;
}
for(;e[u]<(int)G[u].size();++e[u]){
intv=G[u][e[u]];
if(visit[v])continue;
stk.push(u);stk.push(v);
break;
}
}
return0;
}
以上程序进行了一次递归遍历和依次非递归遍历，输入格式是：
10
18
14
19
225
248
31078
16
3156
2310
269
8
第一行表示结点数，第[2..n+1]行每行表示编号为[1..n]的结点的邻接表（邻接点数量结点编号...）
最后一行表示dfs的起点编号。
⑻ 采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。
思路是这样的：
1、从图中任选一个节点，以此节点进行深度优先搜索并将访问的节点做好标记，连通分量数加一。
2、在从图中没有访问的节点集中选一个节点重复1的过程直到所有节点都被标记
⑼ 无向带权图的邻接表怎么画
1、先把要讲解的图在下面展示一下，先看一下；
邻接表是图的常用储存结构之一。邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。