⑴ 《數據結構》以鄰接表位存儲，寫出連通圖的深度優先搜索法。
深度優先搜索法遍歷圖
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、先把要講解的圖在下面展示一下，先看一下；
鄰接表是圖的常用儲存結構之一。鄰接表由表頭結點和表結點兩部分組成，其中圖中每個頂點均對應一個存儲在數組中的表頭結點。