11_그래프(Graph).ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "자료구조_11_그래프(Graph).ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "mount_file_id": "1uVoqhZa4zynILAhm5bFYnabZp62gqDVX",
      "authorship_tag": "ABX9TyMgqBkqJ25YC2a6be87qVbt",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sejin-sim/Data_structure/blob/master/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0_11_%EA%B7%B8%EB%9E%98%ED%94%84(Graph).ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "8x2wfkSSf9NT",
        "outputId": "d528af17-c7e1-4179-a803-562f70199935"
      },
      "source": [
        "# 인접행렬 그래프\n",
        "\n",
        "global Max\n",
        "Max = 256\n",
        "\n",
        "class AdjMatGraph:\n",
        "  def __init__(self): # 정점과 정점의 관계를 행렬로\n",
        "    self.adj = [[0 for j in range(Max)] for i in range(Max)] \n",
        "    self.vertices = []                                       \n",
        "\n",
        "  def size(self): # 정점 갯수\n",
        "    return len(self.vertices)\n",
        "  \n",
        "  def reset(self): # 초기화\n",
        "    self.adj = [[0 for j in range(Max)] for i in range(Max)]\n",
        "    \n",
        "  def setEdge(self, i, j, val): # 간선 셋팅\n",
        "    self.adj[i][j] = val\n",
        "\n",
        "  def insertVertex(self, V):  # 정점 삽입\n",
        "    self.vertices.append(V)\n",
        "  \n",
        "  def insertEdge(self, u, v): # 간선 삽입\n",
        "    self.setEdge(u, v, 1) \n",
        "    self.setEdge(v, u, 1) # 방향 그래프에서는 삭제됨\n",
        "\n",
        "  def getVertex(self, i): # 위치로 정점(문자) 가져오기\n",
        "    return self.vertices[i]\n",
        "  \n",
        "  def getEdge(self, i, j): # 간선의 값(숫자 0 or 1) 가져오기\n",
        "    return self.adj[i][j]\n",
        "\n",
        "  def display(self):\n",
        "    print(self.size())\n",
        "    for i in range(0, self.size()):\n",
        "      print(self.getVertex(i), end=\" \")\n",
        "\n",
        "      for j in range(0, self.size()):\n",
        "        print(self.getEdge(i, j), end=\" \")\n",
        "      print()\n",
        "  \n",
        "g = AdjMatGraph()\n",
        "for i in range(0, 4):\n",
        "  g.insertVertex(chr(65+i))\n",
        "\n",
        "g.insertEdge(0,1)\n",
        "g.insertEdge(0,3)\n",
        "g.insertEdge(1,2)\n",
        "g.insertEdge(1,3)\n",
        "g.insertEdge(2,3)\n",
        "print(\"인접 행렬로 표현한 그래프\")\n",
        "g.display()\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "인접 행렬로 표현한 그래프\n",
            "4\n",
            "A 0 1 0 1 \n",
            "B 1 0 1 1 \n",
            "C 0 1 0 1 \n",
            "D 1 1 1 0 \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "WKUqZZSHnN9T",
        "outputId": "f1033c2d-d0c8-407c-e7ee-9529cd42ca56"
      },
      "source": [
        "# 인접리스트 그래프\n",
        "\n",
        "global Max\n",
        "Max = 256\n",
        "\n",
        "class Node:\n",
        "  def __init__(self, id, link):\n",
        "    self.id = id\n",
        "    self.link = link\n",
        "\n",
        "class AdjListGraph:\n",
        "  def __init__(self): # 정점과 정점의 관계\n",
        "    self.vertices = [] \n",
        "    self.adj = [0 for j in range(Max)]\n",
        "\n",
        "  def size(self):\n",
        "    return len(self.vertices)\n",
        "\n",
        "  def insertVertex(self, V):\n",
        "    self.vertices.append(V)\n",
        "  \n",
        "  def insertEdge(self, u, v):          # 간선삽입 ex) 0, 1\n",
        "    self.adj[u] = Node(v, self.adj[u]) # self.adj[0] = Node(1, self.adj[0])\n",
        "    self.adj[v] = Node(u, self.adj[v]) # self.adj[1] = Node(0, self.adj[1])\n",
        "\n",
        "  def getVertex(self, i):\n",
        "    return self.vertices[i]\n",
        "  \n",
        "  def display(self):\n",
        "    print(self.size())\n",
        "\n",
        "    for i in range(0, self.size()):\n",
        "      print(self.getVertex(i), end=\" \")\n",
        "\n",
        "      v = self.adj[i]\n",
        "      while v != 0:\n",
        "        print(self.getVertex(v.id), end=\" \")\n",
        "        v = v.link\n",
        "      print()\n",
        "\n",
        "g = AdjListGraph()\n",
        "for i in range(0, 4):\n",
        "  g.insertVertex(chr(65+i))\n",
        "g.insertEdge(0,1)\n",
        "g.insertEdge(0,3)\n",
        "g.insertEdge(1,2)\n",
        "g.insertEdge(1,3)\n",
        "g.insertEdge(2,3)\n",
        "print(\"인접 리스트로 표현한 그래프\")\n",
        "g.display()\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "인접 리스트로 표현한 그래프\n",
            "4\n",
            "A D B \n",
            "B D C A \n",
            "C D B \n",
            "D C B A \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QUd03JZ76JGt",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "3ddf39ec-75c7-4f21-925d-a22138499b33"
      },
      "source": [
        "# DFS(신장 트리) & BFS with 인접행렬\n",
        "\n",
        "global Max\n",
        "Max = 256\n",
        "\n",
        "# 큐(queue) 기본(basic)_원형\n",
        "class CircularQueue:\n",
        "  def __init__(self):\n",
        "      self.rear = 0\n",
        "      self.front = 0\n",
        "      self.data = []\n",
        "      self.MaxSize = 100\n",
        "\n",
        "  def size(self):\n",
        "      return len(self.data)\n",
        "\n",
        "  def isFull(self):\n",
        "      return self.size() == self.MaxSize\n",
        "\n",
        "  def isEmpty(self):\n",
        "      return self.size() == 0\n",
        "\n",
        "  def enqueue(self, item):\n",
        "      if self.isFull():\n",
        "        print(\"error: 큐가 포화상태입니다.\")\n",
        "      else:\n",
        "        self.data.append(item)\n",
        "        self.rear = (self.rear +1) % self.MaxSize\n",
        " \n",
        "  def dequeue(self):\n",
        "     if self.isEmpty():\n",
        "       print(\"error: 큐가 공백상태입니다.\")\n",
        "     else:\n",
        "       self.front = (self.front +1) % self.MaxSize\n",
        "       return self.data.pop(0)\n",
        "\n",
        "class SrchAMGraph(AdjMatGraph, CircularQueue):\n",
        "  def __init__(self):\n",
        "    self.adj = [[0 for j in range(Max)] for i in range(Max)]\n",
        "    self.vertices = []\n",
        "    self.visited = [0 for j in range(Max)]\n",
        "    self.finished = [0 for j in range(Max)]\n",
        "    self.haveCycle = False\n",
        "\n",
        "  def resetVisited(self):\n",
        "    for i in range(0, self.size()):\n",
        "      self.visited[i] = False\n",
        "\n",
        "  def isLinked(self, u, v):\n",
        "    if self.getEdge(u, v) != 0:\n",
        "      return True\n",
        "    else:\n",
        "      return False\n",
        "\n",
        "  def DFS(self, v):\n",
        "    self.visited[v] = True\n",
        "    print(self.getVertex(v), end = \" \")\n",
        "    for w in range(self.size()):\n",
        "      if self.isLinked(v, w) and self.visited[w] == False:\n",
        "        self.DFS(w)\n",
        "\n",
        "  def spanningTreeByDFS(self, v):\n",
        "    self.visited[v] = True\n",
        "    for w in range(self.size()):\n",
        "      if self.isLinked(v, w):\n",
        "        if self.visited[w] != True:\n",
        "          print(\"신장트리간선 :\", self.getVertex(v),\"-\", self.getVertex(w))\n",
        "          self.spanningTreeByDFS(w)\n",
        "        elif self.finished[w] != True:\n",
        "          self.haveCycle = True\n",
        "    self.finished[v] = True\n",
        "\n",
        "  def BFS(self, v):\n",
        "    self.visited[v] = True\n",
        "    print(self.getVertex(v), end = \" \")\n",
        "    que = CircularQueue()\n",
        "    que.enqueue(v)\n",
        "    while que.isEmpty() != True :\n",
        "      v = que.dequeue()\n",
        "      for w in range(0, self.size()):\n",
        "        if self.isLinked(v,w) and self.visited[w] == False:\n",
        "          self.visited[w] = True\n",
        "          print(self.getVertex(w), end = \" \")\n",
        "          que.enqueue(w)\n",
        "\n",
        "  def load(self, filename):\n",
        "    fp = open(filename, \"r\")\n",
        "    if( fp != None ):\n",
        "      n = int(fp.readline())\n",
        "      for i in range(0, n):\n",
        "        str = list(fp.readline().split())\n",
        "        self.insertVertex(str[0])\n",
        "        \n",
        "        for j in range(0, n):\n",
        "          if int(str[j+1]) == 1:\n",
        "            self.insertEdge(i,j)\t\n",
        "\n",
        "    fp.close()\n",
        "\n",
        "\n",
        "g = SrchAMGraph()\n",
        "g.load(\"/content/drive/MyDrive/자료구조/업로드/graph.txt\")\n",
        "print(\"그래프(graph.txt)\\n\")\n",
        "g.display()\n",
        "      \n",
        "print(\"\\nDFS ==> \", end=\"\")\n",
        "g.resetVisited()\n",
        "g.DFS(0)\n",
        "\n",
        "print(\"\\n\\nSpanningTreeByDFS\")\n",
        "g.resetVisited()\n",
        "g.spanningTreeByDFS(0)\n",
        "print(\"사이클이 있나요?\", g.haveCycle)\n",
        "print(\"\\nBFS ==> \", end=\"\")\n",
        "g.resetVisited()\n",
        "g.BFS(0)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "그래프(graph.txt)\n",
            "\n",
            "8\n",
            "A 0 1 1 0 0 0 0 0 \n",
            "B 1 0 0 1 0 0 0 0 \n",
            "C 1 0 0 1 1 0 0 0 \n",
            "D 0 1 1 0 0 1 0 0 \n",
            "E 0 0 1 0 0 0 1 1 \n",
            "F 0 0 0 1 0 0 0 0 \n",
            "G 0 0 0 0 1 0 0 1 \n",
            "H 0 0 0 0 1 0 1 0 \n",
            "\n",
            "DFS ==> A B D C E G H F \n",
            "\n",
            "SpanningTreeByDFS\n",
            "신장트리간선 : A - B\n",
            "신장트리간선 : B - D\n",
            "신장트리간선 : D - C\n",
            "신장트리간선 : C - E\n",
            "신장트리간선 : E - G\n",
            "신장트리간선 : G - H\n",
            "신장트리간선 : D - F\n",
            "사이클이 있나요? True\n",
            "\n",
            "BFS ==> A B C D E F G H "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "6az_8MEjT7N2",
        "outputId": "41487770-c6b1-44ff-98e2-9f14a4a06734"
      },
      "source": [
        "# 연결 성분 with 인접 행렬\n",
        "\n",
        "global Max\n",
        "Max = 256\n",
        "\n",
        "class ConnectedComponentGraph(SrchAMGraph):\n",
        "  def __init__(self):\n",
        "    self.adj = [[0 for j in range(Max)] for i in range(Max)]\n",
        "    self.label = [0 for j in range(Max)]\n",
        "    self.vertices = []\n",
        "    self.visited = [0 for j in range(Max)]\n",
        "\n",
        "  def labelDFS(self, v, color):\n",
        "    self.visited[v] = True\n",
        "    self.label[v] = color\n",
        "\n",
        "    for w in range(0, self.size()):\n",
        "      if self.isLinked(v, w) and self.visited[w] == False:\n",
        "        self.labelDFS(w, color)\n",
        "\n",
        "  def findConnectedComponent(self):\n",
        "    count = 0\n",
        "    for i in range(self.size()):\n",
        "      if self.visited[i] == False:\n",
        "        count += 1\n",
        "        self.labelDFS(i, count)\n",
        "    print(\"그래프 연결성분 개수 = =\", count)\n",
        "\n",
        "    for i in range(self.size()):\n",
        "      print(\"{}={} \".format(self.getVertex(i), self.label[i]), end= \"\")\n",
        "    # return count\n",
        "\n",
        "\n",
        "g = ConnectedComponentGraph()\n",
        "for i in range(0, 5):\n",
        "  g.insertVertex(chr(65+i))\n",
        "\n",
        "g.insertEdge(1, 0)\n",
        "g.insertEdge(2, 0)\n",
        "g.insertEdge(3, 4)\n",
        "print(\"연결 성분 그래프 테스트 그래프\")\n",
        "g.display()\n",
        "g.resetVisited()\n",
        "g.findConnectedComponent()"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "연결 성분 그래프 테스트 그래프\n",
            "5\n",
            "A 0 1 1 0 0 \n",
            "B 1 0 0 0 0 \n",
            "C 1 0 0 0 0 \n",
            "D 0 0 0 0 1 \n",
            "E 0 0 0 1 0 \n",
            "그래프 연결성분 개수 = = 2\n",
            "A=1 B=1 C=1 D=2 E=2 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PoXZkT4gunWC",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "c1457de4-9573-4634-bcfa-b9783e1d8d0e"
      },
      "source": [
        "# 브리지 찾기 with 인접 행렬\n",
        "\n",
        "global Max\n",
        "Max = 256\n",
        "\n",
        "class ConnectedComponentGraph(SrchAMGraph):\n",
        "  def __init__(self):\n",
        "    self.adj = [[0 for j in range(Max)] for i in range(Max)]\n",
        "    self.label = [0 for j in range(Max)]\n",
        "    self.vertices = []\n",
        "    self.visited = [0 for j in range(Max)]\n",
        "\n",
        "  def labelDFS(self, v, color):\n",
        "    self.visited[v] = True\n",
        "    self.label[v] = color\n",
        "\n",
        "    for w in range(0, self.size()):\n",
        "      if self.isLinked(v, w) and self.visited[w] == False:\n",
        "        self.labelDFS(w, color)\n",
        "\n",
        "  def findConnectedComponent(self):\n",
        "    count = 0\n",
        "    for i in range(self.size()):\n",
        "      if self.visited[i] == False:\n",
        "        count += 1\n",
        "        self.labelDFS(i, count)\n",
        "\n",
        "    return count\n",
        "\n",
        "def findBridge(g):\n",
        "\tcount = 0\n",
        "\tg.resetVisited()\n",
        "\n",
        "\tfor i in range(0, g.size()):\n",
        "\t\tfor j in range(0, i):\n",
        "\t\t\tif g.getEdge(i, j) != 0:\n",
        "\t\t\t\tg.setEdge(i, j, 0)\n",
        "\t\t\t\tg.setEdge(j, i, 0)\n",
        "\t\t\n",
        "\t\t\t\tg.resetVisited()\n",
        "\t\t\t\tif g.findConnectedComponent() > 1:\n",
        "\t\t\t\t\tprint(\"Bridge{} : {}-{}\".format(count+1, g.getVertex(i), g.getVertex(j)))\n",
        "\t\t\t\t\tcount += 1\n",
        "\t\t\t\tg.setEdge(i, j, 1)\n",
        "\t\t\t\tg.setEdge(j, i, 1)\n",
        "\t\t\n",
        "\treturn count\n",
        "\n",
        "g = ConnectedComponentGraph()\n",
        "\n",
        "g.load(\"/content/drive/MyDrive/자료구조/업로드/graph.txt\")\n",
        "print(\"그래프(graph.txt)\\n\")\n",
        "g.display()\n",
        "g.resetVisited()\n",
        "g.findConnectedComponent()\n",
        "print(\"Bridge :\", findBridge(g))\n"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "그래프(graph.txt)\n",
            "\n",
            "8\n",
            "A 0 1 1 0 0 0 0 0 \n",
            "B 1 0 0 1 0 0 0 0 \n",
            "C 1 0 0 1 1 0 0 0 \n",
            "D 0 1 1 0 0 1 0 0 \n",
            "E 0 0 1 0 0 0 1 1 \n",
            "F 0 0 0 1 0 0 0 0 \n",
            "G 0 0 0 0 1 0 0 1 \n",
            "H 0 0 0 0 1 0 1 0 \n",
            "Bridge1 : E-C\n",
            "Bridge2 : F-D\n",
            "Bridge : 2\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}