A. 數據結構C語言版 圖的遍歷 DFS和BFS演算法，用鄰接矩陣儲存 急阿在線等 求大神指點
#include <iostream>
#include<string.h>
#include<stack>
#include<queue>
const int Max=100;
const int VISITED=101010;
const int UNVISITED=111111;
const int AFFINITY=101010;
const int INFINITY=111111;
using namespace std;
class Edge
{
public:
int start;
int end;
int weight;
Edge(int st=0,int en=0,int w=0):start(st),end(en),weight(w){}
bool operator>(Edge oneEdge){return weight>oneEdge.weight?true:false;}
bool operator<(Edge oneEdge){return weight<oneEdge.weight?true:false;}
bool operator!=(Edge oneEdge)
{
if(weight!=oneEdge.weight||start!=oneEdge.start||end!=oneEdge.end)
return true;
return false;
}
};
class AdjGraf
{
private:
int verticesNum;
int edgeNum;
int **matrix;
int *Mark;
public:
AdjGraf(int vert)
{
int i=0,j=0;
verticesNum=vert;
matrix=(int**)new int*[vert];
for(i=0;i<vert;i++)
matrix[i]=new int[vert];
Mark=new int[vert];
for(i=0;i<vert;i++)
for(j=0;j<vert;j++)
{
matrix[i][j]=0;
}
for( int m=0;m<verticesNum;m++)
Mark[m]=UNVISITED;
}
~AdjGraf();
//返回與頂點oneVertex相關聯的第一條邊
Edge FirstEdge(int oneVertex);
//返回與邊PreEdge有相同關聯頂點oneVertex的下一條邊
Edge NextEdge( Edge preEdge);
//添加一條邊
void setEdge(int fromVertex,int toVertex,int weight);
//刪一條邊
void delEdge(int fromVertex,int toVertex);
//如果oneEdge是邊則返回TRUE，否則返回FALSE
bool IsEdge( Edge oneEdge)
{
if(oneEdge.start>=0&&oneEdge.start<verticesNum&&
oneEdge.end>=0&&oneEdge.end<verticesNum)
return true;
else return false;
}
//返回邊oneEdge的始點
int FromVertex(Edge oneEdge){return oneEdge.start;}
//返回邊oneEdge的終點
int ToVertex(Edge oneEdge){return oneEdge.end;}
//返回邊oneEdge的權
int Weight(Edge oneEdge){return oneEdge.weight;}
void visit(int i){cout<<i+1<<" ";}
void BFS(int i=1);
void DFS(int i);
void DFSTraverse(int v);
void DFSNoReverse(int f=1);
Edge UNVISITEDEdge(int f);
};
AdjGraf::~AdjGraf()
{
for(int i=0;i<verticesNum;i++)
delete[]matrix[i];
delete[]matrix;
}
Edge AdjGraf::FirstEdge(int oneVertex)
{ int i;
Edge tempEdge;
tempEdge.start=oneVertex;
for( i=0;i<verticesNum;i++)
if(matrix[oneVertex][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[oneVertex][i];
return tempEdge;
}
Edge AdjGraf ::NextEdge( Edge preEdge)
{
Edge tempEdge;
tempEdge.start=preEdge.start;
int i=0;
for(i=preEdge.end+1;i<verticesNum;i++)
if(matrix[preEdge.start][i]!=0)
break;
tempEdge.end=i;
tempEdge.weight=matrix[preEdge.start][i];
return tempEdge;
}
void AdjGraf::setEdge(int fromVertex,int toVertex,int weight)
{
if(matrix[fromVertex-1][toVertex-1]==0)
edgeNum++;
matrix[fromVertex-1][toVertex-1]=weight;
}
void AdjGraf::delEdge(int fromVertex,int toVertex)
{
if(matrix[fromVertex][toVertex]==0)
edgeNum--;
matrix[fromVertex][toVertex]=0;
}
/*************遞歸實現深度優先****************/
void AdjGraf::DFS(int i)
{
visit(i);
Mark[i]=VISITED;
for(Edge e=FirstEdge(i);IsEdge(e);e=NextEdge(e))
if(Mark[ToVertex(e)] == UNVISITED)
DFS(ToVertex(e));
}
void AdjGraf::DFSTraverse(int v)
{
v--;
int i;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
for(i=v;i<v+verticesNum;i++)
if (Mark[i]== UNVISITED)
DFS(i);
}
Edge AdjGraf::UNVISITEDEdge(int f)
{ int i;
for( Edge e=FirstEdge(f);IsEdge(e);e=NextEdge(e))
if(Mark[e.end]==UNVISITED)
return e;
return Edge(verticesNum,verticesNum,0) ;
}
/*************非遞歸實現深度優先**************/
void AdjGraf::DFSNoReverse(int f)
{
f--;
int i,counter=0,j,flag;
stack<int>Temp;
for(i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
flag=f;
while(counter<12)
{
while(flag!=verticesNum&&IsEdge(UNVISITEDEdge(flag))||!Temp.empty())
{
// Edge tempEdge=UNVISITEDEdge(j);
while(flag!=verticesNum&&Mark[flag]==UNVISITED)
{
visit(flag);
Mark[flag]=VISITED;
Temp.push(flag);
flag=UNVISITEDEdge(flag).end;
}
if(!Temp.empty())
{
flag=UNVISITEDEdge(Temp.top()).end;
Temp.pop();
}
}
if(Mark[counter]==UNVISITED) flag=counter;
else counter++;
}
}
/*************非遞歸實現廣度優先**************/
void AdjGraf::BFS(int v)
{
int i;
v--;
for( i=0;i<verticesNum;i++)
Mark[i]=UNVISITED;
queue<int>tempqueue;
i=0;
/*********v先從指定位置開始，然後從v=0,1,2......
依次檢查是否有孤立結點*****************/
while(i<verticesNum)
{
tempqueue.push(v);
while(!tempqueue.empty())
{
v=tempqueue.front();
tempqueue.pop();
if(Mark[v]==UNVISITED)
{
visit(v);
Mark[v]=VISITED;
for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e))
{
v=ToVertex(e);
tempqueue.push(v);
}
}
}
/***********防止出現孤立點****************/
if(Mark[i]==VISITED) i++;
else v=i;
}
}
int main()
{
AdjGraf Graph(12);
Graph.setEdge(1,2,1);
Graph.setEdge(2,1,1);
Graph.setEdge(1,3,5);
Graph.setEdge(3,1,5);/** V1 V12 V11 */
Graph.setEdge(2,4,3);/** / \ / \ */
Graph.setEdge(4,2,3);/** v2 v3 V10 V9 */
Graph.setEdge(2,5,7);/** / \ / \ */
Graph.setEdge(5,2,7);/** v4 v5 v6-v7 */
Graph.setEdge(4,8,4);/** \ / */
Graph.setEdge(8,4,4);/** v8 */
Graph.setEdge(5,8,3);
Graph.setEdge(8,5,3);
Graph.setEdge(3,6,2);
Graph.setEdge(6,3,2);
Graph.setEdge(3,7,1);
Graph.setEdge(7,3,1);
Graph.setEdge(6,7,6);
Graph.setEdge(7,6,6);
Graph.setEdge(12,9,6);
Graph.setEdge(9,12,6);
Graph.setEdge(12,10,6);
Graph.setEdge(10,12,6);
Graph.setEdge(11,11,6);
cout<<"DFSTraverse:"<<endl;
Graph.DFSTraverse(3);
cout<<endl;
cout<<"DFSNoReverse:"<<endl;
Graph.DFSNoReverse(3);
cout<<endl;
cout<<"BFS:"<<endl;
Graph.BFS(3);
cout<<endl;
return 0;
}
以上代碼運行環境codeblocks 程序採用DFS遞歸演算法 DFS非遞歸演算法 BFS非遞歸演算法
望採納~
B. 無向圖採用鄰接表存儲結構,編寫演算法輸出圖中各連通分量的節點序列
//按廣度優先非遞歸遍歷圖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");
}
C. 要求採用鄰接矩陣作為無向圖的存儲結構，鄰接表作為有向圖的存儲結構，完成無向圖和有向圖的建立，並對建
#include"utility.h"
#include"adj_matrix_undir_graph.h"
#include"adj_list_dir_graph.h"
#include"dfs.h"
#include"bfs.h"
int main(void)
{
int n,j=0,i=0;
int m,e,b=0;
char vexs[20],c;
char nums[20];
cout<<"輸入無向圖的頂點個數n:"<<endl;
cin>>n;
cout<<"輸入頂點元素："<<endl;
for(i=0;i<n;i++)
{
cout<<"請輸入第"<<j<<"個結點"<<endl;
cin>>vexs[i];
j++;
}
cout<<"輸出無向圖的鄰接矩陣："<<endl;
AdjMatrixUndirGraph<char> aundir(vexs,n);
for(i=0;i<n;i++)
{
for(int v=1;v<n;v++)
{
cout<<"輸入Y/N，是否插入邊:";
cin>>c;
if(c == 'Y' )
aundir.InsertEdge(i,v);
}
}
Display(aundir);
cout<<"請輸入有向圖的頂點個數m：";
cin>>m;
for(int a=0;a<m;a++)
{
cout<<"輸入第"<<b<<"個頂點數據";
cin>>nums[a];
b++;
}
AdjListDirGraph<char> dir(nums,m);
for(int k=0;k<m;k++)
{
for(e=0;e<m;e++)
{
cout<<"是否插入邊V"<<k<<",V"<<e<<":";
cin>>c;
if(c == 'Y' )
dir.InsertEdge(k,e);
}
}
Display(dir);
cout<<"無向圖的深度遍歷：";
DFSTraverse<char>(aundir,Write<char>);
cout<<endl;
cout<<"無向圖的廣度遍歷：";
BFSTraverse<char>(aundir,Write<char>);
cout<<endl;
cout<<"有向圖的深度遍歷：";
DFSTraverse<char>(dir,Write<char>);
cout<<endl;
cout<<"有向圖的廣度遍歷：";
BFSTraverse<char>(dir,Write<char>);