Skip to content

Instantly share code, notes, and snippets.

@daherk2

daherk2/Grafos_Caminho_CompCon.ipynb

Created November 8, 2019 22:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save daherk2/1fc238b684252c56171298ebb4a37a24 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save daherk2/1fc238b684252c56171298ebb4a37a24 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Grafos_Caminho_CompCon.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"# .-------- A0---A3---A5\n",
"# / /\n",
"# / .---------a7\n",
"# A1__/ / \\\n",
"# \\ / \\\n",
"# .-----A2--A4---A6"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"grafo = {\n",
"\"a0\" : ['a1','a2','a3'],\n",
"\"a1\" : ['a0','a2', 'a7'],\n",
"\"a2\" : ['a0','a1','a4'],\n",
"\"a3\" : ['a0', \"a5\"],\n",
"\"a4\" : ['a2','a6'],\n",
"\"a5\" : [\"a3\"],\n",
"\"a6\" : ['a4', 'a7'],\n",
"\"a7\" : [\"a1\", \"a6\"],\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"def encontra_caminho(grafo, ori, dst, caminho=[], visitado=[]):\n",
" viz = [ i for i in grafo[ori] if i not in visitado]\n",
" if ori == dst:\n",
" caminho.append(dst)\n",
" print(caminho)\n",
" else:\n",
" if len(viz) > 0:\n",
" if ori not in caminho:\n",
" visitado.append(ori)\n",
" caminho.append(ori)\n",
" encontra_caminho(grafo, viz[0], dst, caminho, visitado)\n",
" else:\n",
" encontra_caminho(grafo, caminho[len(caminho)-2], dst, caminho[:-1], visitado)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['a1', 'a0', 'a2']\n"
]
}
],
"source": [
"encontra_caminho(grafo, 'a1', 'a2')"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [],
"source": [
"def calc_comp_con(grafo):\n",
" visitado = []; comp =0;temp=0;maior=0;temp_comp=[];comps=[];\n",
" for i in list(grafo.keys()):\n",
" if i not in visitado:\n",
" visitado.append(i)\n",
" temp_comp.append(i)\n",
" comp = comp + 1\n",
" temp = 1 + visita_vizinho(grafo, i, visitado, temp_comp)\n",
" if temp > maior:\n",
" maior = temp\n",
" comps = temp_comp\n",
" temp_comp = []\n",
" return comp, maior, comps\n",
"\n",
"def visita_vizinho(grafo, atual, visitado, comps):\n",
" vizinhos = 0\n",
" for i in grafo[atual]:\n",
" if i not in visitado:\n",
" visitado.append(i)\n",
" comps.append(i)\n",
" vizinhos = vizinhos + 1 + visita_vizinho(grafo, i, visitado, comps)\n",
" return vizinhos"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1, 8, ['a0', 'a1', 'a2', 'a4', 'a6', 'a7', 'a3', 'a5'])"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"calc_comp_con(grafo)"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [],
"source": [
"def busca_em_profundidade(grafo, exp, visitado=[], state):\n",
" ini = grafo[exp]\n",
" visitado.append(exp)\n",
" print(ini)\n",
" print(visitado)\n",
" print ([i for i in ini if i not in visitado])\n",
" "
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['a1', 'a2', 'a3']\n",
"['a0', 'a1']\n",
"['a2', 'a3']\n"
]
}
],
"source": [
"busca_em_profundidade(grafo, \"a0\")"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"['a1', 'a2', 'a3']\n",
"visitados : ['a0']\n",
"Seleciona o : a1\n",
"********************\n",
"['a0', 'a2', 'a7']\n",
"visitados : ['a0', 'a1']\n",
"['a2', 'a7']\n",
"Seleciona o : a2\n",
"********************\n",
"['a0', 'a1', 'a4']\n",
"visitados : ['a0', 'a1', 'a2']\n",
"['a4']\n",
"Seleciona o : a4\n",
"********************\n",
"['a2', 'a6']\n",
"visitados : ['a0', 'a1', 'a2', 'a4']\n",
"['a6']\n",
"Seleciona o : ['a6']\n",
"********************\n",
"['a4', 'a7']\n",
"visitados : ['a0', 'a1', 'a2', 'a4', 'a6']\n",
"['a7']\n",
"Seleciona o : ['a7']\n",
"********************\n",
"['a1', 'a6']\n",
"visitados : ['a0', 'a1', 'a2', 'a4', 'a6', 'a7']\n",
"[]\n",
"Seleciona o : []\n",
"********************\n",
"Como o vetor de opcao de selecao esta vazio, volta-se na cabeca \n",
"['a1', 'a2', 'a3']\n",
"visitados : ['a0', 'a1', 'a2', 'a4', 'a6', 'a7']\n",
"['a3']\n",
"Seleciona o : ['a3']\n",
"********************\n",
"['a0', 'a5']\n",
"visitados : ['a0', 'a1', 'a2', 'a4', 'a6', 'a7', 'a3']\n",
"['a5']\n",
"Seleciona o : ['a5']\n",
"********************\n",
"['a3']\n",
"visitados : ['a0', 'a1', 'a2', 'a4', 'a6', 'a7', 'a3', 'a5']\n",
"[]\n",
"Seleciona o : []\n",
"********************\n",
"Como o vetor de opcao de selecao esta vazio, volta-se na cabeca \n",
"['a1', 'a2', 'a3']\n",
"visitados : ['a0', 'a1', 'a2', 'a4', 'a6', 'a7', 'a3', 'a5']\n",
"[]\n",
"Seleciona o : []\n",
"********************\n",
"Como o vetor de opcao de cabeca esta vazio, fim da execução \n"
]
}
],
"source": [
"print(grafo[\"a0\"])\n",
"print(\"visitados : \"+ str([\"a0\"]))\n",
"print(\"Seleciona o : \"+ str(grafo[\"a0\"][0]))\n",
"print(\"*\"*20)\n",
"print(grafo[\"a1\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\"]))\n",
"print([i for i in grafo[\"a1\"] if i not in [\"a0\", \"a1\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a1\"] if i not in [\"a0\", \"a1\"]][0]))\n",
"print(\"*\"*20)\n",
"print(grafo[\"a2\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\"]))\n",
"print([i for i in grafo[\"a2\"] if i not in [\"a0\", \"a1\", \"a2\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a2\"] if i not in [\"a0\", \"a1\", \"a2\"]][0]))\n",
"print(\"*\"*20)\n",
"print(grafo[\"a4\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\", \"a4\"]))\n",
"print([i for i in grafo[\"a4\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a4\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\"]]))\n",
"print(\"*\"*20)\n",
"print(grafo[\"a6\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\", \"a4\",\"a6\"]))\n",
"print([i for i in grafo[\"a6\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a6\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\"]]))\n",
"print(\"*\"*20)\n",
"print(grafo[\"a7\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\", \"a4\",\"a6\",\"a7\"]))\n",
"print([i for i in grafo[\"a7\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\", \"a7\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a7\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\",\"a7\"]]))\n",
"print(\"*\"*20)\n",
"print(\"Como o vetor de opcao de selecao esta vazio, volta-se na cabeca \")\n",
"print(grafo[\"a0\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\", \"a4\",\"a6\",\"a7\"]))\n",
"print([i for i in grafo[\"a0\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\", \"a7\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a0\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\",\"a7\"]]))\n",
"print(\"*\"*20)\n",
"print(grafo[\"a3\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\", \"a4\",\"a6\",\"a7\", \"a3\"]))\n",
"print([i for i in grafo[\"a3\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\", \"a7\", \"a3\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a3\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\",\"a7\", \"a3\"]]))\n",
"print(\"*\"*20)\n",
"print(grafo[\"a5\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\", \"a4\",\"a6\",\"a7\", \"a3\", \"a5\"]))\n",
"print([i for i in grafo[\"a5\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\", \"a7\", \"a3\", \"a5\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a5\"] if i not in [\"a0\", \"a1\", \"a2\", \"a4\",\"a6\",\"a7\", \"a3\", \"a5\"]]))\n",
"print(\"*\"*20)\n",
"print(\"Como o vetor de opcao de selecao esta vazio, volta-se na cabeca \")\n",
"print(grafo[\"a0\"])\n",
"print(\"visitados : \"+ str([\"a0\", \"a1\",\"a2\", \"a4\",\"a6\",\"a7\", \"a3\", \"a5\"]))\n",
"print([i for i in grafo[\"a0\"] if i not in [\"a0\", \"a1\",\"a2\", \"a4\",\"a6\",\"a7\", \"a3\", \"a5\"]])\n",
"print(\"Seleciona o : \"+ str([i for i in grafo[\"a0\"] if i not in [\"a0\", \"a1\",\"a2\", \"a4\",\"a6\",\"a7\", \"a3\", \"a5\"]]))\n",
"print(\"*\"*20)\n",
"print(\"Como o vetor de opcao de cabeca esta vazio, fim da execução \")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# .-------- A0---A3---A5\n",
"# / /\n",
"# / .---------a7\n",
"# A1__/ / \\\n",
"# \\ / \\\n",
"# .-----A2--A4---A6"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.5"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment