图的深搜和广搜--邻接矩阵

一、深度优先搜索

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

const int N = 60;
int n;
int vex[N], matrix[N][N];

/*
 * 输入矩阵队列图
 */
void scanf_graph(int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n; j++)
            scanf("%d ", &matrix[i][j]);
//        printf("\n");
    }
}

/*
 * 创建图(自己输入)
 */
void create_graph(int n)
{
    // 初始化"顶点"
    for (int i = 0; i < n; i ++) vex[i] = i; 

    scanf_graph(n);
}

/*
 * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
 */
static int first_vertex(int v)
{
    if (v<0 || v>(n-1))  return -1;
        
    for (int i = 0; i < n; i++)
        if (matrix[v][i] == 1)
            return i;

    return -1;
}

/*
 * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
 */
static int next_vertix(int v, int w)
{
    if (v<0 || v>(n-1) || w<0 || w>(n-1)) return -1;

    for (int i = w + 1; i < n; i++)
        if (matrix[v][i] == 1)
            return i;

    return -1;
}

static void DFS(int i, int *visited)
{    
	// 标记为1 代表已访问 
    visited[i] = 1;
    printf("%d ", vex[i]);
    
    // 遍历该顶点的所有邻接顶点。w为邻接顶点索引，若是没有访问过，那么继续往下走
    for (int w = first_vertex(i); w >= 0; w = next_vertix(i, w))
        if (!visited[w])
            DFS(w, visited);   
}

/*
 * 深度优先搜索遍历图
 */
void DFSTraverse()
{
    int i;
    int visited[N];       // 顶点访问标记

    // 初始化所有顶点都没有被访问
    for (i = 0; i < n; i++)  visited[i] = 0;        

    for (i = 0; i < n; i ++)
        if (!visited[i])
            DFS(i, visited);
            
    printf("\n");
}


int main(void)
{
	scanf("%d", &n);
	create_graph(n);
	DFSTraverse();
	
}

二、广度优先搜索

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

const int N = 60;
int n;
int vex[N], matrix[N][N];

/*
 * 输入矩阵队列图
 */
void scanf_graph(int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < n; j++)
            scanf("%d ", &matrix[i][j]);
//        printf("\n");
    }
}

/*
 * 创建图(自己输入)
 */
void create_graph(int n)
{
    // 初始化"顶点"
    for (int i = 0; i < n; i ++) vex[i] = i; 

    scanf_graph(n);
}

/*
 * 返回顶点v的第一个邻接顶点的索引，失败则返回-1
 */
static int first_vertex(int v)
{
    if (v<0 || v>(n-1))  return -1;
        
    for (int i = 0; i < n; i++)
        if (matrix[v][i] == 1)
            return i;

    return -1;
}

/*
 * 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
 */
static int next_vertix(int v, int w)
{
    if (v<0 || v>(n-1) || w<0 || w>(n-1)) return -1;

    for (int i = w + 1; i < n; i++)
        if (matrix[v][i] == 1)
            return i;

    return -1;
}

/*
 * 广度优先搜索（类似于树的层次遍历）
 */
void BFS()
{
    int head = 0;
    int rear = 0;
    int queue[N];     // 辅组队列
    int visited[N];   // 顶点访问标记
    int i, j, k;

    for (i = 0; i < n; i ++)   visited[i] = 0;
       
    for (i = 0; i < n; i ++)
    {
        if (!visited[i])
        {
            visited[i] = 1;
            printf("%d ", vex[i]);
            queue[rear++] = i;  // 入队列
        }
        while (head != rear) 
        {
            j = queue[head++];  // 出队列
            for (k = first_vertex(j); k >= 0; k = next_vertix(j, k)) //k是为访问的邻接顶点
            {
                if (!visited[k])
                {
                    visited[k] = 1;
                    printf("%d ", vex[k]);
                    queue[rear++] = k;
                }
            }
        }
    }
    printf("\n");
}

int main(void)
{
	scanf("%d", &n);
	create_graph(n);
	BFS();
}