无向图以邻接矩阵存储,请算法描述深度优先遍历该图的非递归算法 5C

无向图以邻接矩阵存储,请算法描述深度优先遍历该图的非递归算法。哪位大神可以帮忙写具体点用栈怎么实现?谢谢了!图片说明

3个回答

深度优先遍历算法的非递归实现需要了解深度优先遍历的执行过程,设计一个栈来模拟递归实现中系统设置的工作栈,算法的伪代码描述为:
图片说明

深度优先遍历算法的非递归实现需要了解深度优先遍历的执行过程,设计一个栈来模拟递归实现中系统设置的工作栈,算法的伪代码描述为:

  假设图采用邻接矩阵作为存储结构,具体算法如下:

#include  
#include   
using namespace std;  
#define  MAX_NODE 12  
bool visited[MAX_NODE] ;  
int stack[ MAX_NODE] ;  
queue q;  
int Matric[MAX_NODE][MAX_NODE] =  
{  
    {-1,1,1,0,0,0,0,0,0,0,0,0},  
    {1,-1,1,0,1,1,0,0,0,0,0,0},  
    {1,1,-1,1,0,0,0,0,0,0,0,0},  
    {0,0,1,-1,1,0,0,0,0,0,1,1},  
    {0,1,0,1,-1,0,0,0,0,0,0,0},  
    {0,1,0,0,0,-1,0,0,0,0,1,0},  
    {0,0,0,0,0,0,-1,1,1,1,0,0},  
    {0,0,0,0,0,0,1,-1,0,0,0,0},  
    {0,0,0,0,0,0,1,0,-1,1,1,0},  
    {0,0,0,0,0,0,1,0,1,-1,0,1},  
    {0,0,0,1,0,1,0,0,1,0,-1,0},  
    {0,0,0,1,0,0,0,0,0,1,0,-1},   
};  
void DFS( int v)  
{  
    cout   

  

伪代码说明
图片说明

s_listening
s_listening 这么类c的伪代码看不懂就没办法了[掩面]
大约 2 年之前 回复
xfjjs_net
xfjs江城子 可以帮我用语言描述出来吗?这样我看的懂些,谢谢啦
大约 2 年之前 回复
s_listening
s_listening 那个 n = & a.top() 有点问题, 看得懂就好了..
大约 2 年之前 回复

void DFS( int v)

{

cout << " v"<< v ;

int top = -1 ;

visited[v] = true ;

stack[++top] = v ;

while ( top != -1)

{

v = stack[top] ;

for (int i = 0 ; i < MAX_NODE ; i++)

{

if (Matric[v][i] == 1 &&!visited[i])

{

cout << " v" << i ;

visited[i] = true ;

stack[ ++top ] = i ;

break ;

}

}

if( i == MAX_NODE)

{

top -- ;

}

}

}

void BFS( int v)

{

int node = 0;

q.push(v);

visited[v] = true;

while( !q.empty())

{

node = q.front();

for ( int i = 0; i < MAX_NODE; i++ )

{

if ( Matric[node][i] == 1 && !visited[i])

{

visited[i] = true;

q.push(i);

}

}

cout <<" v" << node;

q.pop();

}

}

void Init()

{

int i = 0;  
for ( i = 0; i < MAX_NODE; i++)  
{  
    visited[i] = false;  
}  

}

int main()

{

Init();

DFS( 1 ) ;

cout << endl ;

Init();

BFS( 1 );

cout << endl;

Init();

DFS( 6 );

cout < return 0 ;
}

  


    
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问