一份数据结构的作业,xx而已.

邻接矩阵可用二维数组来实现.邻接矩阵更适合用深度优先搜索(DFS),一个递归算法即可实现,无须用到队列.为了实现结构化编程,编写了dfs(),isConnected()两个函数来分别实现深度优先搜索和多次查询中每次查询前的初始化的功能.

dfs()函数是实现深度优先搜索的函数,以输入的{dy}个节点为起始节点,在邻接矩阵中寻找与其相邻的非零节点,若找到一个非零节点,便就寻找该非零节点相邻的其它非零节点,而不是寻找出所有非零的节点放到队列里面.在寻找非零节点的过程中要判断该节点是否是输入的第二个节点.在深度优先搜索中的{dy}个for循环和isVisited[]数组保证了每个节点都得到访问(完备性).

在递归的过程中,函数不停地去保存现场,实质上用到了栈的思想,只是计算机底层帮我们实现了,我们无须编写.在程序中我用check这个全局变量来指示是否连通,这样就避免每次递归都须返回值.

该程序并没有实现通用性(矩阵阶数,矩阵输入等).程序用C++实现,主要用到了输入输出流.

代码：

#include<iostream>
using namespace std;
int visited[5];
bool check;

void dfs(int p[5][5],int r,int s){
    int j;
    visited[r] = 1;
    for(j=0;j<5;j++){
        int node = *(*(p+r)+j);
        if(node!=0&&visited[j]==0){
            if(j==s){
                check = true;
            }
            else{
                dfs(p,j,s);
            }
        }
    }
}

bool isConnected(int p[5][5],int i,int j){
    int k;
    check = false;
    for(k=0;k<5;k++){
        visited[k] = 0;
    }
    dfs(p,i,j);
    return check;
}

int main(){
    int a,b;
    int array[5][5] = { {0,1,0,1,0},
                        {1,0,0,0,0},
                        {0,0,0,0,1},
                        {1,0,0,0,0},
                        {0,0,1,0,0} };
    while(cin>>a>>b&&a!=-1&&b!=-1){
        if(isConnected(array,a,b)){
            cout<<"节点"<<a<<"和节点"<<b<<"连通."<<endl;
            continue;
        }
        cout<<"节点"<<a<<"和节点"<<b<<"不连通."<<endl;
    }
}

运行结果：

0 1

节点0和节点1连通.

1 3

节点1和节点3连通.

2 4

节点2和节点4连通.

1 2

节点1和节点不连通.

…